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 implementlift
W
(MonadWriter
for mtl): this requires implementing atell
, alisten
and apass
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”