Algebraic Expression Languages   [4]

Abstracting to a fold over trees

Once we have abstracted out type parameters from the definition of the expression type, it also makes sense to abstract out the recursive structure of the definition of the eval function. The reason is that if we are going to take any real advantage of the possibilities offered by the type abstraction, we are going to end up writing a lot of recursive functions that look essentially like eval, and thus we can save ourselves a lot of tedium and win some conceptual ground by abstracting out parameters to the definition of the recursive function in a way which parallels what we did with the type.

Now the abstract recursive function (traditionally called fold, as in the list case) can be used to define eval as a very simple application involving the identity function (id in Haskell) to handle the literals and a simple semantic function on operators to handle the binary operator case.

data Expr a b = Lit a | Bop b (Expr a b) (Expr a b)




data AOp = Add | Mul




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

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

> eval t
17

data Expr a b = Lit a | Bop b (Expr a b) (Expr a b)

fold f g (Lit k)     = f k
fold f g (Bop o l r) = g o (fold f g l) (fold f g r)

data AOp = Add | Mul

sem Add = (+)
sem Mul = (*)

eval = fold id sem



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

> eval t
17

Notes

• NOTE