owen@bast:~/Code/Haskell$ cat Express.hs
module Express where

data Expr a = X | Lit a | Neg (Expr a)
            | Add (Expr a) (Expr a)
            | Sub (Expr a) (Expr a)
            | Mul (Expr a) (Expr a)
            | Div (Expr a) (Expr a) -- left divided by right
            | Pow (Expr a) (Expr a) -- left to the power of right
            deriving Show

-- Simplification
simplify (Add (Lit a) (Lit b)) = Lit (a + b)
simplify (Add (Lit a) b) = Lit a +/ simplify b
simplify (Add a (Lit b)) = simplify a +/ Lit b
simplify (Add a X) = (simplify a) +/ X
simplify (Add X a) = X +/ (simplify a)
simplify (Add a b) = rsimplify a b (+/)

simplify (Sub (Lit a) (Lit b)) = Lit (a - b)
simplify (Sub (Lit a) b) = Lit a -/ simplify b
simplify (Sub a (Lit b)) = simplify a -/ Lit b
simplify (Sub a X) = (simplify a) -/ X
simplify (Sub X a) = X -/ (simplify a)
simplify (Sub a b) = rsimplify a b (-/)

simplify (Mul (Lit a) (Lit b)) = Lit (a * b)
simplify (Mul (Lit a) b) = Lit a */ simplify b
simplify (Mul a (Lit b)) = simplify a */ Lit b
simplify (Mul a X) = simplify a */ X
simplify (Mul X a) = X */ simplify a
simplify (Mul a b) = rsimplify a b (*/)

simplify (Div (Lit a) (Lit b)) = Lit (a / b)
simplify (Div (Lit a) b) = Lit a // simplify b
simplify (Div a (Lit b)) = simplify a // Lit b
simplify (Div a X) = (simplify a) // X
simplify (Div X a) = X // (simplify a)
simplify (Div a b) = rsimplify a b (//)

simplify (Pow (Lit a) (Lit b)) = Lit (a ^ b)
simplify (Pow (Lit a) b) = Lit a ^/ simplify b
simplify (Pow a (Lit b)) = simplify a ^/ Lit b
simplify (Pow X a) = X ^/ simplify a
simplify (Pow a X) = simplify a ^/ X
simplify (Pow a b) = rsimplify a b (^/)

simplify a = a -- nothing else worked, must be as simple as it can get.

rsimplify a b op = simplify (simplify a `op` simplify b)

-- Nice operators for constructing Exprs in a more natural way
a +/ b = Add a b
a -/ b = Sub a b
a */ b = Mul a b
a ^/ b = Pow a b
a // b = Div a b
owen@bast:~/Code/Haskell$ hugs Express.hs
__   __ __  __  ____   ___      _________________________________________
||   || ||  || ||  || ||__      Hugs 98: Based on the Haskell 98 standard
||___|| ||__|| ||__||  __||     Copyright (c) 1994-2005
||---||         ___||           World Wide Web: http://haskell.org/hugs
||   ||                         Report bugs to: hugs-bugs@haskell.org
||   || Version: 20050308       _________________________________________

Haskell 98 mode: Restart with command line option -98 to enable extensions

Type :? for help
Express> Lit 2 ^/ Lit 3
Pow (Lit 2) (Lit 3)
Express> simplify (Lit 2 ^/ Lit 3)
ERROR - Unresolved overloading
*** Type       : (Fractional a, Integral a) => Expr a
*** Expression : simplify (Lit 2 ^/ Lit 3)