Algebraic Expression Languages   [1]

Representing tree-like structures in Haskell

The natural way to represent tree-like structures in Haskell is to use a recursive algebraic data type. The declaration below is similar to the one we used for natural numbers (or to the one we would use for lists, if they weren't already built in). As for these other data types, we have a base case and recursive cases, each with a constructor. But with the Expr type we have two recursive sub-trees, representing the left and right arguments of the binary operators Add and Mul: this non-linearity is what gives these structures their characteristic tree-like shapes. (Lists have a degenerate tree-like shape when we view them as built from "cons nodes", but the progression of elements is still linear/sequential.)

Once we have a type declared, we can easily define a sample tree such as t below, which represents the expression we would normally write as "2+3*5". We can also write a straightforward recursive definition of an evaluation function eval, which returns an integer value for each expression.

data Expr = Lit Int | Add Expr Expr | Mul Expr Expr

eval (Lit k) = k
eval (Add s t) = eval s + eval t
eval (Mul s t) = eval s * eval t

t = Add (Lit 2) (Mul (Lit 3) (Lit 5))

Notes

• the syntax of data type declarations can be a little confusing because the names of both types (such as Expr or Int and the names of value constructors (such as Lit and Add are spelled with an initial capital letter; the trick is to remember that the first name in each clause is the constructor, whereas the remaining ones are types (namely the argument types of that constructor)
• remember also that a data type declaration introduces both the declared type and all of its value constructors into the program namespace at once