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`

or

`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

*TO BE CONTINUED*

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