2010 March 14

Writer Monads via Continuations

Filed under: continuations, haskell, monads — lpsmith @ 9:00 pm

I have four draft posts started that I don’t have finished. But I won’t be finishing any of them today, instead I’ll issue an erratum for my paper in Issue 14 of the Monad Reader. On page 53 I wrote:

Writer monads partially enforce the efficient use of list concatenation. In the MTL, `Writer [e] a` is just a newtype isomorphism for `([e], a)`. It provides a function `tell` that takes a list and concatenates the remainder of the computation onto the end of the list. This naturally associates to the right, and thus avoids quadratic behavior. Of course, tell accepts arbitrary length lists, and one could inefficiently produce a long argument to tell.

The writer monad does no such thing. In fact, it’s quite easy to write a function using the writer monad that exhibits quadratic behavior. For example here is a function that uses the writer monad to produce the list `[1..n]` in quadratic time:

```enumTo n
| n <= 0    = return ()
| otherwise = enumTo (n-1) >> tell [n]
```

By unfolding the definitions of return and (>>=) for Control.Monad.Writer, and the Monoid instance for List, we can find this is equivalent to:

```enumToWriter n
| n <= 0    = ((), [])
| otherwise = let (a,w ) = enumToWriter (n-1)
(b,w') = (\_ -> ((),[n])) ()
in (b,w ++ w')
```

By beta-reducing the let bindings and making use of snd, we get

```enumToWriter'2 n
| n <= 0    = ((), [])
| otherwise = ((), snd (enumToWriter'2 (n-1)) ++ [n])
```

And finally, we can hoist the pairs out of the loop, if we want:

```enumToWriter'3 n = ((), loop n)
where
loop n
| n <= 0    = []
| otherwise = loop (n-1) ++ [n]
```

It should now be clear that this is quadratic, as the first element of the result gets copied (n-1) times, the second element gets copied (n-2) times, and so on. However, there is a solution. By adjusting the monad, the original definition can be executed in linear time. My erroneous quote is actually an accurate description the continuation-based writer monad.

```
instance (Monoid w) => MonadWriter w (Cont w) where
tell xs = Cont (\k -> xs `mappend` k ())
-- or,  in a direct style:
-- tell xs = mapCont (xs `mappend`) (return ())
```

The expression `runCont (enumTo n) (const [])` produces the list `[1..n]` in linear time. The continuation-based writer monad provides the linear-time guarantee that I described but erroneously attributed to the regular writer monad. By unfolding the definition of return and (>>=) for Control.Monad.Cont and our definition for `tell` above, we can find out what this algorithm actually does:

```-- unfold return and (>>=)
enumToCont n
| n <= 0    = k ()
| otherwise = \k -> enumToCont (n-1) (\a  -> (\_ -> tell [n]) a k)
-- beta-reduction
--            = \k -> enumToCont (n-1) (\_a -> tell [n] k)
-- unfold tell
--            = \k -> enumToCont (n-1) (\_  -> (\k -> [n] ++ k ()) k)
-- beta-reduction
--            = \k -> enumToCont (n-1) (\_  -> [n] ++ k ())
-- unfold (++)
--            = \k -> enumToCont (n-1) (\_  -> n : k ())
```

And, if we like, we can avoid passing () to the continuation argument, resulting in a normal accumulator argument:

```enumToCont' n k
| n <= 0    = k
| otherwise = enumToCont' (n-1) (n:k)
```

By writing it with `(:)`, we know it has to associate to the right and thus operates in linear time. In the quadratic-time solution, the `(++)` cannot be unfolded. However, this solution isn’t incremental: trying to evaluate `take 5 (enumToCont' (10^12) [])` will more than likely run your computer completely out of virtual memory long before it finishes. It’s not to difficult to see why: `enumFromCont'` produces a list element equal to it’s input, and it has to count down from a trillion before it produces `[1,2,3,4,5, ...]`. So it really is better to write it as:

```enumTo' lim = loop 1
where
loop n
| n <= lim  = tell [n] >> loop (n+1)
| otherwise = return ()
```

This definition is both linear and incremental under both the continuation-based writer and the normal writer monad, but it isn’t a generic transformation that applies to any algorithm using the writer monad.

These two writer monads have a number tradeoffs; for example, the continuation-based writer monad cannot be used with the corecursive queue transformer in the paper. An efficient alternative is the regular writer monad with a list representation that offers efficient concatenation, such as difference lists.

For further reading, you might enjoy Asymptotic Improvement of Computations over Free Monads by Janis Voigtländer, which explores this phenomenon further.

1. Another disadvantage of continuation-based monads is that you can’t make them instances of MonadFix :(

Comment by Job — 2010 March 15 @ 7:36 am

• Yes. The continuation monad lacks an `MonadFix` instance, which is why you can’t use it with the corecursive queue transformer. ;-) Additionally, you can’t use it with the examples in Fun with the Lazy State Monad for a different reason: the continuation monad transmutes the lazy state monad into a strict state monad.

It is believed to be impossible to define `MonadFix` on the standard continuation monad, but as far as I am aware, this is not definitively known. Levent Erkök wrote about this conjecture in his Ph.D. thesis Value Recursion in Monadic Computations, where he proves a theorem that seems to support the conjecture.

However, we now know that the statement of Erkök’s conjecture needs to be made more precise. For example, the codensity monad is a continuation monad that uses higher-ranked types to hide the type of the result. It appears in Edward Kmett’s category-extras and Mauro Jaskelioff’s Monatron library, and is the key to Janis Voigtländer’s paper. Interestingly, the codensity monad admits an instance for `MonadFix`, as demonstrated by Monatron but not category-extras. However, the codensity’s `MonadFix` does not appear to be well-behaved, as I don’t know of any interesting examples where it converges.

Also, I’ve heard Erkök’s conjecture informally stated as “there are no useful fixpoint operators on continuations”, which my paper “Lloyd Allison’s Corecursive Queues” throughly refutes. Not only did I demonstrate a fixpoint operator on the continuation monad, I also demonstrate a practical application where it’s use seems to be required!

If you are really interested in the studying the relationship of `MonadFix`, the continuation monad, and other continuation-like monads, you should probably take a look at “Recursion is a Computational Effect” by Dan Friedman and Amr Sabry. I don’t understand all the details, but they implement `mfix` on the continuation monad using `unsafePerformIO`, and use it to implement “LETREC + CALL/CC = SET!” in Haskell.

It seems likely that there is something here yet to be discovered. At the very least, there are explanations to be made and things to be definitively confirmed or refuted.

Comment by lpsmith — 2010 March 15 @ 7:44 pm

2. Also, I should say that the continuation-based writer monad is one of the key aspects of all the various corecursive queue monads in my paper. If you are comfortable with this post, then it should be a little bit easier to understand the construction in my paper.

To clarify, the continuation-based writer is used internally as part of the corecursive queue transformer, but it cannot be used as an argument to the transformer.

Comment by lpsmith — 2010 March 15 @ 8:00 pm