[Haskell-cafe] implementing recursive let

Derek Elkins derek.a.elkins at gmail.com
Tue Nov 24 22:39:52 EST 2009

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 (
    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

More information about the Haskell-Cafe mailing list