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] ais just a newtype isomorphism for
([e], a). It provides a function
tellthat 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]
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 ())
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.