Algebraic Expression Languages   [7]

Folding to eliminate enumerated types

The flexibility of the fold will soon have us defining lots of little one- or two-line functions for various tasks. Each of these definitions will need a little function like sem or syn ... but as we define more of these, and especially if we add one or two cases to the definition of the operator symbol types (e.g. AOp or BOp), these short multi-line definitions will become a bit tedious. We can make these definitions much more succinct by using what amounts to a fold for an enumerated type, here called aop.

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

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

aop a m Add = a
aop a m Mul = m

eval = fold id (aop (+) (*))

Notes