Stricter WriterT monad transformer
Edward Kmett
ekmett at gmail.com
Sat Oct 6 00:05:42 CEST 2012
I use a version of this in my old monad-ran package and in trifecta.
There is a huge caveat that needs to be stated though in the haddocks if nowhere else, the resulting type is in many ways 'too big' because the user can do more with it than just Writer operations!
If you can talk Ross into adding it to transformers, I'd be willing to toss the instance in the mtl.
It might be worth exploring the design space a bit more though to see if there isn't a 'smaller' type that satisfices.
Sent from my iPad
On Oct 5, 2012, at 5:04 PM, Gabriel Gonzalez <gabriel439 at gmail.com> wrote:
> 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.
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
More information about the Libraries
mailing list