Haskell/Monad transformers

From Wikibooks, open books for an open world
Jump to: navigation, search

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. With monads providing such useful general-purpose functionalities, it is very natural that sometimes we would like to use the capabilities of several monads at once - for instance, a function which uses both I/O and Maybe exception handling. Sure, we can use a type like IO (Maybe a), but that forces us to do pattern matching within the do blocks to extract the values you want: the point of monads was also to get rid of that.

Enter monad transformers: special types that allow us to roll two monads into a single one that shares the behaviour of both. We will begin with an example to illustrate why transformers are useful and show a simple example of how they work.

Password validation[edit]

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
 
-- The validation test could be anything we want it to be.
isValid :: String -> Bool
isValid s = length s >= 8 && any isAlpha s && any isNumber s && any isPunctuation s

First and foremost, getPassword is an IO function, as it needs to get input from the user, and so it will not always return. We also use Maybe, as we intend to return Nothing in case the password does not pass the isValid. Note, however, that we aren't actually using Maybe as a monad here: the do block is in the IO monad, and we just happen to return a Maybe value into it.

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. Our password acquisition program could continue like this:

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

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 transformers, we will be able to extract the password in one go, without any pattern matching or equivalent bureaucracy like isJust. The gains for our simple example might seem small, but will scale up for more complex situations.

A simple monad transformer: MaybeT[edit]

To simplify getPassword function and all 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 a wrapper around m (Maybe a), where m can be any monad (in our example, we are interested in IO):

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

This data type definition specifies a MaybeT type constructor, parametrized over m, with a term constructor, also called MaybeT, and a convenient accessor function runMaybeT, with which we can access the underlying representation.

The whole point of monad transformers is that they are monads themselves; and 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

Like for all monads, the bind operator is the heart of the transformer, and the most important snippet for understanding how it works. As always, it is useful to keep the type signature in mind. The type of the MaybeT bind is:

-- The signature of (>>=), specialized to MaybeT m
(>>=) :: MaybeT m a -> (a -> MaybeT m b) -> MaybeT m b

Now, let us consider what it does, step by step, starting from the first line of the do block.

  • First, it uses the runMaybeT accessor to unwrap x into a m (Maybe a) computation. That gives away the do block is in m.
  • Still in the first line, <- extracts a Maybe a value from the unwrapped computation.
  • The case statement tests maybe_value:
    • if it is Nothing, it returns Nothing into m;
    • if it is a Just, it applies f to the value inside it. Since f has MaybeT m b as result type, we need an extra runMaybeT to put the result back into the m monad.
  • Finally, the do block as a whole has m (Maybe b) type; so it is wrapped with the MaybeT constructor.

It may look a bit complicated; but other than for the copious amounts of wrapping and unwrapping, the implementation does the same as the familiar bind operator of Maybe:

-- (>>=) for the Maybe monad
    maybe_value >>= f = case maybe_value of
                            Nothing -> Nothing
                            Just value -> f value

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.

Note

The chained functions in the definition of return suggest an analogy, which you may find either useful or confusing, between the combined monad and a sandwich. In this example, Maybe, the "base" monad, would be the bottom layer; the inner monad m, the filling; and the transformer MaybeT, the top layer. There is some danger in the analogy in that it might suggest there are three layers of monads in action, while in fact there are only two: the inner monad and the combined monad (there are no binds or returns done in the base monad; it only appears as part of the implementation of the transformer). A better way of interpreting the analogy is thinking of the transformer and the base monad as two parts of the same thing - the bread - which wraps the inner monad.


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 _     -> return maybe_value
 
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. As for MonadPlus, since Maybe is an instance of that class it makes sense to make the MaybeT an instance too.

Application to the password example[edit]

With all this done, here is what the previous example of password management looks like:

getValidPassword :: MaybeT IO String
getValidPassword = do s <- lift getLine
                      guard (isValid s) -- MonadPlus provides guard.
                      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. Most importantly, we do not have to manually check whether the result is Nothing or Just: the bind operator takes care of that for us.

Note how we use lift to bring the 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, with the help of MonadPlus 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..."

A plethora of transformers[edit]

The modules of the transformers package provide transformers for many common monads (MaybeT, for instance, can be found in Control.Monad.Trans.Maybe). They are defined consistently with their non-transformer versions; that is, the implementation is basically the same, only with the extra wrapping and unwrapping needed to thread the other monad. From this point on, we will refer to the non-transformer monad on which the transformer is based as the base monad, and to the other monad, on which the transformer is applied, as the inner monad.

To pick an arbitrary example, ReaderT Env IO String is a computation which involves reading values from some environment of type Env (the semantics of Reader, the base monad) and performing some IO in order to give a value of type String. Since the bind operator and return for the transformer mirror the semantics of the base monad, a do block of type ReaderT Env IO String will, from the outside, look a lot like a do block of the Reader monad; the main difference being that IO actions become trivial to embed by using lift.

Type juggling[edit]

We have seen that the type constructor for MaybeT is a wrapper for a Maybe value in the inner monad, and so the corresponding accessor runMaybeT gives us a value of type m (Maybe a) - that is, a value of the base monad returned in the inner monad. In a similar fashion, we have

runListT :: ListT m a -> m [a]

and

runErrorT :: ErrorT e m a -> m (Either e a)

for the list and error transformers.

Not all transformers are related to their base monads in this way, however. The Writer, Reader, State and Cont monads have in common that, unlike the base monads in the examples above, they have neither multiple constructors nor constructors with multiple arguments. For that reason, they have run... functions, which act as simple unwrappers analogous to the run...T of the transformer versions. The table below shows the result types of the run... and run...T functions in each case, which may be thought of as the types wrapped by the base and transformed monads respectively.[1]

Base Monad Transformer Original Type
("wrapped" by base)
Combined Type
("wrapped" by transformed)
Writer WriterT (a, w) m (a, w)
Reader ReaderT r -> a r -> m a
State StateT s -> (a, s) s -> m (a, s)
Cont ContT (a -> r) -> r (a -> m r) -> m r

The first thing to notice is the base monad is nowhere to be seen in the combined types. That is very natural, as without interesting constructors (like the ones for Maybe or lists) there is no reason to retain the base monad type after unwrapping the transformed monad. Besides that, in the three latter cases we have function types being wrapped. StateT, for instance, turns state-transforming functions of the form s -> (a, s) into state-transforming functions of the form s -> m (a, s); so that only the result type of the wrapped function goes into the inner monad. ReaderT is analogous, but not ContT: due to the semantics of Cont (the continuation monad) the result types of both the wrapped function and its functional argument must be the same, and so the transformer puts both into the inner monad. What these examples show is that 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.

Lifting[edit]

The lift function, which we have first presented in the introduction, is very important in day-to-day usage of transformers; and so we will dedicate a few more words to it.

liftM[edit]

Let us begin by considering the more familiar liftM function. It has the following type:

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

liftM applies a function (a1 -> r) to a value within a monad m. If you prefer the point-free interpretation, it converts a regular function into one that acts within m - and that is what is meant by lifting.

To recapitulate, here is a simple example of liftM usage. The following pieces of code all mean the same thing.

do notation liftM liftM as an operator
do x <- monadicValue
   return (f x)
liftM f monadicValue
f `liftM` monadicValue

The third example, in which we use liftM as an operator, suggests an interesting way of viewing liftM: it is a monadic analogue of ($)!

non monadic monadic
f $ value
f `liftM` monadicValue

lift[edit]

When using combined monads created with monad transformers, we avoid having to manage the inner monad types explicitly, 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.

With liftM we have seen how the essence of lifting is, to paraphrase the documentation, promoting something into a monad. The lift function, available for all monad transformers, performs a different kind of lifting: it promotes a computation from the inner monad into the combined monad. lift is defined as the single method of the MonadTrans class in Control.Monad.Trans.Class.

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

There is a variant of lift specific to IO operations called liftIO, which is the single method of the MonadIO class in Control.Monad.IO.Class.

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

liftIO can be convenient when having multiple transformers stacked into a single combined monad. In such cases, IO is always the innermost monad, and so more than one lift would be typically needed to bring IO values to the top of the stack. liftIO, however, is defined for the instances in a way that allows us to bring n IO value from any depth while writing the function a single time.

Implementing lift[edit]

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

instance MonadTrans MaybeT where
    lift m = MaybeT (m >>= 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. Note that, just as in the implementation of the Monad class, both the bind operator and the generic return are working within the confines of the inner monad.

Exercises
  1. Why is it that the lift function has to be defined separately for each monad, where as liftM can be defined in a universal way?
  2. Implement the lift function for the ListT transformer.
  3. How would you lift a regular function into a monad transformer? Hint: very easily.

Implementing transformers[edit]

In order to develop a better feel for the workings of transformers, we will discuss two more implementations in the standard libraries.

The List transformer[edit]

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

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

The implementation of the ListT m monad is also strikingly similar to its "cousin", the list monad. We do the same operations done for [], but with a little extra support to operate within the inner monad m, and to pack and unpack the monadic sandwich.

List ListT
instance Monad [] where
    return x = [x]
    xs >>= f =
        let yss = map f xs
        in concat yss
instance (Monad m) => Monad (ListT m) where
    return x = ListT $ return [x]
    tm >>= f = ListT $ runListT tm
               >>= \xs -> mapM (runListT . f) xs
               >>= \yss -> return (concat yss)
Exercises
  1. Dissect the bind operator for the (ListT m) monad. For example, why do we now have mapM and return?
  2. Identity is a trivial monad defined, in Data.Functor.Identity, as:

    newtype Identity a = Identity { runIdentity :: a }

    instance Monad Identity where
        return a = Identity a
        m >>= k = k (runIdentity m)


    Write a monad transformer IdentityT, which would be the transforming cousin of the Identity monad.
  3. Would IdentityT SomeMonad be equivalent to SomeMonadT Identity for a given monad and its transformer cousin?

The State transformer[edit]

Previously, we have pored over the implementation of one simple monad transformer, MaybeT, and reviewed the implementation of another, ListT, taking a detour along the way to talk about lifting from 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 might have been built upon the definition newtype State s a = State { runState :: (s -> (a,s)) }[2] 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 (which provides get and put), 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:

State StateT
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, if for instance we apply StateT to the List monad, 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.

Acknowledgements[edit]

This module uses a number of excerpts from All About Monads, with permission from its author Jeff Newbern.


Notes[edit]

  1. The wrapping interpretation is only literally true for versions of the mtl package older than 2.0.0.0 .
  2. In the transformers and mtl packages, State s is implemented as a type synonym for StateT s Identity. Incidentally, that explains why there was a state function instead of the State constructor back in the chapter about State, and why we had to defer the explanation until now.