haskell - types - functions - trees

Question

For haskell practice I want to implement a game where students/pupils should learn some algebra playfully.

As basic datatype I want to use a tree:

• with nodes that have labels and algebraic operators stored.
• with leaves that have labels and variables (type String) or numbers

Now I want to define something like

data Tree = Leaf {l :: Label, val :: Expression}
          | Node {l :: Label, f :: Fun, lBranch :: Tree, rBranch :: Tree}

data Fun = "one of [(+),(*),(-),(/),(^)]"

-- type Fun = Int -> Int 

would work

Next things I think about is to make a 'equivalence' of trees - as multiplication/addition is commutative and one can simplify additions to multiplication etc. the whole bunch of algebraic operations. I also have to search through the tree - by label I think is best, is this a good approach.

Any ideas what tags/phrases to look for and how to solve the "data Fun".

Answer 1

To expand a bit on Edward Z. Yang's answer:

The simplest way to define your operators here is probably as a data type, along with the types for atomic values in leaf nodes and the expression tree as a whole:

data Fun = Add | Mul | Sub | Div | Exp deriving (Eq, Ord, Show)

data Val a = Lit a | Var String deriving (Eq, Ord, Show)

data ExprTree a = Node String Fun (ExprTree a) (ExprTree a)
                | Leaf String (Val a)
    deriving (Eq, Ord, Show)

You can then define ExprTree a as an instance of Num and whatnot:

instance (Num a) => Num (ExprTree a) where
    (+) = Node "" Add
    (*) = Node "" Mul
    (-) = Node "" Sub
    negate = Node "" Sub 0
    fromInteger = Leaf "" . Lit

...which allows creating unlabelled expressions in a very natural way:

*Main> :t 2 + 2
2 + 2 :: (Num t) => t
*Main> 2 + 2 :: ExprTree Int
Node "" Add (Leaf "" (Lit 2)) (Leaf "" (Lit 2))

Also, note the deriving clauses above on the data definitions, particularly Ord; this tells the compiler to automatically create an ordering relation on values of that type. This lets you sort them consistently which means you can, for instance, define a canonical ordering on subexpressions so that when rearranging commutative operations you don't get stuck in a loop. Given some canonical reductions and subexpressions in canonical order, in most cases you'll then be able to use the automatic equality relation given by Eq to check for subexpression equivalence.

Note that labels will affect the ordering and equality here. If that's not desired, you'll need to write your own definitions for Eq and Ord, much like the one I gave for Num.

After that, you can write some traversal and reduction functions, to do things like apply operators, perform variable substitution, etc.

Answer 2

It looks like you want to construct a symbolic algebra system. There is a large and varied literature on the subject.

You don't want to represent operators as Int -> Int, because then you can't check what operation any given function implements and then implement peephole optimization for things like simplification, etc. So a simple enumerated data type would do the trick, and then write the function eval which actually evaluates your tree.