Understanding monad transformers (5): add a few good reads

In the first, second, third and fourth post of this series I describe a test case (a function evaluator) and a method to tackle its implementation by writing a complex monad in plain Haskell, built as a pile of transformers. All this from the ground up, without importing any library (except basic stuff like Data.Map and alike) and following the lines described in a presentation by Henrik Nilsson.

All code is available in GitHub, fully covered by tests.

The implementation we’ve come to so far, is able to:

  • trap errors, returning Nothing in all cases of impossible evaluation (transformer ET)
  • manage a state, incrementing an integer value each time the evaluator is called recursively (transformer ST)
  • write a log of all steps encountered during the evaluation (transformer WT)

The evaluation function

eval4d :: Env -> Exp -> ET (WT [String] (ST Int I)) Value

starts its evaluation by closing on an environment (type Env), a map that keeps the value of all the parameters encountered and evaluated so far.

The next step is to have the environment implicitly carried along in the computation; it would be provided as a parameter during the preparation of the evaluation and made available during the run to all the steps that request it. This is a behaviour that suits perfectly a reader monad. There are a few analogies with the purpose and utilisation of the state monad, though:

  • both the state and the reader monad are functions
  • in both cases the evaluation computation is lazy; in the case of `Reader` it executes only when an Env is actually fed by the runner function

The reader monad is much simpler than state. However, its Env parameter is meant to be read-only(**), whereas what a state monad handles is by all means mutable.

(**) well, that’s not entirely accurate, as you can read in about two paragraphs.

Teaching a monad to learn something by heart

In order to give any monad m the capability to carry implicitly a parameter of type r through each step of its own computation we have to follow the example of the reader monad and let m become part of a function of r.

The type that expresses this transformation is called ReaderT in mtl, whereas we will call it RT to avoid name clashes with any other library or package:

newtype RT r m a = RT (r -> m a)
  deriving instance Show (r -> m a) => Show (RT r m a)
  deriving instance Eq (r -> m a) => Eq (RT r m a)

The monad instance that results by adding parameter handling to m is the following:

instance (Monad m) => Monad (RT r m) where
    return x = RT $ \_ -> return x
    rtrma >>= fartrmb = RT $ \r -> do a <- unRT rtrma r
                                      unRT (fartrmb a) r

On Github you may find also the corresponding functor and applicative instance definitions, along with the unwrapper and the runner, as Nilsson does not want us to use the pesky Haskell record syntax.

Giving RT all the traits it deserves

The list of typeclasses that our reader transformer RT may want to implement is the following:

  • MonadTransformer: gotta implement lift
  • R (MonadReader for mtl): this requires implementing an ask and a local methods

Method ask extracts the famous hidden parameter from the monad. In other words, it’s either:

do env <- ask


ask >>= (\env -> {...})

Method local is able to modify temporarily the precious parameter, albeit within the scope of a single do-expression: you will see it at work inside the evaluation rule for the function application case.

The implementations of lift, ask and local are to be found on GitHub.

RT could also become itself an error handler, a state handler and a writer by implementing a bunch of different methods. On their own turn, ET, WT and ST may become readers. This way we wouldn’t have to lift anything in our evaluation functions. But we have decided that our monad transformers will not mix each other’s traits.

Starting simple – Composition of ErrorT and ReaderT

The first application is a three-layer monad pile comprising Identity, ErrorT and ReaderT. This application has been done in two different ways:

Let’s discuss in depth the first case; the monad that handles errors and implicit environment param has type (please follow carefully the passages):

RT Env (ET I) Value
   = RT (Env -> ET I Value) -- definition of RT m a
   = RT (Env -> ET I (Maybe Value)) -- definition of ET m a

The evaluation function must therefore have type:

Exp -> RT Env (ET I) Value

and it will have to be run by a function that closes on an Env and returns a Maybe Value. On GitHub it is called runEval5:

runEval5 :: Env -> RT Env (ET I) Value -> Maybe Value
runEval5 env rtenvetimaybea = unI $ unET $ unRT rtenvetimaybea env

Alike state, the runner requires an explicit initial environment at the beginning of its run.

The evaluation function eval5 that composes RT and ET is the following.

eval5 :: Exp -> RT Env (ET I) Value
  eval5 (Lit i) = return $ IntVal i
  eval5 (Var name) = do env <- ask
                        case (Map.lookup name env) of
                          Just val -> return val
                          Nothing -> lift eFail
  eval5 (Plus e1 e2) = do v1 <- eval5 e1
                          v2 <- eval5 e2
                          case (v1,v2) of
                            (IntVal i1, IntVal i2) -> return $ IntVal $ i1 + i2
                            _ -> lift eFail
  eval5 (Lambda argname body) = do env <- ask
                                   return $ FunVal argname body env
  eval5 (App lambda exp) =
        do val <- eval5 exp
           funval <- eval5 lambda
           case funval of
             FunVal argname body env' -> 
                  do local (const $ Map.insert argname val env') (eval5 body)
             _ -> lift eFail

You have notified that the function runs at the RT level, therefore the error handler action eFail must be lifted using ET‘s lift, whereas ask and local must not.

Here you may admire the function at work in several tests.

Inverting RT and ET

The type is now

ET (RT Env  I) Value
   = ET (RT Env I) (Maybe Value) -- definition of ET m a
   = ET (RT (Env -> I (Maybe Value))) -- definition of ET m a

and it leads to a slightly different evaluation function, which is presented along with a whole suits of tests.

Getting complex – Adding StateT to ErrorT and ReaderT

The next logical step is a four-layer monad pile comprising Identity, ErrorT, StateT and ReaderT.

We still keep ReaderT at the outer layer of the onion and StateT right on top of Identity at the core; the monad that handles errors, manages state and hides environments has type (please follow carefully the passages):

RT Env (ET (ST Int I)) Value
   = RT (Env -> ET (ST Int I) Value)
   = RT (Env -> ET (ST Int I) (Maybe Value))
   = RT (Env -> ET (ST (Int -> I (Maybe Value, Int))))

This type is called eval5c on GitHub.
The evaluation function must therefore have type:

Env -> Int -> RT Env (ET (ST Int I)) Value

and it will have to be run by a function that (after providing an initial env an initial state, and running the state-enabled mechanism) returns a couple (Maybe Value, Int). On Github it is called runEval5c.

The evaluation function eval5c that composes ET, ST and RT is presented on Github. Inside it, the actions related to the state monad have to be lifted twice, while those related to the reader monad need only one pull-up.

Here you may admire the function at work in several tests.

The whole enchilada: ET, ST, WT and RT

The type that encompasses all four monad transformers seen so far is quite a mouthful:

RT Env (ET (WT [String] (ST Int I))) Value
  = RT (Env -> ET (WT [String] (ST Int I)) Value) -- RT r m a
  = RT (Env -> ET (WT [String] (ST Int I)) (Maybe Value)) -- ET m a
  = RT (Env -> ET (ST (Int -> I ((Maybe Value, [String]), Int)))) -- ST s m a

This type is called eval5d on GitHub.

On GitHub you’ll find also all the relevant code:

Time to list, now

The next post will illustrate the usage of one more monad transformers that will change our types into a list monad that evaluates n expressions without a single trace of a loop inside the code



2 thoughts on “Understanding monad transformers (5): add a few good reads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s