[Haskell-cafe] Stream fusion for Hackage

[Ross Paterson]

On Sun, Nov 18, 2007 at 04:19:29PM -0800, Don Stewart wrote:
> twanvl:
> > Don Stewart wrote:
> > >ross:
> > >>The module Data.Stream clashes with a module in the Stream package
> > >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.

Yes indeed.

> > 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.

It's not just for lists, but it is restricted to things that can be
viewed as lists.

Haskell data types are both inductive and coinductive (i.e. initial
algebras and final coalgebras), so the standard System F encodings yield
two views of each recursive type:

	mu x. T x  ~=  forall r. (T r -> r) -> r
	nu x. T x  ~=  exists s. (s, s -> T s)

In the case of lists, the inductive view is the one used in foldr-build
fusion.  The coinductive view is what you're calling streams (ignoring
the Skip constructor), but it's equivalent to the arguments of unfoldr.
So if you say fusion, you should say whether you're using the inductive
or coinductive view.

Hence I think the name should include the elements Data, List and
Coinductive (or Unfold as suggested by Malcolm).

> 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 ;)

Data.Stream has been in the arrows package (with the same meaning) for
at least 4 years, but this use of "stream" is much older than that.