Re: [Haskell-cafe] Stream fusion for Hackage

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

Re: [Haskell-cafe] Stream fusion for Hackage

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

Re: [Haskell-cafe] Stream fusion for Hackage

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

Re[2]: [Haskell-cafe] Stream fusion for Hackage

Bulat Ziganshin-2
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:[hidden email]

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

Re: [Haskell-cafe] Stream fusion for Hackage

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

Re: [Haskell-cafe] Stream fusion for Hackage

Twan van Laarhoven
In reply to this post by Don Stewart-2
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.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
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] Stream fusion for Hackage

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

Re: [Haskell-cafe] Stream fusion for Hackage

Roman Leshchinskiy
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

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

Re: [Haskell-cafe] Stream fusion for Hackage

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

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

Re: [Haskell-cafe] Stream fusion for Hackage

Ross Paterson
In reply to this post by Don Stewart-2
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.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] Stream fusion for Hackage

Roman Leshchinskiy
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

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

Re: [Haskell-cafe] Stream fusion for Hackage

Don Stewart-2
In reply to this post by Malcolm Wallace
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
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] Stream fusion for Hackage

Stefan O'Rear
In reply to this post by Malcolm Wallace
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

_______________________________________________
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: [Haskell-cafe] Stream fusion for Hackage

Conal Elliott
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 < [hidden email]> wrote:

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



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

Re: [Haskell-cafe] Stream fusion for Hackage

Ross Paterson
In reply to this post by Roman Leshchinskiy
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?
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] Stream fusion for Hackage

Roman Leshchinskiy
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

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

Re: [Haskell-cafe] Stream fusion for Hackage

Heinrich Apfelmus
In reply to this post by Roman Leshchinskiy
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

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

Re: [Haskell-cafe] Stream fusion for Hackage

Ross Paterson
In reply to this post by Roman Leshchinskiy
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.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] Stream fusion for Hackage

Roman Leshchinskiy
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

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