Combining State monad with Either-style error propagation

Question

I am fairly new to Haskell. I am trying to combine the State monad with error propagation by treating Either as a monad. I would like to recurse over an abstract syntax tree (for example, for writing an interpreter over statements and expressions) in such a way that I need not explicitly handle state nor errors. I am under the impression that the simplest way to do this is using an ExceptT monad transformer. Here is my example code which compiles:

import Control.Monad.Except
import Control.Monad.State
import qualified Data.Map.Strict as M

-- simple expression language supporting crude let bindings
data Exp = Lit Int | Var String
         | Add (Exp, Exp) | Let (String, Exp, Exp) deriving Show

okExp =  -- let x = 2 in let y = x + 3 in x + y -- evaluate to 7
    Let ("x", Lit 2,
             Let ("y", Add (Var "x", Lit 3),
                      Add (Var "x", Var "y")))
badExp = Var "x"  -- error: x is not defined

type St = M.Map String Int
initialState :: St
initialState = M.empty

type EvalMonad = ExceptT String (State St)

evalExp :: Exp -> EvalMonad Int
evalExp (Lit n) = return n
evalExp (Var v) = do
    mp <- lift get
    case M.lookup v mp of
        Just i -> return i
        Nothing -> throwError (v ++ " not found")
evalExp (Add (a, b)) = do
    x <- evalExp a
    y <- evalExp b
    return (x + y)

I wish to run evalExp on simple examples (okExp, badExp, for instance). I am unsure of three things:

1. How do I get the initial state into the calculation?
2. How do I use runExceptT to extract the result?
3. (Much more general): Is this the "right" way to solve this problem?

Larcher

I think I would data Exp = ... | Add Exp Exp | Let String Exp Exp. No sense adding an additional tuple constructor indirection to every complex expression. – Doyenne

Thanks, I had been wondering about why tuples are not normally used in this content since I would not normally plan on using currying with them, but that makes a lot of sense. – Larcher

Answer 1

Looks like a great start! Here's a tiny example showing how to use runExceptT and runState together in ghci:

> runState (runExceptT (evalExp (Add (Lit 3, Lit 4)))) initialState
(Right 7,fromList [])
> runState (runExceptT (evalExp (Add (Lit 3, Var "x")))) initialState
(Left "x not found",fromList [])

Doyenne

Excellent, thanks. I assume then, that this kind of pairing seems like the right way to go? – Larcher

@Larcher yes this is very common and idiomatic to define a monad transformer stack to describe the possible side-effects of a language you are interpreting. – Weiman

@Larcher an interesting exercise is to consider what would change if you switched the order of the transformers: StateT St (Except String) – Weiman

@Weiman that is very helpful; and I will try that exercise. Much thanks! – Larcher