## Monad transformers: a cautionary tale

When writing the code in my previous post, I wanted to have a monad which combined the ability to generate random numbers with the ability to fail. Naturally, I decided to use `RandT Maybe`. But when I tried to write a failing computation of this type, I got a type error:

``````    No instance for (MonadPlus (RandT StdGen Maybe))
arising from a use of `mzero'``````

It seems that no one ever bothered to add a `MonadPlus` instance for `RandT`. Well, that’s easy to fix. Since `RandT` is just a newtype wrapper around `StateT` we can even derive a `MonadPlus` instance automatically using `-XGeneralizedNewtypeDeriving`. So I modified the `MonadRandom` package, and everything worked great.

…That is, everything worked great until I started to get some strange behavior—sometimes computations would hang when I expected them to complete quickly. I finally was able to boil it down to the following minimal example. `foo` succeeds or fails with equal probability; `bar` reruns `foo` until it succeeds.

``````foo :: RandT StdGen Maybe ()
foo = do
r <- getRandomR (0,1)
if r < 1/2 then return () else mzero

bar :: RandT StdGen Maybe ()
bar = foo `mplus` bar``````

Seems straightforward, right? `bar` should always succeed pretty much instantly, since there’s only a $1/2^n$ chance that it will have to call `foo` $n$ times.

However, this is not what happens: some of the time `bar` returns instantly as expected, and some of the time it hangs in what seems like an infinite loop! What gives?

Have you figured it out yet? (If you like these sorts of puzzles you might want to stop and see if you can figure out what was going on.) The problem is that the `mplus` operation for `RandT StdGen Maybe` runs both of its arguments with the same random seed! In other words, when a computation fails the generator state gets thrown away. And if we think about how monad transformers work this is actually not surprising. We have the following isomorphisms:

``````   RandT StdGen Maybe ()
== StateT StdGen Maybe ()
== StdGen -> Maybe ((), StdGen)``````

So when a computation fails you just get `Nothing`—in particular you don’t get to see what the new `StdGen` value would have been, so you can’t (say) pass it along to the second argument of `mplus`. The upshot is that `bar` succeeds if the first call to `foo` happens to succeed; otherwise it simply keeps calling `foo` with the exact same seed and `foo` keeps failing every time.

The general principle here is that “the effects of inner monad transformers take precedence over the effects of outer transformers”—in this case the failure effect of the inner `Maybe` takes precedence and causes the random generator state to be lost.

So what I really wanted was `MaybeT (Rand StdGen)`, which—after adding a `MonadRandom` instance for `MaybeT`, now released as `MonadRandom`-0.1.9—works perfectly.

The moral of the story: monad transformers aren’t (in general) commutative! Think carefully about what order you want. (I actually wrote about this once before; you’d think I would have learned my lesson.)