Re: [Haskell-cafe] Stream fusion for Hackage
[redirected from haskell-cafe] On Sat, Nov 17, 2007 at 06:31:08PM -0800, Don Stewart wrote:
Just a quick announce: the stream fusion library for lists, that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year is now available on Hackage as a standalone package:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1...
The module Data.Stream clashes with a module in the Stream package (originally from the arrows package), and I think the latter is a more widely used notion of stream. Would you consider renaming Data.Stream and Control.Monad.Stream?
ross:
[redirected from haskell-cafe]
On Sat, Nov 17, 2007 at 06:31:08PM -0800, Don Stewart wrote:
Just a quick announce: the stream fusion library for lists, that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year is now available on Hackage as a standalone package:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1...
The module Data.Stream clashes with a module in the Stream package (originally from the arrows package), and I think the latter is a more widely used notion of stream. Would you consider renaming Data.Stream and Control.Monad.Stream?
Right, so how best to resolve this? Any name suggestions? -- Don
Hello Don, Sunday, November 18, 2007, 11:09:58 PM, you wrote:
widely used notion of stream. Would you consider renaming Data.Stream and Control.Monad.Stream?
Right, so how best to resolve this? Any name suggestions?
Data.List.Stream or Data.List.Fusion i think that adding module directly to Data directory will only increase name clash. how you will name module that adds stream fusion for ByteStrings? ;) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
bulat.ziganshin:
Hello Don,
Sunday, November 18, 2007, 11:09:58 PM, you wrote:
widely used notion of stream. Would you consider renaming Data.Stream and Control.Monad.Stream?
Right, so how best to resolve this? Any name suggestions?
Data.List.Stream or Data.List.Fusion
i think that adding module directly to Data directory will only increase name clash. how you will name module that adds stream fusion for ByteStrings? ;)
They all reuse the underlying Stream type, so bytestring will be unchanged on the interface. It will continue to use Data.ByteString.Fusion, which will import what is currently known as Data.Stream. -- Don
Don Stewart wrote:
ross:
[redirected from haskell-cafe]
On Sat, Nov 17, 2007 at 06:31:08PM -0800, Don Stewart wrote:
Just a quick announce: the stream fusion library for lists, that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year is now available on Hackage as a standalone package:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1...
The module Data.Stream clashes with a module in the Stream package (originally from the arrows package), and I think the latter is a more widely used notion of stream. Would you consider renaming Data.Stream and Control.Monad.Stream?
Right, so how best to resolve this? Any name suggestions?
I would suggest dropping the name 'stream' completely, or at least adding an adjective. There are several things named streams, and these fusion streams are not the most natural of them. Calling them 'streams' will only confuse people. Some suggestions: - Data.List.Fusable - Data.StreamFusion - Data.FusionStream - Data.UnfoldedStream Also, this module feels like an 'internal' module to me. Perhaps poluting the Data. or Control. hierarchy with it is not a good idea. It really belongs in some sort of 'Optimization.' or 'Internal.' hierarchy. Twan
twanvl:
Don Stewart wrote:
ross:
[redirected from haskell-cafe]
On Sat, Nov 17, 2007 at 06:31:08PM -0800, Don Stewart wrote:
Just a quick announce: the stream fusion library for lists, that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year is now available on Hackage as a standalone package:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1...
The module Data.Stream clashes with a module in the Stream package (originally from the arrows package), and I think the latter is a more widely used notion of stream. Would you consider renaming Data.Stream and Control.Monad.Stream?
Right, so how best to resolve this? Any name suggestions?
I would suggest dropping the name 'stream' completely, or at least adding an adjective. There are several things named streams, and these fusion streams are not the most natural of them. Calling them 'streams' will only confuse people.
Some suggestions: - Data.List.Fusable
The first is no good, as Data.Stream is not just for lists. Its a general sequence type after all, supporting automatic loop fusion.
- Data.StreamFusion - Data.FusionStream - Data.UnfoldedStream
So there's two issues here: 1) Where does the basic unfolded sequence type, described in the stream fusion paper live? data Stream a = forall s. Stream (s -> Step a s) s data Step a s = Yield a !s | Skip !s | Done And then, 2) where do variants of base data structures reimplemented in terms of these streams live? Currently, the former is Data.Stream, which conflicts with Wouter et al's natural infinite list type. Fair enough (though we did write the "stream fusion" paper first ;) It has to go somewhere under Data.* though. For part 2), currently we have Data.List.Stream for the fusible [a] variants, Data.ByteString and the Data.Array.Parallel stuff, all reusing the existing Data.Stream. I can imagine a fusible fingertree implementaiton eventually.
Also, this module feels like an 'internal' module to me. Perhaps poluting the Data. or Control. hierarchy with it is not a good idea. It really belongs in some sort of 'Optimization.' or 'Internal.' hierarchy.
This structure isn't internal though, you can program in it directly (as the MLton guys do), or implement your new sequence type on top of it, as bytestrings, ndp, and the stream-fusion modules do. So Internal et al is no good. -- Don
Don Stewart wrote:
So there's two issues here:
1) Where does the basic unfolded sequence type, described in the stream fusion paper live?
data Stream a = forall s. Stream (s -> Step a s) s
data Step a s = Yield a !s | Skip !s | Done
Why not have a Data.Fusion.* hierarchy and put everything having to do with stream fusion there? In any case, we'll need to significantly expand the library if it is to be usable for both lists and arrays/bytestrings due to different strictness of the data structures. The underlying stream data type stays the same but some of the combinators change.
And then, 2) where do variants of base data structures reimplemented in terms of these streams live?
The question is: will those eventually replace the current implementations? Roman
1) Where does the basic unfolded sequence type, described in the stream fusion paper live?
Why not have a Data.Fusion.* hierarchy and put everything having to do with stream fusion there?
It seems perfectly reasonable to me that ordinary users might want to program directly with this data structure, whether or not it ends up being fuseable. The problem with a name like "Data.Fusion" is that it describes the thing that the compiler does with this data structure, rather than the data structure itself. My suggestions for names would therefore be: Data.Unfold Data.Step Data.Pump Regards, Malcolm
Malcolm.Wallace:
1) Where does the basic unfolded sequence type, described in the stream fusion paper live?
Why not have a Data.Fusion.* hierarchy and put everything having to do with stream fusion there?
It seems perfectly reasonable to me that ordinary users might want to program directly with this data structure, whether or not it ends up being fuseable.
The problem with a name like "Data.Fusion" is that it describes the thing that the compiler does with this data structure, rather than the data structure itself.
My suggestions for names would therefore be: Data.Unfold Data.Step Data.Pump
How about Data.Fusion.Stream or Data.Stream.Fusion so you can at least see from the name you're getting stream fusion :) -- Don
On Mon, Nov 19, 2007 at 10:17:56AM +0000, Malcolm Wallace wrote:
1) Where does the basic unfolded sequence type, described in the stream fusion paper live?
Why not have a Data.Fusion.* hierarchy and put everything having to do with stream fusion there?
It seems perfectly reasonable to me that ordinary users might want to program directly with this data structure, whether or not it ends up being fuseable.
The problem with a name like "Data.Fusion" is that it describes the thing that the compiler does with this data structure, rather than the data structure itself.
My suggestions for names would therefore be: Data.Unfold Data.Step Data.Pump
How about Control.Stream? The stream-fusions combinators are in some way trying to capture the order of operations, while Wouter et al's Data.Stream is plain data. Stefan
The Control-vs-Data distinction is pretty fuzzy in lazy functional
programming, so I'd go for a more specific description, like Data.Step.
On Nov 19, 2007 4:55 PM, Stefan O'Rear
How about Control.Stream? The stream-fusions combinators are in some way trying to capture the order of operations, while Wouter et al's Data.Stream is plain data.
Stefan
On Sun, Nov 18, 2007 at 04:19:29PM -0800, Don Stewart wrote:
twanvl:
Don Stewart wrote:
ross:
The module Data.Stream clashes with a module in the Stream package Right, so how best to resolve this? Any name suggestions?
I would suggest dropping the name 'stream' completely, or at least adding an adjective. There are several things named streams, and these fusion streams are not the most natural of them. Calling them 'streams' will only confuse people.
Yes indeed.
Some suggestions: - Data.List.Fusable
The first is no good, as Data.Stream is not just for lists. Its a general sequence type after all, supporting automatic loop fusion.
It's not just for lists, but it is restricted to things that can be viewed as lists. Haskell data types are both inductive and coinductive (i.e. initial algebras and final coalgebras), so the standard System F encodings yield two views of each recursive type: mu x. T x ~= forall r. (T r -> r) -> r nu x. T x ~= exists s. (s, s -> T s) In the case of lists, the inductive view is the one used in foldr-build fusion. The coinductive view is what you're calling streams (ignoring the Skip constructor), but it's equivalent to the arguments of unfoldr. So if you say fusion, you should say whether you're using the inductive or coinductive view. Hence I think the name should include the elements Data, List and Coinductive (or Unfold as suggested by Malcolm).
Currently, the former is Data.Stream, which conflicts with Wouter et al's natural infinite list type. Fair enough (though we did write the "stream fusion" paper first ;)
Data.Stream has been in the arrows package (with the same meaning) for at least 4 years, but this use of "stream" is much older than that.
Ross Paterson wrote:
On Sun, Nov 18, 2007 at 04:19:29PM -0800, Don Stewart wrote:
twanvl:
Don Stewart wrote:
ross:
The module Data.Stream clashes with a module in the Stream package Right, so how best to resolve this? Any name suggestions? I would suggest dropping the name 'stream' completely, or at least adding an adjective. There are several things named streams, and these fusion streams are not the most natural of them. Calling them 'streams' will only confuse people.
Yes indeed.
Some suggestions: - Data.List.Fusable The first is no good, as Data.Stream is not just for lists. Its a general sequence type after all, supporting automatic loop fusion.
It's not just for lists, but it is restricted to things that can be viewed as lists.
Haskell data types are both inductive and coinductive (i.e. initial algebras and final coalgebras), so the standard System F encodings yield two views of each recursive type:
mu x. T x ~= forall r. (T r -> r) -> r nu x. T x ~= exists s. (s, s -> T s)
In the case of lists, the inductive view is the one used in foldr-build fusion. The coinductive view is what you're calling streams (ignoring the Skip constructor), but it's equivalent to the arguments of unfoldr. So if you say fusion, you should say whether you're using the inductive or coinductive view.
Hence I think the name should include the elements Data, List and Coinductive (or Unfold as suggested by Malcolm).
I have to disagree here. Our streams can be used to model both inductive (i.e. tail-strict) and coinductive lists. What data structure is being modelled is not a property of the Stream data type but rather of the stream operations. For inductive data types, we just have to make sure that streams are always fully consumed. Roman
On Mon, Nov 19, 2007 at 10:30:11PM +1100, Roman Leshchinskiy wrote:
I have to disagree here. Our streams can be used to model both inductive (i.e. tail-strict) and coinductive lists. What data structure is being modelled is not a property of the Stream data type but rather of the stream operations. For inductive data types, we just have to make sure that streams are always fully consumed.
I was saying that your "streams" are themselves coinductive objects. Is that controversial?
Ross Paterson wrote:
On Mon, Nov 19, 2007 at 10:30:11PM +1100, Roman Leshchinskiy wrote:
I have to disagree here. Our streams can be used to model both inductive (i.e. tail-strict) and coinductive lists. What data structure is being modelled is not a property of the Stream data type but rather of the stream operations. For inductive data types, we just have to make sure that streams are always fully consumed.
I was saying that your "streams" are themselves coinductive objects. Is that controversial?
They aren't recursive so in my view, they themselves are just as (co)inductive as, say, a function of type (a -> a). My point was that since they can faithfully model both inductive and coinductive types, putting them under a Coinductive hierarchy would be counterintuitive. Roman
On Tue, Nov 20, 2007 at 07:25:08PM +1100, Roman Leshchinskiy wrote:
Ross Paterson wrote:
I was saying that your "streams" are themselves coinductive objects. Is that controversial?
They aren't recursive so in my view, they themselves are just as (co)inductive as, say, a function of type (a -> a).
To quote your own paper, "stream fusion uses an explicit representation of the sequence co-structure [or unfolding]: the Stream type." The key property of System F encodings is that they encode a recursive type in a non-recursive form, and Stream (ignoring Skip) is the standard System F encoding of co-inductive lists.
Ross Paterson wrote:
On Tue, Nov 20, 2007 at 07:25:08PM +1100, Roman Leshchinskiy wrote:
Ross Paterson wrote:
I was saying that your "streams" are themselves coinductive objects. Is that controversial? They aren't recursive so in my view, they themselves are just as (co)inductive as, say, a function of type (a -> a).
To quote your own paper, "stream fusion uses an explicit representation of the sequence co-structure [or unfolding]: the Stream type." The key property of System F encodings is that they encode a recursive type in a non-recursive form, and Stream (ignoring Skip) is the standard System F encoding of co-inductive lists.
All true, but to me, there is a difference between encoding coinductive structure and being coinductive. After all, "encoding" is to a certain extent a matter of interpretation. Anyway, I guess we only disagree about terminology. Roman
Roman Leshchinskiy wrote:
Ross Paterson wrote:
Hence I think the name should include the elements Data, List and Coinductive (or Unfold as suggested by Malcolm).
I have to disagree here. Our streams can be used to model both inductive (i.e. tail-strict) and coinductive lists. What data structure is being modelled is not a property of the Stream data type but rather of the stream operations. For inductive data types, we just have to make sure that streams are always fully consumed.
Every inductive (=finite) list is also a coinductive (=potentially infinite) list but not vice-versa. So it's trivially true that if streams model coinductive types, they can also model inductive ones (in a language with _|_ that is, otherwise fold couldn't be expressed). Regards, apfelmus
participants (9)
-
apfelmus -
Bulat Ziganshin -
Conal Elliott -
Don Stewart -
Malcolm Wallace -
Roman Leshchinskiy -
Ross Paterson -
Stefan O'Rear -
Twan van Laarhoven