[Haskell-cafe] Stream fusion for Hackage

Roman Leshchinskiy rl at cse.unsw.edu.au
Mon Nov 19 06:30:11 EST 2007

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.


More information about the Libraries mailing list