Understanding monad transformers: mastery is in the details

The trouble with learning monad transformers

You’ve read about a bunch of monads and that each one of them has a particular role to fulfill, then you start using them and soon realize that one monad at a time is just a one-off trick.

Enter monad transformers. Many different effects combined, that must be the way to go. You read the analogy with the onion and its layers: it’s fascinating, there are trivial examples around that all make a lot of sense. But putting the onion at work on a ‘real’ case of yours is another story. How can you make then knowledge stick?

This is the first of a series of posts that illustrate the beautiful details of monad transformers in Haskell (and possibly in JavaScript and Khepri, in the next future). They require a minimal familiarity with Haskell syntax, but just that.

All the code here runs in GHC and it is to be found on GitHub, fully equipped with tests.

Standard Haskell transformer libraries make you sloppy and disappointed

Hoping to understand, you turn to the standard Haskell libraries, like mtl, as most professional books/wikis on the subject will tell you to do. But also this does not really help understand what’s going on. Every layer of the onion is a MonadRead, a MonadState, a MonadWrite and a MonadCont at the same time; you can use almost any canonical function at every level.

You don’t have to bother taking note at which layer you are and how many levels a certain operation has got to be lifted, that’s great! So you start cruisin’, until you get bitten in the butt by some obscure, extremely long error message from the compiler.

This happened to me plentiful while studying a couple of papers, notably Monad Transformers Step by Step, by Martin Grabmüller. This one presents a monad transformer solution to a promisingly not-trivial problem: an expression evaluator.

The test case: an expression evaluator

Grabmüller’s expression evaluator handles five sorts of expressions:

type Name = String -- var name (just a synonym)

-- expressions
data Exp = Lit Integer -- constant
         | Var Name -- var
         | Plus Exp Exp -- addition
{- original paper calls next exp 'Abs' - abstraction -}
         | Lambda Name Exp -- unary lambda expression
         | App Exp Exp -- function application
         deriving (Show)

Evaluation of these expressions yields two sorts of values, function values and integer values. Function values stem from the evaluation of Lambda expressions; integer values from every other case:

-- values
data Value = IntVal Integer -- int
           | FunVal Env Name Exp -- env, argname, body
           deriving (Show)

Evaluation must happen inside an environment that holds the values of the known variables:

type Env = Map Name Value -- dictionary varName:varValue

A few examples of the evaluation process

(Lit 12) evaluates to (IntVal 12)

(Var 'x') requires an Env to be evaluated. More to follow.

(Plus (Lit 1) (Lit 1)) must yield (IntVal 2)

(Lambda 'x' (Plus (Var 'x') (Lit 1))) is function \x -> x + 1

(App (Lambda 'x' (Plus (Var 'x') (Lit 1))) (Lit 4)) corresponds to (\x -> x + 1)(4); it assigns (Lit 4) to (Var 'x') in the Env and, as a whole, it evaluates to (IntVal 5).


A plain, non monadic, error prone evaluator function will have type

Env -> Exp -> Value

That’s to say: closing on an environment, take an expression and yield a value out of it. The following function will do:

eval :: Env -> Exp -> Value
eval env (Lit i) = IntVal i
eval env (Var name) = fromJust $ Map.lookup name env
eval env (Plus e1 e2) = let IntVal i1 = eval env e1
                            IntVal i2 = eval env e2
                        in IntVal (i1 + i2)
eval env (Lambda argname body) = FunVal argname body env
eval env (App lambda expr) = let FunVal argname body env' = eval env lambda
                                 val = eval env expr
                             in eval (Map.insert argname val env') body

If you want to see it in action, clone the transformerz project and run TestNilsson_01.hs in GHC. Watch out, the function is called there eval0.

This function will crash at the whim of any malformed expression or incomplete environment. And even when it succeeds, we will never be able to get any grip over the process. We’d like to know the cause of a possible failure, we’d like to know which sequence of steps were undertaken during a successful run, how efficiently the environment was managed. We’d like to process a list of expressions with the same code that processes a single one, and so on. In short, we’d like a bunch of monads, one at a time, to take orderly care of the various facets of this matter.

Grabmüller’s paper presents indeed a monadic evaluator for these expressions, involving ErrorT, StateT, ReaderT and WriterT. Alas, the paper uses mtl and jumps over crucial stuff from time to time. Unless you follow the paper by heart and simply verify what it says (doh…), every little detour you try is doomed to fail.

Reality is: one has to be bloody precise with those onion layers and their interplay. The way I am, I looked around to get to the essence of the matter once and for all.

The way ahead is putting two papers together

There is a rather cryptic 2006 presentation by Henrik Nilsson: AFP Lecture 3 – Monad Transformers. It gives a complete fly over the Error, State, Continuation and Concurrency transformers in 38 slides. It provides simple implementations for all of them: they’re not bulletproof implementations like you’ll find in mtl, but what the heck! here you can see what’s really going on.

Where the paper falls short is in providing too few sample exercises (unbelievably short and complex – I cannot imagine anyone in the audience really understanding their solutions after having heard for the first time about transformers during the presentation itself) and covering too few transformers (what about ListT, ReaderT and WriterT?).

But several points make that presentation valuable, I’d say rather unique:

  • its implementations are bare-bone, but complete in all necessary details
  • it shows various combinations of transformers
  • coverage of each transformer is consistently thorough through all the slides

In other words, what the presentation describes looks and feels like a box of Lego blocks. So what I decided was: let’s implement Grabmüller’s expression evaluator using Nilsson’s transformers, and design ListT, ReaderT and WriterT in the process.

Nilsson’s method in a nutshell: no record syntax

What makes Nilsson’s code enjoyable to me is the absence of those pesky runState‘s, runWriter‘s, runCont‘s wherever you less expect them. For every monad transformer you got to implement two functions that operate on the current monad instance:

  • one to extract its value out of the context (i.e. to peel and discard one layer of the onion without performing the related monadic effect)
  • one to run it, resolving and making its inner types explicit

In some cases these are the same thing, but most of the time, they’re different. Let’s take the example of StateT, which Nilsson calls ST to avoid any possible clash with standard libraries. You need an

unST :: (Monad m) => ST s m a -> (s -> m a)

and a

runST :: (Monad m) => ST s m a -> (s -> m (a,s))

For some obscure, arcane reason Henrik Nilsson decided to invert the names. In his presentation runners begin by un and onion peelers begin by run. This kills me, and made eventually my code ridden with reminders This is NOT a runner!.

Nevertheless, I got to the end. My monad transformerz are now fully worked out in Haskell –well, to be honest I’ve got still to polish ListT. They’re worked out up to the last beautiful detail (if you wanna define a monad without cheating, you’ll have to show GHC its functor and its applicative first…) and I am ready to move on to Khepri and JavaScript.

But in this record, we are just at the start of the journey: in the next post I will present the definition and application of the first monad transformer: ET (that’s MaybeT in mtl).

Advertisements

5 thoughts on “Understanding monad transformers: mastery is in the details

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