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

[David Feuer]

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