Algebraic types in haskell

Question

How can I simplify an expression using basic arithmetic?

Answer 1

You can use the technique described here: http://augustss.blogspot.com/2007/04/overloading-haskell-numbers-part-2.html . Make your type be of the necassary type-classes (Num, Fractional, Floating) so that -, +, * and so on works for your type. Then if the expression tree is finally built, you can operate on it to see what you can simplify.

Answer 2

I'm not sure what you mean, but if you have an expression datatype you can define a recursive eval-function. In this case eval means simplify.

For example,

data Exp = Lit Int
         | Plus Exp Exp
         | Times Exp Exp

eval :: Exp -> Int
eval (Lit x)     = x
eval (Plus x y)  = eval x + eval y
eval (Times x y) = eval x * eval y

It gets really interesting once you add variables to the language, but this is the most basic form of an expression-evaluator.

Answer 3

module Expr where

-- Variables are named by strings, assumed to be identifiers. type Variable = String

-- Representation of expressions. data Expr = Const Integer | Var Variable | Plus Expr Expr | Minus Expr Expr | Mult Expr Expr deriving (Eq, Show)

Simplifications such as 0*e=e*0=0 and 1*e=e*1=0+e=e+0=e-0=e and simplifying constant subexpressions, e.g. Plus (Const 1) (Const 2) would become Const 3. I would not expect variables (or variables and constants) to be concatenated: Var "st" is a distinct variable from Var "s".

they need to be written like the following simplify (Plus (Var'x') (Const 0)) = Var"x"