asum really needs to go into the Foldable class (or something)

[Edward Kmett]

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
that you need to consider your
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 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

On Wed, Nov 5, 2014 at 2:56 PM, David Feuer <david.feuer at gmail.com> wrote:

> 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" <david.feuer at gmail.com> 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" <david.feuer at gmail.com> 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" <ekmett at gmail.com> wrote:
>>>
>>>> Please consider me strongly against such a FoldableMP class.
>>>>
>>>> -Edward
>>>>
>>>> On Wed, Nov 5, 2014 at 11:42 AM, David Feuer <david.feuer at gmail.com>
>>>> 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
>>>>>
>>>>
>>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141105/bfde8e7b/attachment.html>