Gabriel Gonzalez | 17 Mar 17:18 2013
Picon

Stricter WriterT (Part II)

I previously asked on this mailing list about getting a stricter WriterT 
added to transformers here:

http://www.haskell.org/pipermail/libraries/2012-October/018599.html

To recap, neither of the two WriterT implementations in transformers 
keep the accumulator strictly evaluated.  In the previous request, I 
presented four implementations, only one of which runs in constant 
space, all of which are in this hpaste:

http://hpaste.org/75837

To summarize the four implementations:

Version #1: WriterT from Control.Monad.Trans.Writer.Strict
Version #2: Same as Version1, except the monad bind strictly evaluates 
the mappended result
Version #3: WriterT reimplemented as StateT, but no strictness annotations
Version #4: Same as Version3, except 'tell' strictly evaluates the 
mappended result

Only version #4 works and runs in constant space. Actually, not only 
does it run in constant space, but I failed to realize at the time that 
it also compiles to very efficient core when you add an `Int` type 
annotation to the summand.  For example, if you try to sum 1 billion 
`Int`s in the naive way using Version #4:

main :: IO ()
main = (print =<<) $ runWriterT4 $ replicateM_ 1000000000 $ tell4 $ Sum 
(1 :: Int)
(Continue reading)

Ross Paterson | 18 Mar 17:43 2013
Picon

Re: Stricter WriterT (Part II)

On Sun, Mar 17, 2013 at 09:18:13AM -0700, Gabriel Gonzalez wrote:
> So I propose that we add an additional stricter WriterT (under say,
> "Control.Monad.Trans.Writer.Stricter") which is internally
> implemented as StateT, but hide the constructor so we don't expose
> the implementation:
> 
> newtype WriterT w m a = WriterT { unWriterT :: w -> m (a, w) }
> 
> instance (Monad m, Monoid w) => Monad (WriterT w m) where
>     return a = WriterT $ \w -> return (a, w)
>     m >>= f  = WriterT $ \w -> do
>         (a, w') <- unWriterT m w
>         unWriterT (f a) w'
> 
> And define `tell` and `runWriterT` as follows:
> 
> tell :: (Monad m, Monoid w) => w -> WriterT w m ()
> tell w = WriterT $ \w' ->
>     let wt = w `mappend` w'
>      in wt `seq` return ((), w `mappend` w')
> 
> runWriterT :: (Monoid w) => WriterT w m a -> m (a, w)
> runWriterT m = unWriterT m mempty
> 
> If we do that, then WriterT becomes not only usable, but actually
> competitive with expertly tuned code.

Presumably we'll also need

writerT :: m (a, w) -> WriterT w m a
(Continue reading)

Johan Tibell | 18 Mar 17:53 2013
Picon

Re: Stricter WriterT (Part II)

On Sun, Mar 17, 2013 at 9:18 AM, Gabriel Gonzalez <gabriel439 <at> gmail.com> wrote:

So I propose that we add an additional stricter WriterT (under say, "Control.Monad.Trans.Writer.Stricter") which is internally implemented as StateT, but hide the constructor so we don't expose the implementation:

Nice work. If we end up adding a new module (instead of e.g. replacing the current one), lets try to have a more descriptive name. The -er names quickly get out of hand: New, Newer, MoreNewer, Newerest! Better to include a word that explains in what sense the writer is strict.

Let the bikeshedding begin!
 
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Gabriel Gonzalez | 19 Mar 16:07 2013
Picon

Re: Stricter WriterT (Part II)

> Presumably we'll also need
>
> writerT :: m (a, w) -> WriterT w m a

Yes, we would need that, too:

writerT m = WriterT $ \w -> do
     (a, w') <- m
     let wt = mappend w w'
     wt `seq` return (a, wt)

> Is there any reason to keep Control.Monad.Trans.Writer.Strict, or should this replace it?

If we replace the old one, it will break existing code that used the `WriterT` constructor.  Same thing for
the strict RWST constructor if we similarly modify that.  However, I don't know exactly how many packages
use those constructors.  I will try to do a text search of Hackage this coming weekend to check and see if it is
feasible to ask downstream packages that use `WriterT`/`RWST` constructors to set upper bounds on `transformers`.
Edward Kmett | 20 Mar 01:33 2013
Picon

Re: Stricter WriterT (Part II)

I use them fairly heavily, mostly so I can make packages that work with arbitrary transformer stacks.


I'd be willing to endure the pain of using #if MIN_VERSION_transformers(x,y,z) bracketing around the use of Strict.WriterT and Strict.RWST constructors so long as there were writerT/runWriterT and rwsT/runRWST analogues I could simply invoke.

-Edward

On Tue, Mar 19, 2013 at 11:07 AM, Gabriel Gonzalez <gabriel439 <at> gmail.com> wrote:
Presumably we'll also need

writerT :: m (a, w) -> WriterT w m a

Yes, we would need that, too:

writerT m = WriterT $ \w -> do
    (a, w') <- m
    let wt = mappend w w'
    wt `seq` return (a, wt)


Is there any reason to keep Control.Monad.Trans.Writer.Strict, or should this replace it?

If we replace the old one, it will break existing code that used the `WriterT` constructor.  Same thing for the strict RWST constructor if we similarly modify that.  However, I don't know exactly how many packages use those constructors.  I will try to do a text search of Hackage this coming weekend to check and see if it is feasible to ask downstream packages that use `WriterT`/`RWST` constructors to set upper bounds on `transformers`.



_______________________________________________
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
Ben Gamari | 20 May 15:11 2013
Picon

Re: Stricter WriterT (Part II)

Gabriel Gonzalez <gabriel439 <at> gmail.com> writes:

> I previously asked on this mailing list about getting a stricter WriterT 
> added to transformers here:
>
It seems that this thread has died an unfortunate premature death. I,
for one, would love to see this make its way upstream. Will this be
happening?

Cheers,

- Ben
David Luposchainsky | 20 May 16:01 2013

Re: Stricter WriterT (Part II)

The question was about a Writer that basically calls seq on the mappend
operation if I recall correctly? I'd be in on that.
A practical example that I frequently come across is having
Reader+State, but I can't use RWS because of the "mappend ()" thunk
buildup when using "RWS r () s".

+1

David
Gabriel Gonzalez | 20 May 17:00 2013
Picon

Re: Stricter WriterT (Part II)

On 05/20/2013 06:11 AM, Ben Gamari wrote:
> Gabriel Gonzalez<gabriel439 <at> gmail.com>  writes:
>
>    
>> I previously asked on this mailing list about getting a stricter WriterT
>> added to transformers here:
>>
>>      
> It seems that this thread has died an unfortunate premature death. I,
> for one, would love to see this make its way upstream. Will this be
> happening?
>
> Cheers,
>
> - Ben
>
>    
I agree.  We might optionally consider combining two changes to 
`transformers`:

* Adding the stricter `WriterT`
* Adding `EitherT`
Ross Paterson | 20 May 17:17 2013
Picon

Re: Stricter WriterT (Part II)

On Sun, Mar 17, 2013 at 09:18:13AM -0700, Gabriel Gonzalez wrote:
> So I propose that we add an additional stricter WriterT (under say,
> "Control.Monad.Trans.Writer.Stricter") which is internally
> implemented as StateT, but hide the constructor so we don't expose
> the implementation:
> 
> newtype WriterT w m a = WriterT { unWriterT :: w -> m (a, w) }

That would be slightly less transparent than the other transformers,
and it wouldn't be perfectly parallel to the existing versions of WriterT:
- the Applicative and Alternative instances would have different contexts
- there would be no Foldable or Traversable instances

On Tue, Mar 19, 2013 at 08:33:37PM -0400, Edward Kmett wrote:
> I use them fairly heavily, mostly so I can make packages that work with
> arbitrary transformer stacks.

There are several packages like this, that pass various stuff through all
the transformers.  Relatively few seem to use the strict writer for itself:

	alms darcswatch ghc-heap-view Glob GPipe-Collada Haschoo hbayes
	nemesis satchmo shake storable XmlHtmlWriter

I wonder if these users were expecting the linear behaviour that Gabriel
was exploring.

So perhaps the best thing would be to deprecate Writer.Strict in favour
of State.Strict.

Gmane