How to evaluate expressions in Haskell

Question

I understand how to create and evaluate a simple data-type Expr. For example like this:

data Expr = Lit Int | Add Expr Expr | Sub Expr Expr | [...]

eval :: Expr -> Int
eval (Lit x) = x
eval (Add x y) = eval x + eval y
eval (Sub x y) = eval x - eval y

So here is my question: How can I add Variables to this Expr type, which should be evaluated for its assigned value? It should look like this:

data Expr = Var Char | Lit Int | Add Expr Expr [...]
type Assignment = Char -> Int

eval :: Expr -> Assignment -> Int

How do I have to do my eval function now for (Var Char) and (Add Expr Expr)? I think I figured out the easiest, how to do it for Lit already.

eval (Lit x) _ = x

For (Var Char) I tried a lot, but I cant get an Int out of an Assignment.. Thought It would work like this:

eval (Var x) (varname number) = number

Answer 1

Well if you model your enviroment as

type Env = Char -> Int

Then all you have is

eval (Var c) env = env c

But this isn't really "correct". For one, what happens with unbound variables? So perhaps a more accurate type is

type Env = Char -> Maybe Int
emptyEnv = const Nothing

And now we can see whether a variable is unbound

eval (Var c) env = maybe handleUnboundCase id (env c)

And now we can use handleUnboundCase to do something like assign a default value, blow up the program, or make monkeys climb out of your ears.

The final question to ask is "how are variables bound?". If you where looking for a "let" statement like we have in Haskell, then we can use a trick known as HOAS (higher order abstract syntax).

data Exp = ... | Let Exp (Exp -> Exp)

The HOAS bit is that (Exp -> Exp). Essentially we use Haskell's name-binding to implement our languages. Now to evaluate a let expression we do

eval (Let val body) = body val

This let's us dodge Var and Assignment by relying on Haskell to resolve the variable name.

An example let statement in this style might be

 Let 1 $ \x -> x + x
 -- let x = 1 in x + x

The biggest downside here is that modelling mutability is a royal pain, but this was already the case when relying on the Assignment type vs a concrete map.