The following code works fine for me, so it seems you are missing some details that may help. {-# LANGUAGE RecursiveDo, GeneralizedNewtypeDeriving, TypeSynonymInstances, MultiParamTypeClasses #-} import Control.Monad import Control.Monad.State import Control.Monad.Error import Control.Monad.Writer import Control.Monad.Reader import Control.Monad.Fix import Data.Maybe import qualified Data.Map as M data Expr = Let [(String, Expr)] Expr | Const Int | Var String data Value = Data String | Function (Value -> Eval Value) instance Show Value where show (Data s) = s type Env = M.Map String Value example = Let [("x", Const 1)] (Var "x") eval :: Expr -> Eval Value eval (Const n) = return (Data (show n)) eval (Var x) = gets (fromJust . M.lookup x) eval (Let decls body) = mdo let (names,exprs) = unzip decls updateEnv env = foldr (uncurry M.insert) env $ zip names values (values,result) <- local updateEnv $ liftM2 (,) (mapM eval exprs) (eval body) return result newtype Eval a = Eval { unEval :: ErrorT String (StateT Env (Writer [String])) a } deriving ( Monad, MonadFix, MonadWriter [String], -- for warnings & other messages MonadState Env, MonadError String ) runEval :: Eval Value -> Either String Value runEval = fst . runWriter . flip evalStateT M.empty . runErrorT . unEval evaluate = runEval . eval instance MonadReader Env Eval where ask = get local tr act = do s <- get modify tr r <- act put s return r