Haskell/Monad transformers

From Wikibooks, the open-content textbooks collection



[edit] Introduction

Monad transformers are special variants of standard monads that facilitate the combining of monads. For example, ReaderT Env IO a is a computation which can read from some environment of type Env, can do some IO and returns a type a. Their type constructors are parameterized over a monad type constructor, and they produce combined monadic types. In this tutorial, we will assume that you understand the internal mechanics of the monad abstraction, what makes monads "tick". If, for instance, you are not comfortable with the bind operator (>>=), we would recommend that you first read Understanding monads.

[edit] Transformers are cousins

A useful way to look at transformers is as cousins of some base monad. For example, the monad ListT is a cousin of its base monad List. Monad transformers are typically implemented almost exactly the same way that their cousins are, only more complicated because they are trying to thread some inner monad through.

The standard monads of the monad template library all have transformer versions which are defined consistently with their non-transformer versions. However, it is not the case that all monad transformers apply the same transformation. We have seen that the ContT transformer turns continuations of the form (a->r)->r into continuations of the form (a->m r)->m r. The StateT transformer is different. It turns state transformer functions of the form s->(a,s) into state transformer functions of the form s->m (a,s). In general, there is no magic formula to create a transformer version of a monad — the form of each transformer depends on what makes sense in the context of its non-transformer type.

In the table above, most of the transformers FooT differ from their base monad Foo by the wrapping of the result type (right-hand side of the -> for function kinds, or the whole type for non-function types) in the threaded monad (m). The Cont monad has two "results" in its type (it maps functions to values), and so ContT wraps both in the threaded monad. In other words, the commonality between all these transformers is like so, with some abuse of syntax:

[edit] Implementing transformers

The key to understanding how monad transformers work is understanding how they implement the bind (>>=) operator. You'll notice that this implementation very closely resembles that of their standard, non-transformer cousins.

[edit] Transformer type constructors

Type constructors play a fundamental role in Haskell's monad support. Recall that Reader r a is the type of values of type a within a Reader monad with environment of type r. The type constructor Reader r is an instance of the Monad class, and the runReader::Reader r a->r->a function performs a computation in the Reader monad and returns the result of type a.

A transformer version of the Reader monad, called ReaderT, exists which adds a monad type constructor as an addition parameter. ReaderT r m a is the type of values of the combined monad in which Reader is the base monad and m is the inner monad.

ReaderT r m is an instance of the monad class, and the runReaderT::ReaderT r m a->r->m a function performs a computation in the combined monad and returns a result of type m a.

[edit] The Maybe transformer

We begin by defining the data type for the Maybe transformer. Our MaybeT constructor takes a single argument. Since transformers have the same data as their non-transformer cousins, we will use the newtype keyword. We could very well have chosen to use data, but that introduces needless overhead.

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

This might seem a little off-putting at first, but it's actually simpler than it looks. The constructor for MaybeT takes a single argument, of type m (Maybe a). That is all. We use some syntactic sugar so that you can see MaybeT as a record, and access the value of this single argument by calling runMaybeT. One trick to understanding this is to see monad transformers as sandwiches: the bottom slice of the sandwhich is the base monad (in this case, Maybe). The filling is the inner monad, m. And the top slice is the monad transformer MaybeT. The purpose of the runMaybeT function is simply to remove this top slice from the sandwich. What is the type of runMaybeT? It is (MaybeT m a) -> m (Maybe a).

As we mentioned in the beginning of this tutorial, monad transformers are monads too. Here is a partial implementation of the MaybeT monad. To understand this implementation, it really helps to know how its simpler cousin Maybe works. For comparison's sake, we put the two monad implementations side by side

instance Monad Maybe where
 b_v >>= f =
 --
 case b_v of
   Nothing -> Nothing
   Just v -> f v

instance (Monad m) => Monad (MaybeT m) where
 tmb_v >>= f =
 MaybeT $ runMaybeT tmb_v
 >>= \b_v -> case b_v of
   Nothing -> return Nothing
   Just v -> runMaybeT $ f v

You'll notice that the MaybeT implementation looks a lot like the Maybe implementation of bind, with the exception that MaybeT is doing a lot of extra work. This extra work consists of unpacking the two extra layers of monadic sandwich (note the convention topMidBot to reflect the sandwich layers) and packing them up. If you really want to cut into the meat of this, read on. If you think you've understood up to here, why not try the following exercises:

[edit] Dissecting the bind operator

So what's going on here? You can think of this as working in three phases: first we remove the sandwich layer by layer, and then we apply a function to the data, and finally we pack the new value into a new sandwich

Unpacking the sandwich: Let us ignore the MaybeT constructor for now, but note that everything that's going on after the $ is happening within the m monad and not the MaybeT monad!

1. The first step is to remove the top slice of the sandwich by calling runMaybeT topMidBotV
2. We use the bind operator (>>=) to remove the second layer of the sandwich -- remember that we are working in the confines of the m monad.
3. Finally, we use case and pattern matching to strip off the bottom layer of the sandwich, leaving behind the actual data with which we are working

Packing the sandwich back up:

• If the bottom layer was Nothing, we simply return Nothing (which gives us a 2-layer sandwich). This value then goes to the MaybeT constructor at the very beginning of this function, which adds the top layer and gives us back a full sandwich.
• If the bottom layer was Just v (note how we have pattern-matched that bottom slice of monad off): we apply the function f to it. But now we have a problem: applying f to v gives a full three-layer sandwich, which would be absolutely perfect except for the fact that we're now going to apply the MaybeT constructor to it and get a type clash! So how do we avoid this? By first running runMaybeT to peel the top slice off so that the MaybeT constructor is happy when you try to add it back on.

[edit] The List transformer

Just as with the Maybe transformer, we create a datatype with a constructor that takes one argument:

newtype ListT m a = ListT { runListT :: m [a] }

The implementation of the ListT monad is also strikingly similar to its cousin, the List monad. We do exactly the same things for List, but with a little extra support to operate within the inner monad m, and to pack and unpack the monadic sandwich ListT - m - List.

instance Monad [] where
 b_v >>= f =
 --
 let x = map f b_v
 in concat x

instance (Monad m) => Monad (ListT m) where
 tmb_v >>= f =
 ListT $ runListT tmb_v
 >>= \b_v -> mapM (runListT . f) b_v
 >>= \x -> return (concat x)

[edit] Lifting

FIXME: insert introduction

[edit] liftM

We begin with a notion which, strictly speaking, isn't about monad transformers. One small and surprisingly useful function in the standard library is liftM, which as the API states, is meant for lifting non-monadic functions into monadic ones. Let's take a look at that type:

liftM :: Monad m => (a1 -> r) -> m a1 -> m r

So let's see here, it takes a function (a1 -> r), takes a monad with an a1 in it, applies that function to the a1, and returns the result. In my opinion, the best way to understand this function is to see how it is used. The following pieces of code all mean the same thing

do foo <- someMonadicThing
return (myFn foo)

liftM myFn someMonadicThing

myFn `liftM` someMonadicThing

What made the light bulb go off for me is this third example, where we use liftM as an operator. liftM is just a monadic version of ($)!

myFn $ aNonMonadicThing

myFn `liftM` someMonadicThing

[edit] lift

When using combined monads created by the monad transformers, we avoid having to explicitly manage the inner monad types, resulting in clearer, simpler code. Instead of creating additional do-blocks within the computation to manipulate values in the inner monad type, we can use lifting operations to bring functions from the inner monad into the combined monad.

Recall the liftM family of functions which are used to lift non-monadic functions into a monad. Each monad transformer provides a lift function that is used to lift a monadic computation into a combined monad.

The MonadTrans class is defined in Control.Monad.Trans and provides the single function lift. The lift function lifts a monadic computation in the inner monad into the combined monad.

class MonadTrans t where
 lift :: (Monad m) => m a -> t m a

Monads which provide optimized support for lifting IO operations are defined as members of the MonadIO class, which defines the liftIO function.

class (Monad m) => MonadIO m where
 liftIO :: IO a -> m a

[edit] Using lift

[edit] Implementing lift

Implementing lift is usually pretty straightforward. Consider the transformer MaybeT:

instance MonadTrans MaybeT where
 lift mon = MaybeT (mon >>= return . Just)

We begin with a monadic value (of the inner monad), the middle layer, if you prefer the monadic sandwich analogy. Using the bind operator and a type constructor for the base monad, we slip the bottom slice (the base monad) under the middle layer. Finally we place the top slice of our sandwich by using the constructor MaybeT. So using the lift function, we have transformed a lowly piece of sandwich filling into a bona-fide three-layer monadic sandwich.

As with our implementation of the Monad class, the bind operator is working within the confines of the inner monad.

[edit] The State monad transformer

Previously, we have pored over the implementation of two very simple monad transformers, MaybeT and ListT. We then took a short detour to talk about lifting a monad into its transformer variant. Here, we will bring the two ideas together by taking a detailed look at the implementation of one of the more interesting transformers in the standard library, StateT. Studying this transformer will build insight into the transformer mechanism that you can call upon when using monad transformers in your code. You might want to review the section on the State monad before continuing.

Just as the State monad was built upon the definition

newtype State s a = State { runState :: (s -> (a,s)) }

the StateT transformer is built upon the definition

newtype StateT s m a = StateT { runStateT :: (s -> m (a,s)) }

State s is an instance of both the Monad class and the MonadState s class, so

StateT s m should also be members of the Monad and MonadState s classes. Furthermore, if m is an instance of MonadPlus,

StateT s m should also be a member of MonadPlus.

To define StateT s m as a Monad instance:

newtype State s a = State { runState :: (s -> (a,s)) }

instance Monad (State s) where
 return a        = State $ \s -> (a,s)
 (State x) >>= f = State $ \s ->
     let (v,s') = x s
     in runState (f v) s'

newtype StateT s m a = StateT { runStateT :: (s -> m (a,s)) }

instance (Monad m) => Monad (StateT s m) where
 return a         = StateT $ \s -> return (a,s)
 (StateT x) >>= f = StateT $ \s -> do
     (v,s') <- x s          -- get new value and state
     runStateT (f v) s'     -- pass them to f

Our definition of return makes use of the return function of the inner monad, and the binding operator uses a do-block to perform a computation in the inner monad.

We also want to declare all combined monads that use the StateT transformer to be instances of the MonadState class, so we will have to give definitions for get and put:

instance (Monad m) => MonadState s (StateT s m) where
 get   = StateT $ \s -> return (s,s)
 put s = StateT $ \_ -> return ((),s)

Finally, we want to declare all combined monads in which StateT is used with an instance of MonadPlus to be instances of MonadPlus:

instance (MonadPlus m) => MonadPlus (StateT s m) where
 mzero = StateT $ \s -> mzero
 (StateT x1) `mplus` (StateT x2) = StateT $ \s -> (x1 s) `mplus` (x2 s)

The final step to make our monad transformer fully integrated with Haskell's monad classes is to make StateT s an instance of the MonadTrans class by providing a lift function:

instance MonadTrans (StateT s) where
 lift c = StateT $ \s -> c >>= (\x -> return (x,s))

The lift function creates a StateT state transformation function that binds the computation in the inner monad to a function that packages the result with the input state. The result is that a function that returns a list (i.e., a computation in the List monad) can be lifted into StateT s [], where it becomes a function that returns a StateT (s -> [(a,s)]). That is, the lifted computation produces multiple (value,state) pairs from its input state. The effect of this is to "fork" the computation in StateT, creating a different branch of the computation for each value in the list returned by the lifted function. Of course, applying StateT to a different monad will produce different semantics for the lift function.

[edit] Acknowledgements

This module uses a large amount of text from All About Monads with permission from its author Jeff Newbern.