Proposal: Data.Stream

Conor McBride ctm at
Mon Jul 9 15:53:18 EDT 2007


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

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

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  
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


More information about the Libraries mailing list