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 Double
s 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.