So Issue 14 of the Monad Reader is out, which includes my paper “Lloyd Allison’s Corecursive Queues” with a few significant revisions. Compared to earlier versions mentioned on this blog, I moved a few sections around to improve the flow: the first 8 pages now contain an uninterrupted informal derivation of the queue operators. I also demonstrated a new fixpoint operator on continuations, an implementation of the standard
mfix fixpoint on the codensity monad, and argued that
mapCont cannot be implemented in terms of
However, this post focuses on the section that I moved, entitled “Monad Transformers” from pages 51 to 56. It’s basically a short rant about why I don’t like monad transformers, an argument that later culminates in a mostly broken corecursive queue transformer. In retrospect, it’s somewhat unfortunate that I did not reread the classic paper Monad Transformers and Modular Interpreters sometime before Issue 14 came out. I did read that paper approximately nine or ten years ago. Although the paper was helpful in understanding how monads could be shaped to my own ends, now that I actually understand the contents of the paper, it feels rather crufty.
Section 8.1 defines correctness criteria for a monad transformer and associated lifted operations, which I quote as follows:
The basic requirement of lifting is that any program which does not use the added features should behave in the same way after a monad transformer is applied.
The thrust of my argument is that this requirement is indeed very basic; one would hope that certain properties useful for reasoning inside a given monadic language would also be preserved. This additional requirement seems rather hopeless. However, the pièce de résistance of the argument is that the continuation transformer is incorrect by their own criteria, at least in the context of a lazy language such as Haskell or Gofer.
I demonstrate an expression that depends on the laziness of the lazy state monad, and fails to terminate after a continuation transformer is applied. (As an aside, it doesn’t matter if this is a
ContT r (StateT st Identity) monad or
StateT st (ContT r Identity), they are the same monad with the same operations.) In retrospect, this seems obvious: something written in the continuation passing style specifies an evaluation order independent of the host language, and applying the continuation transformer corresponds to a call-by-value CPS transformation of part of the program.
The example involves a definition that computes a right fold over a level-order traversal of a tree:
foldrByLevel :: (MonadState (Queue a) m) => (a -> [a]) -> (a -> b -> b) -> b -> [a] -> m b foldrByLevel childrenOf f b as = fold as where fold  = deQ >>= maybe (return b) (\a -> fold (childrenOf a)) fold (a:as) = do enQ a b <- fold as return (f a b)
If we use this definition to traverse an infinite tree, it will be productive when run with
Control.Monad.State.Lazy, but will get stuck in an infinite non-productive loop when combined with
Control.Monad.Cont. You can download a complete file that demonstrates this phenomenon. There are “simpler” expressions that demonstrate this, but the example I gave is itself interesting because it is useful in other contexts.
As demonstrated in my paper, the laziness can be restored by tweaking the definition of
foldrByLevel to use
mapCont. However, this is a leaky abstraction: in order to maintain the same behavior, we must modify existing code to make use of the “added” features in ways that are not backwards compatible. I do not know how to write a lazy state monad using continuations, or a sensible way of writing a single definition of
foldrByLevel that behaves the same on both the lazy state monad and the continuation state monad.
(I use the word “sensible” because one could provide a unfaithful definition of
mapCont for the lazy state monad that happens to work in the case of
foldrByLevel, but fails in other contexts.)
What impact does this have on the notion that continuations are the mother of all monads? Is there a monad that corresponds to a call-by-name CPS transformation? Is it even possible to express the lazy state monad using continuations?
I do not yet have answers to these questions. One thing is clear, however: its tricky to generalize Filinski’s Representing Monads to lazy evaluation, if indeed it is possible to do so fully.