Can we avoid space leaks in the Writer monad by making mappend non-strict on the second parameter

316 Views Asked by At

I recently read about the space leak issue of the Writer/WriterT monad. If I correctly understood this problem, it is because the bind operator, i.e. (>>=) is not tail-recursive:

m >>= f = WriterT $ do
    (a, w1) <- runWriterT m
    (b, w2) <- runWriterT (f a)
    return (b, w1 `mappend` w2)

With the definition of WriterT and Writer:

newtype WriterT w m a = WriterT { runWriterT :: m (a, w) }
type Writer w = WriterT w Identity

I am curious about whether introducing laziness on the second parameter of mappend would solve this space-leak problem.

By introducing laziness, I mean something like the (++) operator:

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : (xs ++ ys)

The result is produced without actually touching the second parameter.

Now, if we use a monad m with lazy monadic bind (e.g. m ~ Identity, which gives us the plain old Writer monad), and use mappend mentioned above, then the f a part (w2) can remain a thunk while evaluating mappend w1 w2, thus the result can be partially consumed (w1) without actually forcing the rest expression (w2).

Am I correct on this? Are space leaks avoided in such Writer monads?

0

There are 0 best solutions below