WriterT monad transformer

Question

I'm following this tutorial "Monad Transformers Step by Step"

http://www.cs.virginia.edu/~wh5a/personal/Transformers.pdf

and the code in eval5 function from section 2.5

type Name = String

data Exp = Lit Integer
         | Var Name
         | Plus Exp Exp
         | Abs Name Exp
         | App Exp Exp
         deriving (Show)

data Value = IntVal Integer
           | FunVal Env Name Exp
           deriving (Show)         

type Env = Map.Map Name Value   

type Eval5 a = ReaderT Env (ErrorT String 
                           (WriterT [String] (StateT Integer Identity))) a

runEval5 :: Env -> Integer -> Eval5 a -> ((Either String a, [String]), Integer)                       
runEval5 env st ev = 
    runIdentity (runStateT (runWriterT (runErrorT (runReaderT ev env))) st)


eval5 :: Exp -> Eval4 Value
eval5 (Lit i)           = do tick
                             return $ IntVal i

eval5 (Var n)           = do tick 
                             tell [n]
                             env <- ask
                             case Map.lookup n env of 
                                Nothing  -> throwError("unbound variable: " ++ n)
                                Just val -> return val

eval5 (Plus e1 e2)      = do tick
                             e1' <- eval5 e1
                             e2' <- eval5 e2
                             case (e1', e2') of
                                (IntVal i1, IntVal i2) ->
                                    return $ IntVal $ i1 + i2
                                _ -> throwError "type error in Plus"                                

eval5 (Abs n e)         = do tick
                             env <- ask
                             return $ FunVal env n e

eval5 (App e1 e2)       = do tick
                             val1 <- eval5 e1
                             val2 <- eval5 e2
                             case val1 of
                                FunVal env' n body ->
                                    local (const $ Map.insert n val2 env')
                                          $ eval5 body
                                _ -> throwError "type error in App"

fails to compile with the message:

No instance for (MonadWriter [Name] Identity)
  arising from a use of `tell'
Possible fix:
  add an instance declaration for (MonadWriter [Name] Identity)
In a stmt of a 'do' block: tell [n]
In the expression:
  do { tick;
       tell [n];
       env <- ask;
       case Map.lookup n env of {
         Nothing -> throwError ("unbound variable: " ++ n)
         Just val -> return val } }
In an equation for `eval5':
    eval5 (Var n)
      = do { tick;
             tell [n];
             env <- ask;
             .... }

ghc version 7.6.3

Stephen Diehl Stephen Diehl · Accepted Answer · 2014-02-09T00:44:03

Assuming the tick function is the same function mentioned in the paper:

tick :: Eval5 ()
tick = do n <- get
          put (n+1)

There also seems to be some confusion around Eval4 vs Eval5 in your monad transformer. The evaluator seems to be written against Eval4. Here's the fixed source:

import Control.Monad.Reader
import Control.Monad.Writer
import Control.Monad.Error
import Control.Monad.Identity
import Control.Monad.State

import qualified Data.Map as Map

type Name = String

data Exp = Lit Integer
         | Var Name
         | Plus Exp Exp
         | Abs Name Exp
         | App Exp Exp
         deriving (Show)

data Value = IntVal Integer
           | FunVal Env Name Exp
           deriving (Show)

type Env = Map.Map Name Value

type Eval5 a = ReaderT Env (ErrorT String
                           (WriterT [String] (StateT Integer Identity))) a

runEval5 :: Env -> Integer -> Eval5 a -> ((Either String a, [String]), Integer)
runEval5 env st ev =
    runIdentity (runStateT (runWriterT (runErrorT (runReaderT ev env))) st)

tick :: Eval5 ()
tick = do n <- get
          put (n+1)

eval5 :: Exp -> Eval5 Value
eval5 (Lit i) = do
  tick
  return $ IntVal i

eval5 (Var n) = do
  tick
  tell [n]
  env <- ask
  case Map.lookup n env of
     Nothing  -> throwError("unbound variable: " ++ n)
     Just val -> return val

eval5 (Plus e1 e2) = do
  tick
  e1' <- eval5 e1
  e2' <- eval5 e2
  case (e1', e2') of
     (IntVal i1, IntVal i2) ->
         return $ IntVal $ i1 + i2
     _ -> throwError "type error in Plus"

eval5 (Abs n e) = do
  tick
  env <- ask
  return $ FunVal env n e

eval5 (App e1 e2) = do
  tick
  val1 <- eval5 e1
  val2 <- eval5 e2
  case val1 of
     FunVal env' n body ->
         local (const $ Map.insert n val2 env')
               $ eval5 body
     _ -> throwError "type error in App"

On an aside there is a composite monad transformer called RWS ( Reader/Writer/State ) which does exactly what your stack does. Using it can simplify the unrolling code quite a bit.

type EvalRWST a = RWS Env [String] Integer a

runEvalRWS :: Env -> Integer -> EvalRWST a -> (a, Integer, [String])
runEvalRWS env st ev = runRWS ev env st

WriterT monad transformer

1 Answers