Proposal: Add a few extra members to Foldable and Traversable classes

David Feuer

18 Sep 2014 18 Sep '14

5:37 p.m.

To go along with Herbert Valerio Riedel's moving functions from Foldable and Traversable to Prelude, I realized that `null` and `size` make sense for all Foldables; Reid W. Barton noted that these can have optimized implementations for many containers. He also noted that scanl1 and scanr1 make sense for general Traversables. I therefore propose: Add `null` and `size` to the Foldable class. Default implementations: null = foldr (\_ _ -> False) True size = foldl' (\acc _ -> acc+1) 0 Add `scanl1` and `scanr1` to the Traversable class. Default implementations are a little less simple. David

Attachments:

attachment.html (text/html — 734 bytes)

Show replies by date

Edward Kmett

18 Sep 18 Sep

5:43 p.m.

Choosing the name `size` isn't free. If we chose `length` then the existing code continues to work, code that was hiding it on import continues to hide it and you don't get conflicts. Picking 'size' is compatible with common practice, but means a ton of modules would break. Given the two solutions, one that doesn't break anything and one that does, with negligible differences between them otherwise, I'd prefer the one that causes the least amount of pain. -Edward On Thu, Sep 18, 2014 at 5:37 PM, David Feuer wrote:

...

To go along with Herbert Valerio Riedel's moving functions from Foldable and Traversable to Prelude, I realized that `null` and `size` make sense for all Foldables; Reid W. Barton noted that these can have optimized implementations for many containers. He also noted that scanl1 and scanr1 make sense for general Traversables. I therefore propose:

Add `null` and `size` to the Foldable class. Default implementations:

null = foldr (\_ _ -> False) True

size = foldl' (\acc _ -> acc+1) 0

Add `scanl1` and `scanr1` to the Traversable class. Default implementations are a little less simple.

David

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

David Feuer

5:49 p.m.

R.W. Barton was having trouble spitting out the words "length of a set", and the same holds for all sorts of other things, but unfortunately I think you're right. Proposal amended: put length in the Foldable class. On Thu, Sep 18, 2014 at 5:43 PM, Edward Kmett wrote:

...

Choosing the name `size` isn't free.

If we chose `length` then the existing code continues to work, code that was hiding it on import continues to hide it and you don't get conflicts.

Picking 'size' is compatible with common practice, but means a ton of modules would break.

Given the two solutions, one that doesn't break anything and one that does, with negligible differences between them otherwise, I'd prefer the one that causes the least amount of pain.

-Edward

On Thu, Sep 18, 2014 at 5:37 PM, David Feuer wrote:

...
To go along with Herbert Valerio Riedel's moving functions from Foldable and Traversable to Prelude, I realized that `null` and `size` make sense for all Foldables; Reid W. Barton noted that these can have optimized implementations for many containers. He also noted that scanl1 and scanr1 make sense for general Traversables. I therefore propose:

Add `null` and `size` to the Foldable class. Default implementations:

null = foldr (\_ _ -> False) True

size = foldl' (\acc _ -> acc+1) 0

Add `scanl1` and `scanr1` to the Traversable class. Default implementations are a little less simple.

David

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

David Feuer

6:20 p.m.

I'm sorry to send so many emails, but elem should also be moved into the Foldable class to support optimized versions for searchable containers. We should also move maximum and minimum into the Foldable class to allow optimized versions. We need to settle the semantics of these anyway—Data.List.{maximum,minimum} and Data.Foldable.{maximum,minimum} currently behave differently (left-to-right vs. right-to-left). I think we want "whatever's best", which thankfully leaves the list version with its current semantics. David On Thu, Sep 18, 2014 at 5:49 PM, David Feuer wrote:

...

R.W. Barton was having trouble spitting out the words "length of a set", and the same holds for all sorts of other things, but unfortunately I think you're right. Proposal amended: put length in the Foldable class.

On Thu, Sep 18, 2014 at 5:43 PM, Edward Kmett wrote:

...
Choosing the name `size` isn't free.

If we chose `length` then the existing code continues to work, code that was hiding it on import continues to hide it and you don't get conflicts.

Picking 'size' is compatible with common practice, but means a ton of modules would break.

Given the two solutions, one that doesn't break anything and one that does, with negligible differences between them otherwise, I'd prefer the one that causes the least amount of pain.

-Edward

On Thu, Sep 18, 2014 at 5:37 PM, David Feuer wrote:

...
To go along with Herbert Valerio Riedel's moving functions from Foldable and Traversable to Prelude, I realized that `null` and `size` make sense for all Foldables; Reid W. Barton noted that these can have optimized implementations for many containers. He also noted that scanl1 and scanr1 make sense for general Traversables. I therefore propose:

Add `null` and `size` to the Foldable class. Default implementations:

null = foldr (\_ _ -> False) True

size = foldl' (\acc _ -> acc+1) 0

Add `scanl1` and `scanr1` to the Traversable class. Default implementations are a little less simple.

David

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

David Feuer

7:26 p.m.

After discussing these matters some more with Edward Kmett and Reid Barton, it appears the following makes sense: Add the following to Foldable: length—often stored as a separate field for O(1) access null—called very often and slightly faster than foldr (\_ _ -> False) True for some containers toList—may be the identity or nearly so, and this fact may not be statically available to the foldr/id rule sum, product—may be cached internally in tree nodes for fast update, giving O(1) access; may be calculated in parallel. maximum, minimum—O(n) for a search tree; O(1) for a finger tree. elem—O(log n) for search trees; likely better for hash tables and such. Don't add anything to Traversable, because scanl1 and scanr1 are not worth the extra dictionary weight. On Thu, Sep 18, 2014 at 6:20 PM, David Feuer wrote:

...

I'm sorry to send so many emails, but elem should also be moved into the Foldable class to support optimized versions for searchable containers. We should also move maximum and minimum into the Foldable class to allow optimized versions. We need to settle the semantics of these anyway—Data.List.{maximum,minimum} and Data.Foldable.{maximum,minimum} currently behave differently (left-to-right vs. right-to-left). I think we want "whatever's best", which thankfully leaves the list version with its current semantics.

David

On Thu, Sep 18, 2014 at 5:49 PM, David Feuer wrote:

...
R.W. Barton was having trouble spitting out the words "length of a set", and the same holds for all sorts of other things, but unfortunately I think you're right. Proposal amended: put length in the Foldable class.

On Thu, Sep 18, 2014 at 5:43 PM, Edward Kmett wrote:

...
Choosing the name `size` isn't free.

If we chose `length` then the existing code continues to work, code that was hiding it on import continues to hide it and you don't get conflicts.

Picking 'size' is compatible with common practice, but means a ton of modules would break.

Given the two solutions, one that doesn't break anything and one that does, with negligible differences between them otherwise, I'd prefer the one that causes the least amount of pain.

-Edward

On Thu, Sep 18, 2014 at 5:37 PM, David Feuer wrote:

...
To go along with Herbert Valerio Riedel's moving functions from Foldable and Traversable to Prelude, I realized that `null` and `size` make sense for all Foldables; Reid W. Barton noted that these can have optimized implementations for many containers. He also noted that scanl1 and scanr1 make sense for general Traversables. I therefore propose:

Add `null` and `size` to the Foldable class. Default implementations:

null = foldr (\_ _ -> False) True

size = foldl' (\acc _ -> acc+1) 0

Add `scanl1` and `scanr1` to the Traversable class. Default implementations are a little less simple.

David

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

John Lato

7:49 p.m.

Enthusiastically +1 Every package I know that provides something like Foldable (ListLike, mono-traversable, a few others) includes these, largely for performance reasons. I'm not entirely convinced with the reasoning that sum and product may be calculated in parallel though. IMHO for structures that care about parallel reductions, I think foldMap should be the main entry point. But I can see these might be cached. John L. On Thu, Sep 18, 2014 at 4:26 PM, David Feuer wrote:

...

After discussing these matters some more with Edward Kmett and Reid Barton, it appears the following makes sense:

Add the following to Foldable: length—often stored as a separate field for O(1) access null—called very often and slightly faster than foldr (\_ _ -> False) True for some containers toList—may be the identity or nearly so, and this fact may not be statically available to the foldr/id rule sum, product—may be cached internally in tree nodes for fast update, giving O(1) access; may be calculated in parallel. maximum, minimum—O(n) for a search tree; O(1) for a finger tree. elem—O(log n) for search trees; likely better for hash tables and such.

Don't add anything to Traversable, because scanl1 and scanr1 are not worth the extra dictionary weight.

On Thu, Sep 18, 2014 at 6:20 PM, David Feuer wrote:

...
I'm sorry to send so many emails, but elem should also be moved into the Foldable class to support optimized versions for searchable containers. We should also move maximum and minimum into the Foldable class to allow optimized versions. We need to settle the semantics of these anyway—Data.List.{maximum,minimum} and Data.Foldable.{maximum,minimum} currently behave differently (left-to-right vs. right-to-left). I think we want "whatever's best", which thankfully leaves the list version with its current semantics.

David

On Thu, Sep 18, 2014 at 5:49 PM, David Feuer wrote:

...
R.W. Barton was having trouble spitting out the words "length of a set", and the same holds for all sorts of other things, but unfortunately I think you're right. Proposal amended: put length in the Foldable class.

On Thu, Sep 18, 2014 at 5:43 PM, Edward Kmett wrote:

...
Choosing the name `size` isn't free.

If we chose `length` then the existing code continues to work, code that was hiding it on import continues to hide it and you don't get conflicts.

Picking 'size' is compatible with common practice, but means a ton of modules would break.

Given the two solutions, one that doesn't break anything and one that does, with negligible differences between them otherwise, I'd prefer the one that causes the least amount of pain.

-Edward

On Thu, Sep 18, 2014 at 5:37 PM, David Feuer wrote:

...
To go along with Herbert Valerio Riedel's moving functions from Foldable and Traversable to Prelude, I realized that `null` and `size` make sense for all Foldables; Reid W. Barton noted that these can have optimized implementations for many containers. He also noted that scanl1 and scanr1 make sense for general Traversables. I therefore propose:

Add `null` and `size` to the Foldable class. Default implementations:

null = foldr (\_ _ -> False) True

size = foldl' (\acc _ -> acc+1) 0

Add `scanl1` and `scanr1` to the Traversable class. Default implementations are a little less simple.

David

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Edward Kmett

7:59 p.m.

sum and product inclusion mostly allows you do a.) do something smarter than foldl or b.) deal with containers that do things like store prefix sums. In general you can view the operations as being defined as given toList = foldr (:) [] then all the other operations as giving results to match e.g. maximum = maximum . toList with possibly asymptotically much more efficient implementations. Including toList in the class permits lists and many containers that include a list directly to convert to the 'view' type of being a list in O(1). -Edward On Thu, Sep 18, 2014 at 7:49 PM, John Lato wrote:

...

Enthusiastically +1

Every package I know that provides something like Foldable (ListLike, mono-traversable, a few others) includes these, largely for performance reasons.

I'm not entirely convinced with the reasoning that sum and product may be calculated in parallel though. IMHO for structures that care about parallel reductions, I think foldMap should be the main entry point. But I can see these might be cached.

John L.

On Thu, Sep 18, 2014 at 4:26 PM, David Feuer wrote:

...
After discussing these matters some more with Edward Kmett and Reid Barton, it appears the following makes sense:

Add the following to Foldable: length—often stored as a separate field for O(1) access null—called very often and slightly faster than foldr (\_ _ -> False) True for some containers toList—may be the identity or nearly so, and this fact may not be statically available to the foldr/id rule sum, product—may be cached internally in tree nodes for fast update, giving O(1) access; may be calculated in parallel. maximum, minimum—O(n) for a search tree; O(1) for a finger tree. elem—O(log n) for search trees; likely better for hash tables and such.

Don't add anything to Traversable, because scanl1 and scanr1 are not worth the extra dictionary weight.

On Thu, Sep 18, 2014 at 6:20 PM, David Feuer wrote:

...
I'm sorry to send so many emails, but elem should also be moved into the Foldable class to support optimized versions for searchable containers. We should also move maximum and minimum into the Foldable class to allow optimized versions. We need to settle the semantics of these anyway—Data.List.{maximum,minimum} and Data.Foldable.{maximum,minimum} currently behave differently (left-to-right vs. right-to-left). I think we want "whatever's best", which thankfully leaves the list version with its current semantics.

David

On Thu, Sep 18, 2014 at 5:49 PM, David Feuer wrote:

...
R.W. Barton was having trouble spitting out the words "length of a set", and the same holds for all sorts of other things, but unfortunately I think you're right. Proposal amended: put length in the Foldable class.

On Thu, Sep 18, 2014 at 5:43 PM, Edward Kmett wrote:

...
Choosing the name `size` isn't free.

If we chose `length` then the existing code continues to work, code that was hiding it on import continues to hide it and you don't get conflicts.

Picking 'size' is compatible with common practice, but means a ton of modules would break.

Given the two solutions, one that doesn't break anything and one that does, with negligible differences between them otherwise, I'd prefer the one that causes the least amount of pain.

-Edward

On Thu, Sep 18, 2014 at 5:37 PM, David Feuer wrote:

...
To go along with Herbert Valerio Riedel's moving functions from Foldable and Traversable to Prelude, I realized that `null` and `size` make sense for all Foldables; Reid W. Barton noted that these can have optimized implementations for many containers. He also noted that scanl1 and scanr1 make sense for general Traversables. I therefore propose:

Add `null` and `size` to the Foldable class. Default implementations:

null = foldr (\_ _ -> False) True

size = foldl' (\acc _ -> acc+1) 0

Add `scanl1` and `scanr1` to the Traversable class. Default implementations are a little less simple.

David

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

David Feuer

8:37 p.m.

I'm sorry for confusing things. I had wondered why Foldable uses a right fold instead of a left fold, and the parallel thing was the answer to that. On Thu, Sep 18, 2014 at 7:59 PM, Edward Kmett wrote:

...

sum and product inclusion mostly allows you do a.) do something smarter than foldl or b.) deal with containers that do things like store prefix sums.

In general you can view the operations as being defined as

given

toList = foldr (:) []

then all the other operations as giving results to match

e.g.

maximum = maximum . toList

with possibly asymptotically much more efficient implementations.

Including toList in the class permits lists and many containers that include a list directly to convert to the 'view' type of being a list in O(1).

-Edward

On Thu, Sep 18, 2014 at 7:49 PM, John Lato wrote:

...
Enthusiastically +1

Every package I know that provides something like Foldable (ListLike, mono-traversable, a few others) includes these, largely for performance reasons.

I'm not entirely convinced with the reasoning that sum and product may be calculated in parallel though. IMHO for structures that care about parallel reductions, I think foldMap should be the main entry point. But I can see these might be cached.

John L.

On Thu, Sep 18, 2014 at 4:26 PM, David Feuer wrote:

...
After discussing these matters some more with Edward Kmett and Reid Barton, it appears the following makes sense:

Add the following to Foldable: length—often stored as a separate field for O(1) access null—called very often and slightly faster than foldr (\_ _ -> False) True for some containers toList—may be the identity or nearly so, and this fact may not be statically available to the foldr/id rule sum, product—may be cached internally in tree nodes for fast update, giving O(1) access; may be calculated in parallel. maximum, minimum—O(n) for a search tree; O(1) for a finger tree. elem—O(log n) for search trees; likely better for hash tables and such.

Don't add anything to Traversable, because scanl1 and scanr1 are not worth the extra dictionary weight.

On Thu, Sep 18, 2014 at 6:20 PM, David Feuer wrote:

...
I'm sorry to send so many emails, but elem should also be moved into the Foldable class to support optimized versions for searchable containers. We should also move maximum and minimum into the Foldable class to allow optimized versions. We need to settle the semantics of these anyway—Data.List.{maximum,minimum} and Data.Foldable.{maximum,minimum} currently behave differently (left-to-right vs. right-to-left). I think we want "whatever's best", which thankfully leaves the list version with its current semantics.

David

On Thu, Sep 18, 2014 at 5:49 PM, David Feuer wrote:

...
R.W. Barton was having trouble spitting out the words "length of a set", and the same holds for all sorts of other things, but unfortunately I think you're right. Proposal amended: put length in the Foldable class.

On Thu, Sep 18, 2014 at 5:43 PM, Edward Kmett wrote:

...
Choosing the name `size` isn't free.

If we chose `length` then the existing code continues to work, code that was hiding it on import continues to hide it and you don't get conflicts.

Picking 'size' is compatible with common practice, but means a ton of modules would break.

Given the two solutions, one that doesn't break anything and one that does, with negligible differences between them otherwise, I'd prefer the one that causes the least amount of pain.

-Edward

On Thu, Sep 18, 2014 at 5:37 PM, David Feuer wrote:

> To go along with Herbert Valerio Riedel's moving functions from > Foldable and Traversable to Prelude, I realized that `null` and `size` make > sense for all Foldables; Reid W. Barton noted that these can have optimized > implementations for many containers. He also noted that scanl1 and scanr1 > make sense for general Traversables. I therefore propose: > > Add `null` and `size` to the Foldable class. Default implementations: > > null = foldr (\_ _ -> False) True > > size = foldl' (\acc _ -> acc+1) 0 > > Add `scanl1` and `scanr1` to the Traversable class. Default > implementations are a little less simple. > > David > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org > http://www.haskell.org/mailman/listinfo/libraries > >

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Edward Kmett

10:55 p.m.

Actually the answer is different. foldMap is used to provide a 'natural' fold regardless of associativity. foldMap and foldr are are mutually definable, by using Endo to get foldr from foldMap, or just accepting a right associated monoidal reduction. This is why foldr or foldMap are the minimal definitions. However, you can't build foldr in terms of foldl with the right behavior on infinite containers, so foldl is _not_ a viable minimal definition for Foldable in a world where you can have infinitely big things to fold! -Edward On Thu, Sep 18, 2014 at 8:37 PM, David Feuer wrote:

...

I'm sorry for confusing things. I had wondered why Foldable uses a right fold instead of a left fold, and the parallel thing was the answer to that.

On Thu, Sep 18, 2014 at 7:59 PM, Edward Kmett wrote:

...
sum and product inclusion mostly allows you do a.) do something smarter than foldl or b.) deal with containers that do things like store prefix sums.

In general you can view the operations as being defined as

given

toList = foldr (:) []

then all the other operations as giving results to match

e.g.

maximum = maximum . toList

with possibly asymptotically much more efficient implementations.

Including toList in the class permits lists and many containers that include a list directly to convert to the 'view' type of being a list in O(1).

-Edward

On Thu, Sep 18, 2014 at 7:49 PM, John Lato wrote:

...
Enthusiastically +1

Every package I know that provides something like Foldable (ListLike, mono-traversable, a few others) includes these, largely for performance reasons.

I'm not entirely convinced with the reasoning that sum and product may be calculated in parallel though. IMHO for structures that care about parallel reductions, I think foldMap should be the main entry point. But I can see these might be cached.

John L.

On Thu, Sep 18, 2014 at 4:26 PM, David Feuer wrote:

...
After discussing these matters some more with Edward Kmett and Reid Barton, it appears the following makes sense:

Add the following to Foldable: length—often stored as a separate field for O(1) access null—called very often and slightly faster than foldr (\_ _ -> False) True for some containers toList—may be the identity or nearly so, and this fact may not be statically available to the foldr/id rule sum, product—may be cached internally in tree nodes for fast update, giving O(1) access; may be calculated in parallel. maximum, minimum—O(n) for a search tree; O(1) for a finger tree. elem—O(log n) for search trees; likely better for hash tables and such.

Don't add anything to Traversable, because scanl1 and scanr1 are not worth the extra dictionary weight.

On Thu, Sep 18, 2014 at 6:20 PM, David Feuer wrote:

...
I'm sorry to send so many emails, but elem should also be moved into the Foldable class to support optimized versions for searchable containers. We should also move maximum and minimum into the Foldable class to allow optimized versions. We need to settle the semantics of these anyway—Data.List.{maximum,minimum} and Data.Foldable.{maximum,minimum} currently behave differently (left-to-right vs. right-to-left). I think we want "whatever's best", which thankfully leaves the list version with its current semantics.

David

On Thu, Sep 18, 2014 at 5:49 PM, David Feuer wrote:

...
R.W. Barton was having trouble spitting out the words "length of a set", and the same holds for all sorts of other things, but unfortunately I think you're right. Proposal amended: put length in the Foldable class.

On Thu, Sep 18, 2014 at 5:43 PM, Edward Kmett wrote:

> Choosing the name `size` isn't free. > > If we chose `length` then the existing code continues to work, code > that was hiding it on import continues to hide it and you don't get > conflicts. > > Picking 'size' is compatible with common practice, but means a ton > of modules would break. > > Given the two solutions, one that doesn't break anything and one > that does, with negligible differences between them otherwise, I'd prefer > the one that causes the least amount of pain. > > -Edward > > On Thu, Sep 18, 2014 at 5:37 PM, David Feuer > wrote: > >> To go along with Herbert Valerio Riedel's moving functions from >> Foldable and Traversable to Prelude, I realized that `null` and `size` make >> sense for all Foldables; Reid W. Barton noted that these can have optimized >> implementations for many containers. He also noted that scanl1 and scanr1 >> make sense for general Traversables. I therefore propose: >> >> Add `null` and `size` to the Foldable class. Default >> implementations: >> >> null = foldr (\_ _ -> False) True >> >> size = foldl' (\acc _ -> acc+1) 0 >> >> Add `scanl1` and `scanr1` to the Traversable class. Default >> implementations are a little less simple. >> >> David >> >> _______________________________________________ >> Libraries mailing list >> Libraries@haskell.org >> http://www.haskell.org/mailman/listinfo/libraries >> >> >

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Daniel Díaz Casanueva

19 Sep 19 Sep

12:32 a.m.

+1 from me as well. In a library I wrote recently, I also provided with more efficient alternatives to those provided by the Foldable class. I'd rather point users to use the generic interface of Data.Foldable. Regards, Daniel Díaz. On Thu, Sep 18, 2014 at 10:55 PM, Edward Kmett wrote:

...

Actually the answer is different.

foldMap is used to provide a 'natural' fold regardless of associativity.

foldMap and foldr are are mutually definable, by using Endo to get foldr from foldMap, or just accepting a right associated monoidal reduction.

This is why foldr or foldMap are the minimal definitions.

However, you can't build foldr in terms of foldl with the right behavior on infinite containers, so foldl is _not_ a viable minimal definition for Foldable in a world where you can have infinitely big things to fold!

-Edward

On Thu, Sep 18, 2014 at 8:37 PM, David Feuer wrote:

...
I'm sorry for confusing things. I had wondered why Foldable uses a right fold instead of a left fold, and the parallel thing was the answer to that.

On Thu, Sep 18, 2014 at 7:59 PM, Edward Kmett wrote:

...
sum and product inclusion mostly allows you do a.) do something smarter than foldl or b.) deal with containers that do things like store prefix sums.

In general you can view the operations as being defined as

given

toList = foldr (:) []

then all the other operations as giving results to match

e.g.

maximum = maximum . toList

with possibly asymptotically much more efficient implementations.

Including toList in the class permits lists and many containers that include a list directly to convert to the 'view' type of being a list in O(1).

-Edward

On Thu, Sep 18, 2014 at 7:49 PM, John Lato wrote:

...
Enthusiastically +1

Every package I know that provides something like Foldable (ListLike, mono-traversable, a few others) includes these, largely for performance reasons.

I'm not entirely convinced with the reasoning that sum and product may be calculated in parallel though. IMHO for structures that care about parallel reductions, I think foldMap should be the main entry point. But I can see these might be cached.

John L.

On Thu, Sep 18, 2014 at 4:26 PM, David Feuer wrote:

...
After discussing these matters some more with Edward Kmett and Reid Barton, it appears the following makes sense:

Add the following to Foldable: length—often stored as a separate field for O(1) access null—called very often and slightly faster than foldr (\_ _ -> False) True for some containers toList—may be the identity or nearly so, and this fact may not be statically available to the foldr/id rule sum, product—may be cached internally in tree nodes for fast update, giving O(1) access; may be calculated in parallel. maximum, minimum—O(n) for a search tree; O(1) for a finger tree. elem—O(log n) for search trees; likely better for hash tables and such.

Don't add anything to Traversable, because scanl1 and scanr1 are not worth the extra dictionary weight.

On Thu, Sep 18, 2014 at 6:20 PM, David Feuer wrote:

...
I'm sorry to send so many emails, but elem should also be moved into the Foldable class to support optimized versions for searchable containers. We should also move maximum and minimum into the Foldable class to allow optimized versions. We need to settle the semantics of these anyway—Data.List.{maximum,minimum} and Data.Foldable.{maximum,minimum} currently behave differently (left-to-right vs. right-to-left). I think we want "whatever's best", which thankfully leaves the list version with its current semantics.

David

On Thu, Sep 18, 2014 at 5:49 PM, David Feuer wrote:

> R.W. Barton was having trouble spitting out the words "length of a > set", and the same holds for all sorts of other things, but unfortunately I > think you're right. Proposal amended: put length in the Foldable class. > > On Thu, Sep 18, 2014 at 5:43 PM, Edward Kmett > wrote: > >> Choosing the name `size` isn't free. >> >> If we chose `length` then the existing code continues to work, code >> that was hiding it on import continues to hide it and you don't get >> conflicts. >> >> Picking 'size' is compatible with common practice, but means a ton >> of modules would break. >> >> Given the two solutions, one that doesn't break anything and one >> that does, with negligible differences between them otherwise, I'd prefer >> the one that causes the least amount of pain. >> >> -Edward >> >> On Thu, Sep 18, 2014 at 5:37 PM, David Feuer > > wrote: >> >>> To go along with Herbert Valerio Riedel's moving functions from >>> Foldable and Traversable to Prelude, I realized that `null` and `size` make >>> sense for all Foldables; Reid W. Barton noted that these can have optimized >>> implementations for many containers. He also noted that scanl1 and scanr1 >>> make sense for general Traversables. I therefore propose: >>> >>> Add `null` and `size` to the Foldable class. Default >>> implementations: >>> >>> null = foldr (\_ _ -> False) True >>> >>> size = foldl' (\acc _ -> acc+1) 0 >>> >>> Add `scanl1` and `scanr1` to the Traversable class. Default >>> implementations are a little less simple. >>> >>> David >>> >>> _______________________________________________ >>> Libraries mailing list >>> Libraries@haskell.org >>> http://www.haskell.org/mailman/listinfo/libraries >>> >>> >> >

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

John Wiegley

8:09 a.m.

...

...
...
...
...
Daniel Díaz Casanueva writes:

...

+1 from me as well. In a library I wrote recently, I also provided with more efficient alternatives to those provided by the Foldable class. I'd rather point users to use the generic interface of Data.Foldable.

+1 from me. John

Andreas Abel

9:42 a.m.

+1, go forward. --Andreas On 19.09.2014 14:09, John Wiegley wrote:

...

...
...
...
...
...
Daniel Díaz Casanueva writes:

...
+1 from me as well. In a library I wrote recently, I also provided with more efficient alternatives to those provided by the Foldable class. I'd rather point users to use the generic interface of Data.Foldable.

+1 from me.

John _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-- Andreas Abel <>< Du bist der geliebte Mensch. Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

Sjoerd Visscher

21 Sep 21 Sep

11:21 a.m.

...

foldMap is used to provide a 'natural' fold regardless of associativity.

foldMap and foldr are are mutually definable, by using Endo to get foldr from foldMap, or just accepting a right associated monoidal reduction.

This is why foldr or foldMap are the minimal definitions.

However, you can't build foldr in terms of foldl with the right behavior on infinite containers, so foldl is _not_ a viable minimal definition for Foldable in a world where you can have infinitely big things to fold!

Wouldn’t it be the other way around for infinite snoc-lists? Sjoerd

Edward Kmett

11:37 a.m.

Yes. I really do consider foldMap to be the canonical form, and both foldr and foldl to be definable things in terms of it, but for historical reasons foldMap has a default definition in terms of foldr. -Edward On Sun, Sep 21, 2014 at 11:21 AM, Sjoerd Visscher wrote:

...

foldMap is used to provide a 'natural' fold regardless of associativity.

foldMap and foldr are are mutually definable, by using Endo to get foldr from foldMap, or just accepting a right associated monoidal reduction.

This is why foldr or foldMap are the minimal definitions.

However, you can't build foldr in terms of foldl with the right behavior on infinite containers, so foldl is _not_ a viable minimal definition for Foldable in a world where you can have infinitely big things to fold!

Wouldn’t it be the other way around for infinite snoc-lists?

Sjoerd

Herbert Valerio Riedel

19 Sep 19 Sep

7:54 a.m.

On 2014-09-19 at 01:26:22 +0200, David Feuer wrote:

...

After discussing these matters some more with Edward Kmett and Reid Barton, it appears the following makes sense:

Add the following to Foldable:

...

length—often stored as a separate field for O(1) access null—called very often and slightly faster than foldr (\_ _ -> False) True for some containers toList—may be the identity or nearly so, and this fact may not be statically available to the foldr/id rule sum, product—may be cached internally in tree nodes for fast update, giving O(1) access; may be calculated in parallel. maximum, minimum—O(n) for a search tree; O(1) for a finger tree. elem—O(log n) for search trees; likely better for hash tables and such.

Don't add anything to Traversable, because scanl1 and scanr1 are not worth the extra dictionary weight.

Seems sensible to me, hence +1

Joachim Breitner

4:09 p.m.

Hi, Am Donnerstag, den 18.09.2014, 19:26 -0400 schrieb David Feuer:

...

sum, product—may be cached internally in tree nodes for fast update,

I’m a bit doubtful about the real-world impact of having product there, and probably also sum, besides educational code. Are these so much more common than other aggregations? I think if you want to cache something in treenodes for performance, you should use a suitable data structure there that supports this directly, instead of hoping that your operation happens to be one of the two special cases provided by the type class. Slightly off topic: Wouldn’t it be nice if we would not have to have to add these methods to provide optimized behavior, but rather have the user write "sum . toList" or some other idiomatic code (maybe suggested in the docs), and RULES provided by the container implementer would reliable replace this with the optimized version. Wouldn’t help in polymorphic code, but I doubt that much performance critical code is polymorphic in the container. But then he could simply provide a sumTree or sumSet or something else... I should stop mumbling in circles. Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

Henning Thielemann

4:29 p.m.

On Fri, 19 Sep 2014, Joachim Breitner wrote:

...

Slightly off topic: Wouldn’t it be nice if we would not have to have to add these methods to provide optimized behavior, but rather have the user write "sum . toList" or some other idiomatic code (maybe suggested in the docs), and RULES provided by the container implementer would reliable replace this with the optimized version. Wouldn’t help in polymorphic code, but I doubt that much performance critical code is polymorphic in the container.

But then he could simply provide a sumTree or sumSet or something else... I should stop mumbling in circles.

I am also worried about extending the classes more and more. Where to stop? At which point the API will be stable? A way to optimize non-methods for certain instances would be nice. Unfortunately, it is not only hard to predict when RULES fire, a RULES based solution is also dangerous. If a default method implementation and an actual instance implementation do different things, that's ok. In contrast, if a function is replaced by different functionality via RULES, that's very bad.

David Feuer

4:52 p.m.

Joachim, you may be right about sum and product; I really don't know. Henning: this doesn't change the Data.Foldable API at all. Data.Foldable already exports all of these functions, and the class would give each of them a valid default implementation. I thoroughly agree with you about the peril of using RULES to specialize a function to a typeclass instance. As well as being hard to predict, potentially perilous, and inapplicable to polymorphic recursive situations, RULES also privilege "built-in" types over identical user-defined ones. On Fri, Sep 19, 2014 at 4:29 PM, Henning Thielemann < lemming@henning-thielemann.de> wrote:

...

On Fri, 19 Sep 2014, Joachim Breitner wrote:

Slightly off topic: Wouldn’t it be nice if we would not have to have to

...
add these methods to provide optimized behavior, but rather have the user write "sum . toList" or some other idiomatic code (maybe suggested in the docs), and RULES provided by the container implementer would reliable replace this with the optimized version. Wouldn’t help in polymorphic code, but I doubt that much performance critical code is polymorphic in the container.

But then he could simply provide a sumTree or sumSet or something else... I should stop mumbling in circles.

I am also worried about extending the classes more and more. Where to stop? At which point the API will be stable? A way to optimize non-methods for certain instances would be nice. Unfortunately, it is not only hard to predict when RULES fire, a RULES based solution is also dangerous. If a default method implementation and an actual instance implementation do different things, that's ok. In contrast, if a function is replaced by different functionality via RULES, that's very bad. _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Henning Thielemann

5:05 p.m.

On Fri, 19 Sep 2014, David Feuer wrote:

...

Joachim, you may be right about sum and product; I really don't know. Henning: this doesn't change the Data.Foldable API at all. Data.Foldable already exports all of these functions, and the class would give each of them a valid default implementation.

For consumers of the functions it would not change much. However, user instances with custom implementations of the new methods cannot be used with older Prelude versions anymore.

David Feuer

5:17 p.m.

On Fri, Sep 19, 2014 at 5:05 PM, Henning Thielemann < lemming@henning-thielemann.de> wrote:

...

On Fri, 19 Sep 2014, David Feuer wrote:

Joachim, you may be right about sum and product; I really don't know.

...
Henning: this doesn't change the Data.Foldable API at all. Data.Foldable already exports all of these functions, and the class would give each of them a valid default implementation.

For consumers of the functions it would not change much. However, user instances with custom implementations of the new methods cannot be used with older Prelude versions anymore.

Don't we normally blame the person who wrote code that was incompatible with the library version they wanted to support, rather than the new library for adding something new that they chose to depend on?

Edward Kmett

5:25 p.m.

A secondary reason for their inclusion is explicitly to avoid randomly changing the semantics of the versions supplied by Prelude by changing to the definitions from Foldable. E.g. foldl vs foldr based sum and the like. Sent from my iPhone

...

On Sep 19, 2014, at 5:05 PM, Henning Thielemann wrote:

...
On Fri, 19 Sep 2014, David Feuer wrote:

Joachim, you may be right about sum and product; I really don't know. Henning: this doesn't change the Data.Foldable API at all. Data.Foldable already exports all of these functions, and the class would give each of them a valid default implementation.

For consumers of the functions it would not change much. However, user instances with custom implementations of the new methods cannot be used with older Prelude versions anymore. _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

David Feuer

5:26 p.m.

I'd forgotten about that, Edward. Yes, without that, one or the other would have to change, and not necessarily for the good. On Fri, Sep 19, 2014 at 5:25 PM, Edward Kmett wrote:

...

A secondary reason for their inclusion is explicitly to avoid randomly changing the semantics of the versions supplied by Prelude by changing to the definitions from Foldable.

E.g. foldl vs foldr based sum and the like.

Sent from my iPhone

...
On Sep 19, 2014, at 5:05 PM, Henning Thielemann < lemming@henning-thielemann.de> wrote:

...
On Fri, 19 Sep 2014, David Feuer wrote:

Joachim, you may be right about sum and product; I really don't know. Henning: this doesn't change the Data.Foldable API at all. Data.Foldable already exports all of these functions, and the class would give each of them a valid default implementation.

For consumers of the functions it would not change much. However, user instances with custom implementations of the new methods cannot be used with older Prelude versions anymore. _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Edward Kmett

5:27 p.m.

Keep in mind as part of the "burning bridges proposal that caused us to form the core libraries committee in the first place the Foldable/Traversable definitions replace the Prelude ones. There is no new conflict against Prelude. Sent from my iPhone

...

On Sep 19, 2014, at 5:05 PM, Henning Thielemann wrote:

...
On Fri, 19 Sep 2014, David Feuer wrote:

Joachim, you may be right about sum and product; I really don't know. Henning: this doesn't change the Data.Foldable API at all. Data.Foldable already exports all of these functions, and the class would give each of them a valid default implementation.

For consumers of the functions it would not change much. However, user instances with custom implementations of the new methods cannot be used with older Prelude versions anymore. _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Joachim Breitner

4:59 p.m.

Hi, Am Freitag, den 19.09.2014, 22:29 +0200 schrieb Henning Thielemann:

...

Unfortunately, it is not only hard to predict when RULES fire, a RULES based solution is also dangerous. If a default method implementation and an actual instance implementation do different things, that's ok. In contrast, if a function is replaced by different functionality via RULES, that's very bad.

I meant rules provided by whoever implements the class: instance Traversable Foo where.. {-# RULES "sum/Foo" forall fx :: Foo Int . sum (toList fx) = sumFoo xs #-} so there would be no worry about soundness. I do _not_ mean adding such rules to where the class is defined. (This assumes that GHC does the right thing when the overloaded toList occurs in a rule, which I am not sure of.) Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

Edward Kmett

5:04 p.m.

The problem with rules here is if the user is working polymorphically then when their code does or doesn't inline then you get varying semantics. You can see this in code that uses realToFrac but doesn't get inlined to specialize to Float/Double today in behavior around NaN. Let's not double down on a design that causes flaky behavior that doesn't scale. Sent from my iPhone

...

On Sep 19, 2014, at 4:59 PM, Joachim Breitner wrote:

Hi,

Am Freitag, den 19.09.2014, 22:29 +0200 schrieb Henning Thielemann:

...
Unfortunately, it is not only hard to predict when RULES fire, a RULES based solution is also dangerous. If a default method implementation and an actual instance implementation do different things, that's ok. In contrast, if a function is replaced by different functionality via RULES, that's very bad.

I meant rules provided by whoever implements the class:

instance Traversable Foo where..

{-# RULES "sum/Foo" forall fx :: Foo Int . sum (toList fx) = sumFoo xs #-}

so there would be no worry about soundness.

I do _not_ mean adding such rules to where the class is defined.

(This assumes that GHC does the right thing when the overloaded toList occurs in a rule, which I am not sure of.)

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

3894

Age (days ago)

3897

Last active (days ago)

List overview

Download

24 comments

10 participants

participants (10)

Andreas Abel
Daniel Díaz Casanueva
David Feuer
Edward Kmett
Henning Thielemann
Herbert Valerio Riedel
Joachim Breitner
John Lato
John Wiegley
Sjoerd Visscher

Proposal: Add a few extra members to Foldable and Traversable classes

tags

participants (10)