Monad Transformers: Constructive Stack Order

What are Monad Transformers?

Monad Transformers provide a modular solution to combining monads, in which a combined monad can be viewed as an ordered stack of layers -- each layer implements the semantics of a single monad. Here's a small stack:

top:     State
bottom:  Maybe

And here's a bigger one:

top:     State
         Maybe
         Error
         Maybe
         Writer
bottom:  Reader

As I mentioned, the stack is ordered -- and one of the problems that people run into when learning how to use monad transformers is what difference the stack order makes, figuring out what the semantics of a given stack are, and coming up with a stack that meets some given criteria.

Does stack order matter?

Yes! For example, let's compare State/Maybe to Maybe/State using the standard transformers. First, we create a stateful computation that increments the state by 1 -- this shows how many times it's executed -- then we create a computation that runs `inc`, fails, and runs `inc` again:

import Control.Monad.State          (StateT(..), MonadState(..))
import Control.Monad.Trans.Maybe    (MaybeT(..))
import Control.Applicative          (Alternative(..))
import Data.Functor.Identity        (Identity(..))

inc :: (Num s, MonadState s m) => m ()
inc = get >>= (put . (+ 1))

calc :: (Num s, MonadState s m, Alternative m) => m ()
calc = (inc >> empty) <|> inc

Here we create our two stacks, differing only in order, and functions for unwrapping the stacks from all the constructors:

type Type1 s a = StateT s (MaybeT Identity) a
type T
ype2 s a = MaybeT (StateT s Identity) a
run1 :: Int -> Maybe ((), Int)
run1 s = runIdentity $ runMaybeT (runStateT calc s)

run2 :: Int -> (Maybe (), Int)
run2 s = runIdentity $ runStateT (runMaybeT calc) s

And the results?

*Main> run1 32
Just ((),33)

*Main> run2 32
(Just (),34)

Different! Apparently the first example only ran `inc` once, while the second ran it twice -- but why?

Calculating stack order

In order to figure out the underlying types of transformer stacks, we need two things: first, the types of monads to which they are applied:

Maybe         /\  a.  Maybe a
State         /\s a.  s -> (a, s)
List          /\  a.  [] a
Identity      /\  a.  a
Either        /\e a.  Either e a
Reader        /\r a.  r -> a
Writer        /\w a.  (a, w)
Cont          /\r a.  (a -> r) -> r

and second, the types of the transformers. Working from Haskell's mtl monad transformer library, I've pulled out the types:

MaybeT        /\  m a.    m (Maybe a)

StateT        /\s m a.    s -> m (a, s)

ListT         /\  m a.    m [a]

IdentityT     /\  m a.    m a

ErrorT        /\e m a.    m (Either e a)

ReaderT       /\r m a.    r -> m a

WriterT       /\w m a.    m (a, w)

ContT         /\r m a.    (a -> m r) -> m r

Now to start building complicated stacks, there are two approaches that I use. The first I find simpler: starting from simple monads, successively add layers, with the result of each step being a more complicated monad that could be placed in the bottom of a monad transformer stack. In other words, what we're doing is:

1. simple monad, or monad(1)
2. transformer + monad(1) = monad(2)
3. transformer + monad(2) = monad(3)
4. ... etc. ...

And an example using StateT as the transformer and Maybe as the monad:

• Step 1: write down the types that the transformer and monad represent
• transformer: /\s m a. s -> m (a, s)
• monad: /\a. Maybe a
• Step 2: substitute the monad into the transformer type, taking the place of type variable `m`
• /\s m a. s -> Maybe (a, s)
• unbind type variable m, bind all type variables except the last (`a`) from the monad
• /\s a. s -> Maybe (a, s)

Let's also do it the other way around: MaybeT and State:

• Step 1: /\m a. m (Maybe a) and /\s a. s -> (a, s)
• Step 2: /\m a. s -> (Maybe a, s)
• Step 3: /\s a. s -> (Maybe a, s)

So we've built some 2-layer monads which can themselves be passed to transformers. For example, with ErrorT as the transformer and Maybe/State as the monad:

• Step 1: /\e m a. m (Either e a) and /\s a. s -> (Maybe a, s)
• Step 2: /\e m a. s -> (Maybe (Either e a), s)
• Step 3: /\e s a. s -> (Maybe (Either e a), s)

And applying ErrorT to State/Maybe:

• Step 1: /\e m a. m (Either e a) and /\s a. s -> Maybe (a, s)
• Step 2: /\e m a. s -> Maybe (Either e a, s)
• Step 3: /\e s a. s -> Maybe (Either e a, s)

The third step is just to tidy things up, making sure the right type variables are in scope and that unused ones are not in scope. The second approach is to combine a transformer with another transformer to create a two-layer transformer. It works similarly to the first approach, except that the resulting transformer can be placed anywhere in a monad stack, instead of just at the bottom.

Semantic differences from stack order

So why is Maybe/State `s -> (Maybe a, s)` different from State/Maybe `s -> Maybe (a, s)`? In Maybe/State, the state is outside of the Maybe, which means that even if the computation fails, you'll still get a (possibly modified) state output; in State/Maybe, if the computation fails, you won't get a new state.

What this means is that the state in Maybe/State is not subject to Maybe's effects; if you're using Maybe for backtracking, as we were in the examples, any modifications to the state won't be undone by backtracking. Since the state is subject to Maybe's effects in State/Maybe, backtracking did prevent the effect of the first `inc` from being reflected in the final output. It's important to note that both orderings are useful in practice, albeit for different things.

On the other hand, for other combinations the order doesn't matter. Examples are Maybe/Error and State/Writer. I don't know of any rule to figure out which pairs are order-dependent and which aren't, so I'm stuck looking it up on a little table of combinations!