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

I would recommend using Map from Data.Map instead. You could implement it something like

import Data.Map (Map)
import qualified Data.Map as M  -- A lot of conflicts with Prelude
-- Used to map operations through Maybe
import Control.Monad (liftM2)

data Expr
    = Var Char
    | Lit Int
    | Add Expr Expr
    | Sub Expr Expr
    | Mul Expr Expr
    deriving (Eq, Show, Read)

type Assignment = Map Char Int

eval :: Expr -> Assignment -> Maybe Int
eval (Lit x) _      = Just x
eval (Add x y) vars = liftM2 (+) (eval x vars) (eval y vars)
eval (Sub x y) vars = liftM2 (-) (eval x vars) (eval y vars)
eval (Mul x y) vars = liftM2 (*) (eval x vars) (eval y vars)
eval (Var x)   vars = M.lookup x vars

But this looks clunky, and we'd have to keep using liftM2 op every time we added an operation. Let's clean it up a bit with some helpers

(|+|), (|-|), (|*|) :: (Monad m, Num a) => m a -> m a -> m a
(|+|) = liftM2 (+)
(|-|) = liftM2 (-)
(|*|) = liftM2 (*)
infixl 6 |+|, |-|
infixl 7 |*|

eval :: Expr -> Assignment -> Maybe Int
eval (Lit x) _      = return x  -- Use generic return instead of explicit Just
eval (Add x y) vars = eval x vars |+| eval y vars
eval (Sub x y) vars = eval x vars |-| eval y vars
eval (Mul x y) vars = eval x vars |*| eval y vars
eval (Var x)   vars = M.lookup x vars

That's a better, but we still have to pass around the vars everywhere, this is ugly to me. Instead, we can use the ReaderT monad from the mtl package. The ReaderT monad (and the non-transformer Reader) is a very simple monad, it exposes a function ask that returns the value you pass in when it's run, where all you can do is "read" this value, and is usually used for running an application with static configuration. In this case, our "config" is an Assignment.

This is where the liftM2 operators really come in handy

-- This is a long type signature, let's make an alias
type ExprM a = ReaderT Assignment Maybe a

-- Eval still has the same signature
eval :: Expr -> Assignment -> Maybe Int
eval expr vars = runReaderT (evalM expr) vars

-- evalM is essentially our old eval function
evalM :: Expr -> ExprM Int
evalM (Lit x)   = return x
evalM (Add x y) = evalM x |+| evalM y
evalM (Sub x y) = evalM x |-| evalM y
evalM (Mul x y) = evalM x |*| evalM y
evalM (Var x)   = do
    vars <- ask  -- Get the static "configuration" that is our list of vars
    lift $ M.lookup x vars
-- or just
-- evalM (Var x) = ask >>= lift . M.lookup x

The only thing that we really changed was that we have to do a bit extra whenever we encounter a Var x, and we removed the vars parameter. I think this makes evalM very elegant, since we only access the Assignment when we need it, and we don't even have to worry about failure, it's completely taken care of by the Monad instance for Maybe. There isn't a single line of error handling logic in this entire algorithm, yet it will gracefully return Nothing if a variable name is not present in the Assignment.

---

Also, consider if later you wanted to switch to Doubles and add division, but you also want to return an error code so you can determine if there was a divide by 0 error or a lookup error. Instead of Maybe Double, you could use Either ErrorCode Double where

data ErrorCode
    = VarUndefinedError
    | DivideByZeroError
    deriving (Eq, Show, Read)

Then you could write this module as

data Expr
    = Var Char
    | Lit Double
    | Add Expr Expr
    | Sub Expr Expr
    | Mul Expr Expr
    | Div Expr Expr
    deriving (Eq, Show, Read)

type Assignment = Map Char Double

data ErrorCode
    = VarUndefinedError
    | DivideByZeroError
    deriving (Eq, Show, Read)

type ExprM a = ReaderT Assignment (Either ErrorCode) a

eval :: Expr -> Assignment -> Either ErrorCode Double
eval expr vars = runReaderT (evalM expr) vars

throw :: ErrorCode -> ExprM a
throw = lift . Left

evalM :: Expr -> ExprM Double
evalM (Lit x)   = return x
evalM (Add x y) = evalM x |+| evalM y
evalM (Sub x y) = evalM x |-| evalM y
evalM (Mul x y) = evalM x |*| evalM y
evalM (Div x y) = do
    x' <- evalM x
    y' <- evalM y
    if y' == 0
        then throw DivideByZeroError
        else return $ x' / y'
evalM (Var x) = do
    vars <- ask
    maybe (throw VarUndefinedError) return $ M.lookup x vars

Now we do have explicit error handling, but it isn't bad, and we've been able to use maybe to avoid explicitly matching on Just and Nothing.

This is a lot more information than you really need to solve this problem, I just wanted to present an alternative solution that uses the monadic properties of Maybe and Either to provide easy error handling and use ReaderT to clean up that noise of passing an Assignment argument around everywhere.

Answer 2

You need to apply your Assignment function to the variable name to get the Int:

eval (Var x) f = f x

This works because f :: Char -> Int and x:: Char, so you can just do f x to get an Int. Pleasingly this will work across a collection of variable names.

Example

ass :: Assignment
ass 'a' = 1
ass 'b' = 2

meaning that

eval ((Add (Var 'a') (Var 'b')) ass
= eval (Var 'a') ass + eval (Var 'b') ass
= ass 'a'            + ass 'b'
= 1 + 2
= 3

Pass the assignment functions through to other calls of eval

You need to keep passing the assignment function around until you get integers:

eval (Add x y) f = eval x f + eval y f

Different order?

If you're allowed to change the types, it seems more logical to me to put the assignment function first and the data second:

eval :: Assignment -> Expr -> Int
eval f (Var x) = f x
eval f (Add x y) = eval f x + eval f y

...but I guess you can think of it as a constant expression with varying variables (feels imperative)rather than a constant set of values across a range of expressions (feels like referential transparency).

Answer 3

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.