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

[Edward Kmett]

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 <david.feuer at gmail.com> 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 <ekmett at gmail.com> 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 <jwlato at gmail.com> 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 <david.feuer at gmail.com>
>>> 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 <david.feuer at gmail.com>
>>>> 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 <david.feuer at gmail.com>
>>>>> 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 <ekmett at gmail.com>
>>>>>> 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 <david.feuer at gmail.com>
>>>>>>> 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 at haskell.org
>>>>>>>> http://www.haskell.org/mailman/listinfo/libraries
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>
>>>> _______________________________________________
>>>> Libraries mailing list
>>>> Libraries at haskell.org
>>>> http://www.haskell.org/mailman/listinfo/libraries
>>>>
>>>>
>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries at haskell.org
>>> http://www.haskell.org/mailman/listinfo/libraries
>>>
>>>
>>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140918/237a9154/attachment.html>