Proposal: Data.Stream

[Donald Bruce Stewart]

ctm:
> 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.

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.

A standalone package would be my preference.

-- Don