Haskell/Monad transformers

From Wikibooks, the open-content textbooks collection



By this point you should have grasped the concept of monad, and what different monads are used for: IO for impure functions, Maybe for values that can be there or not, and so on. A common practical problem is that, sometimes, you would like to have a monad with several of these characteristic at once. Indeed you can use things like IO (Maybe a), but then you have to start doing pattern matching within do blocks to extract the values you want: the point of monads was also to get rid of that.

Enter monad transformers: these are special types that, when applied to a monad, generate a new, combined monad, that shares the behaviour of both.

[edit] Motivation

Consider a common real-life problem for IT staff worldwide: to get their users to select passwords that are not easy to guess. A typical strategy is to force the user to enter a password with a minimum length, and at least one letter, one number and similar irritating requirements.

A Haskell function to acquire a password from a user could look like:

getPassword :: IO (Maybe String)
getPassword = do s <- getLine
                 if isValid s then return $ Just s
                              else return Nothing

We need the IO monad because the function will not return always the same result, and the Maybe monad because we intend to return Nothing in case the password does not pass some test.

For the isValid function, you can use whatever you want; as an example, consider:

isValid :: String -> Bool
isValid s = length s >= 8 && any isAlpha s && any isNumber s && any isPunctuation s

The true motivation for monad transformers is not only to make it easier to write getPassword (which it nevertheless does), but rather to simplify all the code instances in which we use it:

askPassword :: IO ()
askPassword = do putStrLn "Insert your new password:"
                 maybe_value <- getPassword
                 if isJust maybe_value 
                     then putStrLn "Storing in database..."

We need one line to generate the maybe_value variable, and then we have to do some further checking to figure out whether our password is OK or not.

With monad combinators, we will be able to extract the password in one go, without any pattern matching. The gains for our simple example may seem small, but will scale up for more complex ones.

[edit] A Simple Monad Transformer: MaybeT

To simplify the code for the getPassword function and the code that uses it, we will define a monad transformer that gives the IO monad some characteristics of the Maybe monad; we will call it MaybeT, following the convention that monad transformers have a "T" appended to the name of the monad whose characteristics they provide.

MaybeT is essentially a wrapper around m (Maybe a), where m can be any monad (for our particular case, we are interested in IO):

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

using the accessor function runMaybeT we can access the underlying representation.

Monad transformers are monads themselves, so we need to make MaybeT m an instance of the Monad class:

instance Monad m => Monad (MaybeT m) where
    return  = MaybeT . return . Just

return is implemented by Just, which injects into the Maybe monad, a generic return that injects into m (whatever it is), and the MaybeT constructor. It would also have been possible (though arguably less readable) to write return = MaybeT . return . return.

    x >>= f = MaybeT $ do maybe_value <- runMaybeT x
                          case maybe_value of
                               Nothing    -> return Nothing
                               Just value -> runMaybeT $ f value

The bind operator, which is the most important code snippet to understand how the transformer works, extracts the Maybe value in the do block, and based on whether it is a Nothing or Just value it returns accordingly either m Nothing or m (Just value), wrapped in the MaybeT constructor.

You may wonder why we are using the MaybeT constructor before the do block, when inside it we use the accessor runMaybeT: however, the do block must be in the m monad, not in MaybeT m, since for the latter we have not yet defined the bind operator.

Technically, this is all we need; however, it is convenient to make MaybeT an instance of a few other classes:

instance Monad m => MonadPlus (MaybeT m) where
    mzero     = MaybeT $ return Nothing
    mplus x y = MaybeT $ do maybe_value <- runMaybeT x
                            case maybe_value of
                                 Nothing    -> runMaybeT y
                                 Just value -> runMaybeT x
 
instance MonadTrans MaybeT where
    lift = MaybeT . (liftM Just)

The latter class, MonadTrans, implements the lift function, which is very useful to take functions from the m monad and bring them into the MaybeT m monad, so that we can use them in do blocks inside the MaybeT m monad.

[edit] Application to Password Example

After having done all this, here is how the previous example of password management looks like:

getValidPassword :: MaybeT IO String
getValidPassword = do s <- lift getLine
                      guard (isValid s)
                      return s
 
askPassword :: MaybeT IO ()
askPassword = do lift $ putStrLn "Insert your new password:"
                 value <- getValidPassword
                 lift $ putStrLn "Storing in database..."

The code is now simpler, especially in the user function askPassword, and what is most important in that we do not need to manually check whether the result is Nothing or Just: the bind operator takes care of it for us.

Note how we use lift to bring functions getLine and putStrLn into the MaybeT IO monad. Also, since MaybeT IO is an instance of MonadPlus, checking for password validity can be taken care of by a guard statement, which will return mzero (i.e. IO Nothing) in case of a bad password.

Incidentally, it also becomes very easy to ask the user ad infinitum for a valid password:

askPassword :: MaybeT IO ()
askPassword = do lift $ putStrLn "Insert your new password:"
                 value <- msum $ repeat getValidPassword
                 lift $ putStrLn "Storing in database..."

[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 sandwich 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.