Haskell, simple evaluator of expressions with monad Reader

Question

I did write some working evaluator of expressions. However, sometimes I get exception:

*** Exception: Maybe.fromJust: Nothing

I know from what it is. However, I can't really solve it. My aim is return in such case Nothing.

Could you help me with it?

type Var = String

data Exp = EInt Int
     | EOp  Op Exp Exp
     | EVar Var
     | ELet Var Exp Exp  -- let var = e1 in e2

data Op = OpAdd | OpMul | OpSub

evalExpM :: Exp -> Reader (Map.Map String Int) (Maybe Int)
evalExpM (EInt n) = return $ Just n
evalExpM (EVar var) = ask >>= (\x -> return ( Map.lookup var x))
evalExpM (EOp OpAdd e1 e2) = ask >>= (\x -> return (Just ((fromJust (runReader (evalExpM e1) x)) + (fromJust (runReader (evalExpM e2) x )))))

evalExpM (EOp OpMul e1 e2) = ask >>= (\x -> return (Just ((fromJust (runReader (evalExpM e1) x)) * (fromJust (runReader (evalExpM e2) x )))))

evalExpM (EOp OpSub e1 e2) = ask >>= (\x -> return (Just ((fromJust (runReader (evalExpM e1) x)) - (fromJust (runReader (evalExpM e2) x )))))

evalExpM (ELet var e1 e2) = ask >>= (\x -> (local (Map.insert var (fromJust (runReader (evalExpM e1) x))) (evalExpM e2)) >>= (\y -> return y))

evalExp :: Exp -> Int
evalExp exp = fromJust $ runReader (evalExpM exp) Map.empty

Answer 1

what you intend is to use the Monad Maybe, which automatically passes the Nothing down so that you do not need to handle that manually.

so, you could use the type (ReaderT r Maybe)(a) instead of (Reader r)(Maybe a).

but i guess you eventually want to simplify this to r -> Maybe a.

---

anyway, you are using Monad Reader r which is only a fancy way of supplying a parameter. because r->a is only syntactic sugar for (->) r a and (->) r is already a Reader Monad, you can use that instead: you could even replace ask with id.

you probably do not want to use the silly ask function all the time, so you could use reader to simply lift the function.

evalExpM :: Exp -> Reader (Map.Map String Int) (Maybe Int)
evalExpM (EVar var) = ask >>= (\x -> lift ( Map.lookup var x))
evalExpM (EVar var) = reader $ \x -> Map.lookup var x
evalExpM (EVar var) = reader $ Map.lookup var

it is more convenient to use Reader (or ReaderT) only when you want to automatically pass the param to inner functions. but even then you can just use the Monad (->) r or simply pass a parameter. you get a better feeling for this if you always use the Monad (->) r and id instead of Reader r and ask. for ReaderT on the other hand, you will see its need when you have to pass one param to most functions you use in do notation.

evalExp :: Exp -> Map.Map String Int -> Maybe Int

evalExp (EOp OpSub e1 e2) = ask >>= (\x -> return (Just ((fromJust ({-runReader-} (evalExp e1) x)) - (fromJust ({-runReader-} (evalExp e2) x )))))

evalExp (EOp OpSub e1 e2) = do -- Monad ((->) (Map.Map String Int))
  x <- id -- hehe, same as ask
  return (Just ((fromJust ({-runReader-} (evalExp e1) x)) - (fromJust ({-runReader-} (evalExp e2) x ))))

evalExp (EOp OpSub e1 e2) x = -- directly with param x
  (Just ((fromJust ((evalExp e1) x)) - (fromJust ((evalExp e2) x ))))

evalExp (EOp OpSub e1 e2) x = do -- Monad (Maybe)
  let a = fromJust ((evalExp e1) x)
  let b = fromJust ((evalExp e2) x)
  Just $ a - b

evalExp (EOp OpSub e1 e2) x = do -- Monad (Maybe)
  a <- return $ fromJust ((evalExp e1) x)
  b <- return $ fromJust ((evalExp e2) x)
  Just $ a - b

-- and without that bug:
evalExp (EOp OpSub e1 e2) x = do -- because return=Just
  a <- evalExp e1 x
  b <- evalExp e2 x
  return $ a - b

evalExp (EOp OpSub e1 e2) = runReaderT $ do -- Monad (ReaderT (Map...) Maybe)
  a <- ReaderT $ evalExp e1
  b <- ReaderT $ evalExp e2 -- this is a nice example to use ReaderT
  return $ a - b

-- this is ugly unless we need that param wrapped quite often:
evalExpM :: Exp -> ReaderT (Map.Map String Int) Maybe Int
evalExpM exp = ReaderT $ evalExp exp

Answer 2

Firstly, the way to work with monadic computations is not to "run" the computation every time you encounter a value wrapped in the monad (in this case Reader ..). You should be using the >>= operator. Furthermore, you are trying to combine two monadic effects: Reader and Maybe. The "standard" way to do this is with a monad transformer, but luckily for you Reader (or more precisely ReaderT) is itself a monad transformer.

Furthermore, you would benefit from some abstraction, i.e. :

import Control.Monad.Reader 
import qualified Data.Map as M 

type Env = M.Map String Int 

type EvalM = ReaderT (M.Map String Int) Maybe

lookupEnv :: String -> EvalM Int 
lookupEnv x = ask >>= lift . M.lookup x

withBind :: String -> Int -> EvalM a -> EvalM a 
withBind x v = local (M.insert x v) 

These functions define an interface to working with environments in which lookup can fail. You should write these functions once as opposed to inlining their definitions when you need them. Now the base cases of your function are trivial:

evalExpM :: Exp -> EvalM Int 
evalExpM (EInt n) = return n 
evalExpM (EVar v) = lookupEnv v 

Many people (including probably myself) would use applicative operators for the recursive cases, but you can avoid the soup of symbols:

evalExpM (EOp op e1 e2) = liftM2 
  (case op of 
    OpAdd -> (+) 
    OpMul -> (-) 
    OpSub -> (-)
  ) (evalExpM e1) (evalExpM e2) 
evalExpM (ELet var e1 e2) = evalExpM e1 >>= \e -> withBind var e $ evalExpM e2

Running it is the same as before - just change runReader to runReaderT - but now you only ever run a computation when you are really done with the context.

evalExp :: Exp -> Int
evalExp e = maybe (error "evalExp") id $ runReaderT (evalExpM e) M.empty