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