Melding Monads

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.

The Shocking Blue Green Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.