[Proposal] Strict `sum` and `product`
Sylvain Henry
sylvain at haskus.fr
Tue Oct 20 16:40:28 UTC 2020
Do we have an actual example of the use of a lazy sum in the wild?
If the most common case is the strict one, making `sum` strict would be
a better default. If need be we could also provide `lazySum` or
something, but is there really a need?
Sylvain
On 18/10/2020 22:16, Oleg Grenrus wrote:
>
> 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
>
> _______________________________________________
> 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/20201020/8b4c6f9b/attachment.html>
More information about the Libraries
mailing list