Proposal: Data.Stream

[Conor McBride]

Hi

On 9 Jul 2007, at 18:46, apfelmus wrote:

> Stefan O'Rear wrote:
>> On Mon, Jul 09, 2007 at 03:38:56PM +0200, Wouter Swierstra wrote:
>>>
>>> I just uploaded a fairly unspectacular package Data.Stream to  
>>> Hackage. It
>>> implements quite a few operations on streams (infinite lists)
>>
>> Unfortunately, there is a bit of a name collision here; Coutts,  
>> Stewart,
>> and Leshchinskiy are pushing for a completely unrelated  
>> Data.Stream to
>> be added to base.  (Theirs is a package of operations on lists  
>> defined
>> by generalized unfold operators.)
>
> How about Data.Colist for infinite lists :)

It's such a precarious business, this. But, by way of documentation,

data   List   x = Nil | Cons x (List x)
codata CoList x = Nil | Cons x (CoList x)
codata Stream x =       Cons x (Stream x)

Which of these things are what, if you're a scrupulous (co)programmer?

             | List       | CoList     | Stream
------------+------------+------------+------------
Functor     | Yes        | Yes        | Yes
------------+------------+------------+------------
Applicative | Yes-nondet | Yes-nondet |
             |            | Yes-zipmin | Yes-zip
------------+------------+------------+------------
Monad       | Yes-nondet | No         | Yes-zip
------------+------------+------------+------------
CoMonad     | No         | No         | Yes
------------+------------+------------+------------
Monoid      | Yes        | Yes        | No

By Yes-nondet, I mean monadic/applicative with respect to the
return/concatMap structure. By Yes-zipmin, I mean applicative
via a truncating zip operation. The stream monad is not the same as
the list monad: the stream join takes the diagonal of an infinite
matrix.

It's interesting to add columns for *nonempty* lists and colists, but  
I'll
leave that for another time. Similarly, I can think of a few more  
rows...

Anyhow, the point is this. The fact that Haskell's [] is big enough to
represent all of these things does not mean that [] is all we need in
the library. If a type is just a bucket to chuck data into, we should  
base
the library on leaf-labelled binary trees, with a special notation for
right-nested spines.

But we use types to indicate computational structure and to guide
the specialisation of overloaded operations (eg traverse) which exploit
that structure. Types tell us what the programs are: lists and streams
have different computational structure, hence different (co)programs.

I'm in favour of starting a separate stream library, and I would
expect it to diverge from the list library over time.

All the best

Conor