[Haskell-cafe] Stream fusion for Hackage

[Don Stewart]

twanvl:
> Don Stewart wrote:
> 
> >ross:
> >
> >>[redirected from haskell-cafe]
> >>
> >>On Sat, Nov 17, 2007 at 06:31:08PM -0800, Don Stewart wrote:
> >>
> >>>Just a quick announce: the stream fusion library for lists, 
> >>>that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year
> >>>is now available on Hackage as a standalone package:
> >>>
> >>>   http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1
> >>
> >>The module Data.Stream clashes with a module in the Stream package
> >>(originally from the arrows package), and I think the latter is a more
> >>widely used notion of stream.  Would you consider renaming Data.Stream
> >>and Control.Monad.Stream?
> >
> >Right, so how best to resolve this? Any name suggestions?
> 
> I would suggest dropping the name 'stream' completely, or at least 
> adding an adjective. There are several things named streams, and these 
> fusion streams are not the most natural of them. Calling them 'streams' 
> will only confuse people.
> 
> Some suggestions:
>  - Data.List.Fusable

The first is no good, as Data.Stream is not just for lists. Its a
general sequence type after all, supporting automatic loop fusion.

>  - Data.StreamFusion
>  - Data.FusionStream
>  - Data.UnfoldedStream

So there's two issues here:

1) Where does the basic unfolded sequence type, described in the stream
fusion paper live?

        data Stream a = forall s. Stream (s -> Step a s) s             

        data Step a s = Yield a !s
                      | Skip    !s
                      | Done

And then, 2) where do variants of base data structures reimplemented in
terms of these streams live?
 
Currently, the former is Data.Stream, which conflicts with Wouter et
al's natural infinite list type.  Fair enough (though we did write the
"stream fusion" paper first ;) It has to go somewhere under Data.*  though.


For part 2), currently we have Data.List.Stream for the fusible [a]
variants, Data.ByteString and the Data.Array.Parallel stuff, all reusing
the existing Data.Stream. I can imagine a fusible fingertree
implementaiton eventually.

> Also, this module feels like an 'internal' module to me. Perhaps 
> poluting the Data. or Control. hierarchy with it is not a good idea. It 
> really belongs in some sort of 'Optimization.' or 'Internal.' hierarchy.

This structure isn't internal though, you can program in it directly (as
the MLton guys do), or implement your new sequence type on top of it, as
bytestrings, ndp, and the stream-fusion modules do. So Internal et al is
no good.

-- Don