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

[David Feuer]

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
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140918/4fd4818c/attachment-0001.html>