In the first, second and third 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, is able to:

- trap errors, returning
`Nothing`

in all cases of impossible evaluation - manage a state, incrementing an integer value each time the evaluator is called recursively

The next step is to add some logging capability to the process, a thing that suits perfectly a **writer monad**. We will push string messages inside an array and get at the end a complete report of all the evaluation steps. I agree that we could entrust this task to the state monad of the previous post and manage logged strings along with the counter inside a suitable `state :: (Int, [String])`

, but using a state monad for a pure writing operation is certainly overkill.

In the next paragraphs of this post I will present a monad pile Error + Writer, which is very much simpler than when using State and does anyhow a very good job. On the other hand, a transformers library without State won’t get very far, so I felt I had to present that one first.

## Teaching a monad to write on a board

We know from our deep studies in monadology that a Writer wants a monoid to write into. Gotta be a monoid because the monad will need associativity to glue together all its writings, and what each monoid does for a living is just carry on a specific, single associative binary operation.

The type that expresses this transformation is called `WriterT`

in mtl; following the previous two examples, I decided to call it `WT`

:

```
newtype WT w m a = WT (m (a, w))
deriving instance Show (m (a, w)) => Show (WT w m a)
deriving instance Eq (m (a, w)) => Eq (WT w m a)
```

The monoid’s name is then `w`

. This type constructor is the one usually found in the literature, but it is not the only one thinkable. As an experiment, I tried also a different type constructor

`newtype WT w m a = WT (m a, w)`

and I present in the next paragraph what came out of that experiment.

The monad instance that results by adding writer capabilities to a monad `m`

is the following:

```
instance (Monoid w, Monad m) => Monad (WT w m) where
return x = WT (return (x, mempty))
wtmcaw >>= fawtwmb = WT $ do (a, w1) <- unWT wtmcaw
(b, w2) <- unWT (fawtwmb a)
return (b, mappend w1 w2)
```

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.

The idea here is to carry a write-only *list* along with the computation and have the evaluator monad insert there *strings* at will, on top of all the rest that it is already able to do. In our case the monoid will be therefore `[String]`

and at the end the evaluation log will be an ordered bunch of strings. We could have used also a plain `String`

as monoid, and in that case the final log would have been a long string created by concat-ing the various monadic writings.

### Starting simple – Composition of ErrorT and WriterT

The first application is a three-layer monad pile comprising Identity, ErrorT and WriterT.

Assuming to keep ErrorT at the outer layer of the onion, the monad that handles errors and logs messages has type (please follow carefully the passages):

```
ET (WT [String] I) Value
= ET (WT [String] I) (Maybe Value) -- definition of ET m a
= ET (WT I(Maybe Value, [String])) -- definition of WT w m a
```

The evaluation function must therefore have type:

Env -> Exp -> ET (WT [String] I) Value

and it will have to be run by a function that returns a couple `(Maybe Value, [String])`

. On GitHub it is called `runEval4c`

:

```
runEval4c :: ET (WT [String] I) Value -> (Maybe Value, [String])
runEval4c etwticmaybevalstrarra =
unI $ unWT $ unET etwticmaybevalstrarra
```

As it is customary with writer, we don’t have to provide the empty log at the beginning of the run, because writer’s monoid knows how to provide a `mempty`

one (pun intended) at the first invocation. This is very much unlike state, that requires an explicit initial state at the beginning of its run.

The evaluation function `eval4c`

that composes ET and WT is the following. At each step the canonical writer monad operation `tell`

appends a one-element string array to the log.

```
eval4c :: Env -> Exp -> ET (WT [String] I) Value
eval4c env (Lit i) = do lift $ tell ["literal"]
return $ IntVal i
eval4c env (Var name) =
do lift $ tell ["lookup " ++ name]
case (Map.lookup name env) of
Just val -> do lift $ tell ["lookup ok"]
return $ val
Nothing -> do lift $ tell ["lookup ko"]
eFail
eval4c env (Plus e1 e2) =
do lift $ tell ["sum"]
v1 <- eval4c env e1
v2 <- eval4c env e2
case (v1, v2) of
(IntVal i1, IntVal i2) -> do lift $ tell ["sum ok"]
return $ IntVal (i1 + i2)
_ -> do lift $ tell ["sum ko"]
eFail
eval4c env (Lambda argname body) =
do lift $ tell ["lambda"]
return $ FunVal argname body env
eval4c env (App lambda exp) =
do lift $ tell ["application"]
val <- eval4c env exp
funval <- eval4c env lambda
case funval of
FunVal argname body env'
-> do lift $ tell ["application ok"]
eval4c (Map.insert argname val env') body
_ -> do lift $ tell ["application ko"]
eFail
```

It’s important to observe that **the function runs at the ET level**, therefore the writer’s action

`tell`

must be lifted using `ET`

‘s `lift`

, whereas `eFail`

**must not**.

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

### Giving `WT`

all the traits it deserves

The list of typeclasses that our writer transformer `WT`

may want to implement is the following:

`MonadTransformer`

: gotta implement`lift`

`W`

(`MonadWriter`

for mtl): this requires implementing a`tell`

, a`listen`

and a`pass`

methods

The implementations of `lift`

, `tell`

and `listen`

are to be found on GitHub; `tell`

writes directly to the monoid, whereas `listen`

invokes an action and writes the output from *that* action to the monoid (kinda confusing, if you’d ask me). `pass`

is actually not implemented.

`WT`

could also become itself an error handler and a state handler by implementing a bunch of different methods. On their own turn, `ET`

and `ST`

may become writers. This way we wouldn’t have to `lift tell`

all over the place. But we have decided that our monad transformers will not mix each other’s traits.

### Getting complex – Composition of ErrorT, WriterT and StateT

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

We still keep ErrorT 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 logs messages has type (please follow carefully the passages):

```
ET (WT [String] (ST Int I)) Value
= ET (WT [String] (ST Int I)) (Maybe Value) -- def of ET m a
= ET (WT (ST Int I)(Maybe Value, [String])) -- def of WT w m a
= ET (WT (ST (Int -> I((Maybe Value, [String]), Int)))) -- def of ST s m a
```

The name of this type is shortened to Eval4d on GitHub.

The evaluation function must therefore have type:

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

and it will have to be run by a function that (after providing an initial state and running the state-enabled mechanism) returns a couple of couples `((Maybe Value, [String]), Int)`

. On Github it is called `runEval4d`

:

```
runEval4d :: Int -> ET (WT [String] (ST Int I)) Value
-> ((Maybe Value, [String]), Int)
runEval4d s etwtetc =
unI $ unST (unWT (unET etwtetc)) s
```

The evaluation function `eval4d`

that composes ET, ST and WT is presented on Github. At each step, while State `tick`

s, the canonical writer monad operation `tell`

appends a one-element string array to the log.

It’s important to observe that **the function runs at the ET level**, therefore the writer’s action

`tell`

must be lifted using `ET`

‘s `lift`

, whereas `eFail`

**must not**. Poor

`tick`

runs in the state monad, two layers down, and it has to get lifted twice, first by writer’s `lift`

and then by error’s.Here you may admire the function at work in several tests.

## Let’s try a different type constructor for the writer transformer!

One of the most interesting experiences in this whole project has been my attempt to redefine the type constructor for `WT`

.

Instead of the widely used

`newtype WT w m a = WT (m (a, w))`

I tried

`newtype WT w m a = WT (m a, w)`

All started smoothly but soon I got to implement the monad instance constructor. There I got a whole bunch of compiler errors which I couldn’t manage to overcome. At the end I threw the towel and asked assistance on Stack Overflow. To my great surprise, I was told that my definition of type constructor is not compatible with the monad laws.

Nice try but no cigar, this time…

### Time to read and list, now

The next posts will illustrate the usage of more monad transformers that will change our types into:

- a
**reader monad**that carries implicitly the evaluation environment and serves it to any computation step that may need to consult it - a
**list monad**that evaluates n expressions without a single trace of a loop inside the code

## 2 thoughts on “Understanding monad transformers (4): put in some creative writing”