Understanding monad transformers (4): put in some creative writing

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 ticks, 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