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

[David Feuer]

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" <ekmett at gmail.com> 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
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141105/f6a72f85/attachment-0001.html>