Proposal: Data.Stream
Donald Bruce Stewart
dons at cse.unsw.edu.au
Mon Jul 9 22:07:14 EDT 2007
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
More information about the Libraries
mailing list