[Proposal] Strict `sum` and `product`
Oleg Grenrus
oleg.grenrus at iki.fi
Sun Oct 18 20:16:46 UTC 2020
Sorry I wasn't clear myself. Option C is "add sum'"
For lists:
sum = foldr (+) 0
sum' = foldl' (+) 0
For Foldable
sum = getSum #. foldMap Sum
sum' = getSum #. foldMap' Sum
- Oleg
On 18.10.2020 23.11, Hécate wrote:
>
> Indeed, and I initially went to suggest a `foldMap'`-based
> implementation to keep with the current implementation of many
> Foldable functions that are based on `foldMap` rather than a raw `fold`.
>
> On 18/10/2020 22:04, Oleg Grenrus wrote:
>> For the sake of bigger audience I didn't bother mentioning #. which
>> is a coercion helper. It's essentially better (.) when the first
>> argument is newtype constructor (i.e. coerce).
>>
>> So with Option A (strict):
>>
>> sum = getSum #. foldMap' Sum
>>
>> Or Option B (lazy)
>>
>> sum = getSum #. foldMap Sum
>>
>> ---
>>
>> There is also third option, Option C:
>>
>> sum = foldr (+) 0
>> sum' = foldl' (+) 0
>>
>> I don't think this is worthwhile, but it is an option.
>> (to rehash, I don't consider maintaining status quo to be an option
>> at all).
>>
>> - Oleg
>> On 18.10.2020 22.54, Vanessa McHale wrote:
>>>
>>> It's
>>>
>>> sum = getSum #. foldMap Sum
>>>
>>> in base.
>>>
>>> On 10/18/20 2:49 PM, Oleg Grenrus wrote:
>>>>
>>>> The problem is the current definition of sum for lists which uses
>>>> foldl, i.e non-strict left fold
>>>>
>>>> sum = foldl (+) 0
>>>>
>>>> It's utterly broken. Either we should change it to foldl' to work
>>>> on some types where addition is strict, Option A:
>>>>
>>>> sum = foldl' (+) 0
>>>>
>>>> or alternatively (to make people using lazy accumulator types),
>>>> Option B:
>>>>
>>>> sum = foldr (+) 0
>>>>
>>>> The current state is no good for anyone or anything.
>>>>
>>>> ---
>>>>
>>>> Related issue which Hecate didn't clearly mention, is that Foldable
>>>> class default implementation has
>>>>
>>>> class Foldable f where
>>>> ...
>>>> sum = getSum . foldMap Sum -- this is "good" lazy definition
>>>>
>>>> If we select option A, then I argue that for consistency the
>>>> default `Foldable.sum` should be
>>>>
>>>> sum = getSum . foldMap' Sum -- strict foldMap'
>>>>
>>>> If we select option B, Foldable definition doesn't need to be changed.
>>>>
>>>> ---
>>>>
>>>> I repeat, using non-strict left fold, foldl, for sum and product is
>>>> not good for anything.
>>>> Either foldr or foldl'.
>>>>
>>>> I have no strong preference. Current state is unacceptable.
>>>>
>>>> - Oleg
>>>>
>>>> On 18.10.2020 22.24, Henning Thielemann wrote:
>>>>>
>>>>> On Sun, 18 Oct 2020, Hécate wrote:
>>>>>
>>>>>> In conclusion, leaving things to the optimiser that could be
>>>>>> trivially made fast every time seems needlessly risky.
>>>>>
>>>>> `seq` is still a hack. A strict 'sum' and 'product' would still
>>>>> fail on a lazy accumulator type, say a lazy pair type. If at all,
>>>>> sum and product should be deepseq-strict. So currently, letting
>>>>> the optimiser make a lazy sum strict is still the smaller hack.
>>>>>
>>>>> _______________________________________________
>>>>> Libraries mailing list
>>>>> Libraries at haskell.org
>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>>
>>>> _______________________________________________
>>>> Libraries mailing list
>>>> Libraries at haskell.org
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries at haskell.org
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> --
> Hécate ✨
> IRC: Uniaika
> WWW: https://glitchbra.in
> RUN: BSD
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20201018/be9598d8/attachment-0001.html>
More information about the Libraries
mailing list