3

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?

Ruifeng Xie
  • 813
  • 4
  • 16
  • 2
    `Writer` is just `WriterT` with `m ~ Identity`, and the space leak issue with `Writer` is frequently discussed using the list monoid so `++` **is** the `mappened` operation, which as you note is lazy in the second parameter. – Ben Aug 28 '19 at 01:33
  • @Ben, I understand that `Writer w ~ WriterT w m`, as well as `mappend = (++)` in the list monoid. Given that the general `WriterT` has space leak problems, what I wonder was whether this also apply to the simple `Writer` monad with lazy `mappend`. I am asking **whether space leaks also happen** in such situations. – Ruifeng Xie Aug 28 '19 at 01:41
  • It would leak. See https://blog.infinitenegativeutility.com/2016/7/writer-monads-and-space-leaks – Thomas M. DuBuisson Aug 28 '19 at 02:17
  • @ThomasM.DuBuisson I have read that before. Actually, I learned about space leaks on `Writer` monads just from that blog. But it did not clarify the space leak issue when `mappend` does not force the evaluation of its second parameter. – Ruifeng Xie Aug 28 '19 at 02:22
  • I found Getty's write up really fitting "notice that in order to start evaluating the call to mappend in step C, we need to have the output from both steps A and B. …except step B represents evaluating the entire rest of the computation, including an arbitrarily large number of other calls to >>=". I.E. the leak happens before mappend is ever called. – Thomas M. DuBuisson Aug 28 '19 at 02:55
  • @ThomasM.DuBuisson Oh, I got it. I finally noticed the `b` in the bind operator. That result is from the second action, so the second action should still performed before `mappend`. – Ruifeng Xie Aug 28 '19 at 02:58
  • @Krantz Apologies for being unclear. I was trying to say that your 2 suggestions are usually present in examples given when discussing the problem, which wouldn't be the case if your 2 suggestions avoided the problem. – Ben Aug 28 '19 at 03:07
  • @Ben Thanks. I think I know the actual issue now. The leak happens because of the non-tail-recursive nature of the bind operator, not because of strictness. – Ruifeng Xie Aug 28 '19 at 03:11

0 Answers0