Starting with a representation of Boolean formulas, we'll gradually work up to representing more general expressions, then statements, then programs.
Define an algebraic data type Exp
to represent expressions including
these features:
Write a substitution function
subst :: Exp -> Name -> Exp -> Exp
where subst e' x e
is pronounced e'
is substituted for x
in e
.
Write a function eval
that evaluates an expression and produces
a value. The type of eval
should be discussed in class.
Write a simplifier
simplify :: Exp -> Maybe Exp
which, if it can, returns a simpler version of its argument, and
if it cannot, returns Nothing
.
Hint: find a way to reuse eval
and other functions you may
have already written.