Proposal: Data.Stream

[Roman Leshchinskiy]

Wouter Swierstra wrote:
>>>
>>> I'm in favour of starting a separate stream library, and I would
>>> expect it to diverge from the list library over time.
>>
>> I agree: this should probably be a separate library for now, until we
>> see how far it grows. There's an awful lot of other things not in base:
>> queues, difference lists, comonads, that live outside base, and I'm not
>> sure there's a strong enough case yet that this should go into base.
> 
> I think you're taking Conor's quote out of context. If I understand it 
> correctly, he's replying to Neil Mitchell's post; he is arguing for a 
> separate library different from Data.List. I don't think he objects to 
> including it in base.
> 
> Conor makes a strong case for separating lists and streams: they are 
> different types, with fundamentally different properties. I don't claim 
> that the proposed Stream library is the final word on the subject, but 
> it is a theoretically solid and the content is completely 
> uncontroversial. If nothing else, it is a starting point for encouraging 
> more coinductive Haskell programming. For that reason, I'd argue for 
> including it in the standard distribution.

In general, I don't think there is a "standard" definition of a stream 
datatype. IIUC, you see streams as necessarily infinite but there are 
other perfectly valid interpretations. Stream is simply a very broad 
term which means too many different things. In particular, I don't see 
why our Stream data type doesn't model streams. Anyway, IMHO to avoid 
confusion we shouldn't have a standard stream type at all. And, as 
Stefan O'Rear has pointed out, a non-base package probably shouldn't put 
its modules under Data (unless, perhaps, it is under Data.<package>); in 
any case, the package name should appear somewhere in the path.

> I am not too concerned whether or not this library should go into base 
> or a separate package. I'd be happy to settle for Codata.Stream. This is 
> easy to separate from base and does not cause any conflicts. Other 
> libraries can be added to the Codata package, as we see fit.
> 
> I would argue against calling the ByteString package Data.Stream. As 
> tempting as it may be, the package is not about streams, but colists.

I have to admit that I don't really understand the distinction between 
Haskell's lists and colists (or, in general, datatypes in Haskell and 
codatatypes). To me, lists are inductive and colists are coinductive, 
i.e., the former are the least and the latter the greatest fixed point 
of the underlying functor. Thus, Haskell's list datatype actually models 
colists (and algebraic datatypes in Haskell are coinductive by default). 
This thread seems to implicitly assume a different interpretation of the 
prefix "co" but I don't really understand what this interpretation is.

As to Data.Stream, I don't think that the ByteString library actually 
includes a module with that name  Our stream fusion based list library 
does but that's really quite experimental and not really released, I 
think. However, our streams will have to go into base at some point as 
they are already used by the ByteString and NDP packages (even though 
each has its own copy) and we plan on using them for Data.Array and 
friends as well. The module doesn't really have to be called 
Data.Stream, though.

Roman