Proposal: Data.Stream

[Wouter Swierstra]

> What is the advantage of knowing that a list is infinite?

There is plenty of overlap with the *functions* defined in Data.List,  
but the *data types* are really different. Conor emphasizes this  
point by tabulating the different structure Streams, Lists and  
CoLists carry.

This distinction makes perfect sense if you distinguish between data  
and codata. Languages such as Coq have separate types for (inductive)  
lists and (coinductive) streams. See the Coq standard libraries for  
instance:

http://coq.inria.fr/V8.1/stdlib/Coq.Lists.List.html
http://coq.inria.fr/V8.1/stdlib/Coq.Lists.Streams.html

I've encountered the need for streams, as opposed to lists, on  
several occassions. I know that Ross Paterson's arrow library defines  
a Data.Stream as well (used in Control.Arrows.Internal). I'm sure  
these aren't the only places where you really want to use streams  
instead of lists.

As far as name clashes are concerned, Andres Loeh suggested  
Codata.Stream. I realize this requires the creation of a new category  
of libraries, but its the best suggestion I've heard so far.

   Wouter