Gabriel Gonzalez | 5 Oct 23:04 2012
Picon

Stricter WriterT monad transformer

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
(Continue reading)

Evan Laforge | 5 Oct 23:09 2012
Picon

Re: Stricter WriterT monad transformer

On Fri, Oct 5, 2012 at 2:04 PM, Gabriel Gonzalez <gabriel439 <at> gmail.com> wrote:
> 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

Long ago, I had the same problem, and went through the same three
attempts before settling on the last one.  With help from kind people
on haskell-cafe (probably findable in the archives).

So I support putting it in libraries along with comments about why, so
that future generations need not go through the same process.  Then we
can tell them about how we had to walk in the snow both ways uphill
fighting space leaks with bare hands while they just have to read
about it.

For the same reason I support State.modify' :)
Edward Kmett | 6 Oct 00:05 2012
Picon

Re: Stricter WriterT monad transformer

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
(Continue reading)

Gabriel Gonzalez | 6 Oct 03:20 2012
Picon

Re: Stricter WriterT monad transformer

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

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

Gmane