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;
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 chance that it will have to call
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
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.)