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