[Haskell-cafe] Stream fusion for Hackage

[Roman Leshchinskiy]

Ross Paterson wrote:
> 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).

I have to disagree here. Our streams can be used to model both inductive 
(i.e. tail-strict) and coinductive lists. What data structure is being 
modelled is not a property of the Stream data type but rather of the 
stream operations. For inductive data types, we just have to make sure 
that streams are always fully consumed.

Roman