Proposal: Data.Stream

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
26 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Data.Stream

Stefan O'Rear
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

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Data.Stream

Malcolm Wallace
Stefan O'Rear <[hidden email]> wrote:

> What does Data. mean in a language where almost everything is a data
> type?

And I thought in Haskell almost everything was a function...

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

I couldn't disagree more strongly.  _Very_ few libraries are about
providing general-purpose data structures.  The vast majority of
libraries are task-oriented: OpenGL for graphical rendering,
HaXml/HXT/pretty for document processing, HUnit/QuickCheck for testing,
process/unix/win32/filepath/directory for accessing OS facilities,
the list goes on.

Looking at
  http://www.haskell.org/ghc/docs/latest/html/libraries/index.html
the Data.* hierarchy is a mere 2/11th of the modules listed (which
admittedly covers only a tiny selection of packages available, but these
are the ones distributed with ghc).

Regards,
    Malcolm
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Data.Stream

Wouter Swierstra
In reply to this post by Roman Leshchinskiy
> 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.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Data.Stream

Wouter Swierstra
In reply to this post by Ian Lynagh
Hi Ian,
>
>> 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!

Thanks for clearing that up.

But why do libraries like mtl or QuickCheck work "out of the box" (on  
my distribution) without having installed them from Hackage? Maybe  
this is just me being a bit thick, but there seems to be at least  
several packages, beyond base, that come bundled with ghc. That's  
what I'd refer to as "standard libraries" - the term comes from the  
link to http://haskell.cs.yale.edu/ghc/docs/latest/html/libraries/ 
index.html on the haskell.org frontpage.

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

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.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Data.Stream

Neil Mitchell
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
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Data.Stream

Chris Smith-39
In reply to this post by Donald Bruce Stewart
> 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

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
12