Stricter WriterT monad transformer

Gabriel Gonzalez gabriel439 at gmail.com
Fri Oct 5 23:04:04 CEST 2012


This is a suggestion I initially ran by Ross and he recommended that I 
post it to this mailing list.

Here's the problem: WriterT always leaks space.  I've tested three ways 
to fix the space leak, and only one works:

* [DOES NOT WORK] Add a strictness annotation to the Monad instance for 
WriterT
* [DOES NOT WORK] Use the StateT monad transformer *without* a 
strictness annotation
* [WORKS] Use the StateT monad transformer *with* a strictness annotation

I've hpasted the three different approaches and their test cases so you 
all can test it for yourselves:

http://hpaste.org/75837

I'm requesting this because I need a WriterT monad transformer that does 
not leak space for defining folds for my pipes library.  I can 
temporarily define the correct one within my own library but in the long 
run I believe it belongsin transformers.

I also discovered another subtle advantage of using StateT to simulate 
WriterT.  The traditional WriterT monad instance punishes the case where 
you use a free monad as the base monad because of the following bind in 
its monad instance:

instance (Monad m, Monoid w) => Monad (WriterT w m) where
     return a = WriterT2 $ return (a, mempty)
     m >>= f  = WriterT2 $ do
         (a, w)  <- runWriterT m
         (b, w') <- runWriterT (k a)  <= This bind is the problem
         return (b, w `mappend` w')

This bind triggers a quadratic blowup when the base monad is a free 
monad, whereas the StateT simulation of WriterT runs in linear time.

For these reasons, I suggest adding a 
"Control.Monad.Trans.Writer.Stricter" module to "transformers" that 
implements WriterT using the "WriterT4" implementation from the above 
hpaste.



More information about the Libraries mailing list