snip

Thanks for the link, Stefan. That's exactly what I was looking for. I've created a ticket and will add the corresponding darcs patch shortly. On 9 Jul 2007, at 19:46, apfelmus wrote:

...

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

The problem with calling it Colist, is that a Colist can still have a base case. I consider Colists the same as "lazy lists", that Haskell programmers are familiar with. Streams on the other hand, do *not* have a base case and are necessarily infinite. I realize there's a bit of a naming conflict with Don, Duncan, and Roman's "Data.List.Stream". Clearly, their library should have been called "Data.List.ImpredicativeChurchEncodingOfNuX.OnePlusATimesX" :) On a more serious note, this proposal has no chance if we can't agree no some name. I could almost settle for "Data.Infinite.Stream" or maybe even "Data.Infinite.List". I'd welcome any other suggestions. Wouter

Hi Wouter,

I just uploaded a fairly unspectacular package Data.Stream to Hackage. It implements quite a few operations on streams (infinite lists), analogous to those defined in Data.List. Sometimes it is just good to know a list is infinite.

What is the advantage of knowing that a list is infinite? Are these versions just identical to the Data.List versions, but you know you won't encounter [] ? If so, I'm not sure there is a pressing need for this. I would have thought a much more common problem is telling the difference between an empty list and a non-empty list, rather than an infinite list and another type of list. I'm not saying that its not useful, I'm just not sure it deserves to be in the base libraries. We could add a multitude of different data types, each of which is "a list by some other name", but we'd probably end up confusing users more than helping them. As a related point, if you do use infinite lists, and are worried that your operations might cause a pattern-match error, Catch will detect this and prove it for you: http://www-users.cs.york.ac.uk/~ndm/catch/ Thanks Neil

On Mon, Jul 09, 2007 at 10:51:35PM +0200, Wouter Swierstra wrote:

As far as name clashes are concerned, Andres Loeh suggested Codata.Stream. I realize this requires the creation of a new category of libraries, but its the best suggestion I've heard so far.

Currenly, Haskell package main module names almost invariably take the form Data.* for some value of *. This utterly defeats the point of a hierarchy! I'd like to see *lots* more top level categories, on the order of sqrt(packages in hackage). Stefan

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

...

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.

I think you're taking Conor's quote out of context. If I understand it correctly, he's replying to Neil Mitchell's post; he is arguing for a separate library different from Data.List. I don't think he objects to including it in base. Conor makes a strong case for separating lists and streams: they are different types, with fundamentally different properties. I don't claim that the proposed Stream library is the final word on the subject, but it is a theoretically solid and the content is completely uncontroversial. If nothing else, it is a starting point for encouraging more coinductive Haskell programming. For that reason, I'd argue for including it in the standard distribution. I am not too concerned whether or not this library should go into base or a separate package. I'd be happy to settle for Codata.Stream. This is easy to separate from base and does not cause any conflicts. Other libraries can be added to the Codata package, as we see fit. I would argue against calling the ByteString package Data.Stream. As tempting as it may be, the package is not about streams, but colists. There's quite some literature on the subject - see for instance Tarmo Uustalu's "Essence of Data Flow Programming" http://cs.ioc.ee/~tarmo/ papers/essence.pdf, numerous papers by Jan Rutten (http:// homepages.cwi.nl/~janr/papers/, for instance http://homepages.cwi.nl/ ~janr/papers/files-of-papers/CRM.pdf), various proceedings of CALCO, etc. I can understand that Stream sounds quite punchy and suitably coinductive, but calling this library Data.Stream will confuse certain people. I don't want to sound at all negative: I think the library is nothing short of phenomenal and "by any other name would smell as sweet". Best, Wouter

Roman,

I have to admit that I don't really understand the distinction between Haskell's lists and colists (or, in general, datatypes in Haskell and codatatypes). To me, lists are inductive and colists are coinductive, i.e., the former are the least and the latter the greatest fixed point of the underlying functor. Thus, Haskell's list datatype actually models colists (and algebraic datatypes in Haskell are coinductive by default). This thread seems to implicitly assume a different interpretation of the prefix "co" but I don't really understand what this interpretation is.

In Haskell, coinductive types and inductive types coincide. So, Haskell's [] models both lists and colists. Cheers, Stefan

In general, I don't think there is a "standard" definition of a stream datatype. IIUC, you see streams as necessarily infinite but there are other perfectly valid interpretations. Stream is simply a very broad term which means too many different things. In particular, I don't see why our Stream data type doesn't model streams.

I have to admit that, in general, "stream" can mean a lot of different things. A quick google gives all kinds of results, from streaming media to bandwidth benchmarks. However, there is quite a lot of research, closely related to functional programming, with a clear consensus of what a stream is: \nu X . A * X (or equivalently, functions from Nat -> A) Personally, I think this gives a very clear definition of what a stream is that leaves nothing open to interpretation. Of course people are free to call their data types whatever they like, but in this instance it may be advisable to at least be aware of any related work. Of course, your streams (what I would call colists) can be used to model this type. There are very compelling reasons not to do this: streams are a comonad, colists are not; streams and colists have are really different instances of Monad (just look at the definition of return for both cases); colists are a monoid, streams are not; I'm sure Conor can come up with plenty of other reasons. The important thing is, although you can model streams using colists (I'm using my terminology here), it may not be desirable to do so. It can sometimes pay to be as precise as possible about your types.

I have to admit that I don't really understand the distinction between Haskell's lists and colists (or, in general, datatypes in Haskell and codatatypes). To me, lists are inductive and colists are coinductive, i.e., the former are the least and the latter the greatest fixed point of the underlying functor. Thus, Haskell's list datatype actually models colists (and algebraic datatypes in Haskell are coinductive by default). This thread seems to implicitly assume a different interpretation of the prefix "co" but I don't really understand what this interpretation is.

That's exactly the way I think about this as well. In the context of Haskell, the distinction is not so clear. When you write "data" as a programmer, you sometimes really mean codata (as in my Stream type). On the other hand, there are occassions where you have an (implicit) invariant in your head stating you will never construct infinite terms, and hence it's safe to assume that a fold will terminate, for instance. Then you really mean data - and not codata. Haskell does not support this separation: both data and codata are introduced by the same language construct. It's a real pity sometimes; if we really care about the types of our programs, I think this is a distinction worth making. All the best, Wouter This message has been checked for viruses but the contents of an attachment may still contain software viruses, which could damage your computer system: you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation.

Hi folks On 10 Jul 2007, at 00:05, Donald Bruce Stewart wrote:

stefanor:

...

On Mon, Jul 09, 2007 at 03:38:56PM +0200, Wouter Swierstra wrote:

...

Dear all,

I just uploaded a fairly unspectacular package Data.Stream to Hackage. It implements quite a few operations on streams (infinite lists), analogous to those defined in Data.List. Sometimes it is just good to know a list is infinite.

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

He's talking about this module, btw,

http://www.cse.unsw.edu.au/~dons/code/streams/list/Data/Stream.hs

This looks like lovely stuff, but I'm not sure Stream is the right name. This is a very cunning CoList package, by the looks of things, exploiting the key computational structure of codata, namely being built from coalgebras. But maybe I should shut up, as I always lose fights about names. Cheers Conor

On Fri, Jul 13, 2007 at 11:18:27AM +1000, Donald Bruce Stewart wrote:

igloo:

...

On Mon, Jul 09, 2007 at 03:38:56PM +0200, Wouter Swierstra wrote:

...

* Hackage homepage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Stream-0.1

fairly uncontroversial, and would like to see it added to base (I realize that there are also proposals to clean up base to speed up the build of ghc),

Yes indeed; I don't see any reason for adding this to the base library while we're trying to make base smaller.

...

or at least, the standard libraries.

I'm not sure what you mean by "the standard libraries". It wouldn't be needed to build GHC, so it wouldn't be a GHC "core lib".

Other than that, if it's in hackage then it's as standard as any other library!

A "stream" (or "colist" or whatever) package seems reasonable to me.

(The http://www.cse.unsw.edu.au/~dons/code/streams/list/Data/Stream.hs module also looks too specific to use such a generic name, in my opinion).

Yes, I agree. Probably if it will be the base for fusion in ndp arrays, bytestrings and lists, we can find a tag to put between Data.* and *.Stream.

What does Data. mean in a language where almost everything is a data type? I think we should move abolish that subtree entirely, moving the major subtrees (Binary, Generics, Array, ...) to top level, and creating a bunch of new categories (Numeric, Collection, etc) for the remaining modules. (ByteString can go in Text) Stefan

igloo:

...

I'm not sure what you mean by "the standard libraries". It wouldn't be needed to build GHC, so it wouldn't be a GHC "core lib".

Other than that, if it's in hackage then it's as standard as any other library!

There does seem to be another level of "standard-ness" than this. Specifically, it would involve the library being distributed with GHC distributions and included in the documentation at http://haskell.org/ghc/docs/latest/html/libraries/. The base split is great, but I hope that it doesn't mean the standard libraries (in this sense) are being phased out, or that libraries or documentation will be made harder for Haskell newcomers to find and use. -- Chris Smith

Hi

But why do libraries like mtl or QuickCheck work "out of the box" (on my distribution) without having installed them from Hackage?

Your distribution has chosen to include them. In general, the only package which is guaranteed to be present is base, plus filepath from 6.6.1 onwards, plus many fragments of base from 6.8 onwards.

Ideally, that's where I'd like to see a separate package for Codata.Stream pop up.

Is it fair to say that your intention is not to give a level of blessing or whatever to this package, but to lower the barrier to use for your library? If so, things like cabal-install will nearly eliminate the difference between libraries shipped and libraries installed - wait for the tools to catch up and bundling won't be necessary. Thanks Neil