There's a big difference between operations that don't care what's in the Foldable, or that inherently know it, and ones that do care. Foldable is very good at things that don't care, or that know it, like foldl, foldl', foldl1, foldr, foldr', foldr1, toList, length, null, and, or, any, all. For elem, sum, product, asum, and traverse_, it matters very much, but Foldable can't distinguish! On Wed, Nov 5, 2014 at 1:02 PM, Felipe Lessa wrote:

Why the separate type class? Am I missing something?

Cheers! :)

-- Felipe.

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

OK, so can you suggest a good implementation of sum or asum or traverse_ that will work sanely regardless of the monoid? Because I can't think of any way to do that. Or can you think of a better way than FoldableMP to accomplish that objective? On Nov 5, 2014 1:45 PM, "Edward Kmett" wrote:

Please consider me strongly against such a FoldableMP class.

-Edward

On Wed, Nov 5, 2014 at 11:42 AM, David Feuer wrote:

...

The current definition is "biased", using foldr and <|> instead of foldMap and the new Alt. This is a bit awkward in the post-BBP world, but we also don't want to just debias it across the board, because if the Foldable is holding lists, the debiased version will be very bad.

More generally, there are a number of Foldable members that are very awkward, pleading for MPTC, because the sane implementations depend on both the container type and the element type. I know we're pushing right up against the deadline for 7.10.1, but the current situation is making me very nervous.

David

No, this doesn't get the job done either. Here are some situations: 1. The Foldable is a cons list, snoc list, or tree 2. The Monoid is right-handed (list-like, IO-like), left-handed (snoc-list-like), balanced (a balanced tree), or indifferent (Int, Double, etc). 3. The Monoid is left-strict (certain lazy Nats), right-strict (certain other ones), entirely strict (Int, etc.), or entirely lazy (an unbalanced leaf tree). How can we hope to do something sane in all these cases? On Nov 5, 2014 2:07 PM, "David Feuer" wrote:

Well, I guess I can try to answer my own question. The main distinction is between left-handed and right-handed monoids. So the thing to do is to add explicitly left-handed and explicitly right-handed versions of these functions to Data.Foldable. On Nov 5, 2014 2:03 PM, "David Feuer" wrote:

...

OK, so can you suggest a good implementation of sum or asum or traverse_ that will work sanely regardless of the monoid? Because I can't think of any way to do that. Or can you think of a better way than FoldableMP to accomplish that objective? On Nov 5, 2014 1:45 PM, "Edward Kmett" wrote:

...

Please consider me strongly against such a FoldableMP class.

-Edward

On Wed, Nov 5, 2014 at 11:42 AM, David Feuer wrote:

...

The current definition is "biased", using foldr and <|> instead of foldMap and the new Alt. This is a bit awkward in the post-BBP world, but we also don't want to just debias it across the board, because if the Foldable is holding lists, the debiased version will be very bad.

More generally, there are a number of Foldable members that are very awkward, pleading for MPTC, because the sane implementations depend on both the container type and the element type. I know we're pushing right up against the deadline for 7.10.1, but the current situation is making me very nervous.

David

Thank you for your thoughtful response. My concern is not only for infinite snoc-lists and such: those issues point to potential efficiency problems in finite cases. As Reid Barton put it, the Foldable abstraction starts to look leaky as soon as efficiency becomes a concern. As you point out, however, there's only so much we can do about it. I suppose fancier abstractions will have to develop off to the side for now. David On Nov 5, 2014 3:48 PM, "Edward Kmett" wrote:

We're not trying for perfect symmetry here.

Out of the box, the combinators in Foldable will mostly 'do the right

thing' for the right-handed list-like case, balanced and indifferent cases -- to borrow your vocabulary.

It is when you are working with a left-handed infinitely large container

options carefully, but anything that buries an infinite recursion anywhere but on the right hand side is going to have problems already today!

Assume almost everything will be biased to be strict on its left because of the heritage of these operations being defined on list.

Foldable is less ambitious than what you want it to be here. It merely takes the cases we can do for lists and other possibly infinite-on-the-right constructions and extends them to get to exploit *finite* tree structure as well.

They've done that all along, without any of this current wave of additions to the class. What we've added are methods that make it possible to get a few asymptotic wins for things that we could already say, avoid a few space leaks the current generalization would otherwise incur, and which let us paper over the differences in evaluation order between Foldable and

that you need to consider your the existing Prelude combinators.

These are all useful things -- with or without Foldable perfectly

handling all of its operations on infinite-snoc lists. They make the API "just better" at doing the things it can already do today.

We've gotten very good at shaking things out so they handle infinite

recursion on the right hand side. Infinitely large lazy lists have been a huge part of Haskell since the beginning!

But, if you use infinite recursion elsewhere, toList is just going to

bottom out. It can never finish. There is no sensible answer. -MOST- of the API is similar, but you're being lured in by the notion that things like e.g. foldMap (Dual . Sum) will work for infinite recursion on the left.

Every so often you'll be able to use them on sufficiently lazy monoids or

things with the right strictness properties, but ultimately the _vast_ majority of consumers of Foldable will never encounter these sorts of concerns. They've already lived with them for several years mostly, and the "issue" that has you up in arms has passed almost entirely without complaint.

What we've done by extending the class is removed a lot of the impedence

mismatch between the two major sets of cases that Foldable does handle well -- finite tree structures and right biased infinite list-like structures.

These extensions are not intended to offer a perfect solution for every

possible infinitely large tree structure. Things like toList show one provably can never succeed in the the more idealized form of the Foldable mission you'd like.

There is a fundamental tension between the desire you have for

universality and the need to handle infinite-recursion on the right. That latter scenario forces many of our monoids to be strict in the left argument. Otherwise the ability to merely finitely reassociate isn't sufficient to actually finish computing an answer in a way that is productively corecursive.

That doesn't mean we shouldn't continue to look to ways to make Foldable

better at the things it can be made to do better, but it does mean I'm not in a hurry to make Foldable unusable for normal users in order to better support the "infinite snoc-list" cases that we can never fully successfully support!

-Edward