Stricter WriterT monad transformer

Gabriel Gonzalez gabriel439 at gmail.com
Sat Oct 6 03:20:55 CEST 2012


Alright.  I think Edward is right and perhaps some Codensity-like
transformation will keep the type smaller.  I will try my hand at it.
On Oct 5, 2012 3:05 PM, "Edward Kmett" <ekmett at gmail.com> wrote:
>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20121005/7af3734c/attachment.htm>


More information about the Libraries mailing list