[Proposal] Strict `sum` and `product`

Wed Oct 21 19:36:43 UTC 2020

I can't think of an example where a raw lazy `sum` would be preferable to a strict version. If summing over infinite data structures, it will always be prefixed by a `take` or a `drop` prior to summing to make sure we work with finite chunks. In which case, a strict sum is still better. Maybe someone has a more complex, contrived example showing the usefulness of lazy sums.

The fact that no one seems to be able to name one in this or other discussions, or come up with a contrived example, is a good indicator to me that at least the default should be strict in this case. We should offer a lazy variant as a second option, not the first.

I'm in favor of Oleg's `foldMap` implementation. It's really clean. Also thank you Hécate!

Cheers,

Emily

On Tue, Oct 20, 2020 at 12:40 PM, Sylvain Henry < sylvain at haskus.fr > wrote:

> 
> 
> 
> 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@ haskell. org ( Libraries at haskell.org )
>>>>>>> http:/ / mail. haskell. org/ cgi-bin/ mailman/ listinfo/ libraries (
>>>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries )
>>>>>>> 
>>>>>> 
>>>>>> 
>>>>>> _______________________________________________
>>>>>> Libraries mailing list
>>>>>> Libraries@ haskell. org ( Libraries at haskell.org )
>>>>>> http:/ / mail. haskell. org/ cgi-bin/ mailman/ listinfo/ libraries (
>>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries )
>>>>>> 
>>>>> 
>>>>> 
>>>>> _______________________________________________
>>>>> Libraries mailing list
>>>>> Libraries@ haskell. org ( Libraries at haskell.org )
>>>>> http:/ / mail. haskell. org/ cgi-bin/ mailman/ listinfo/ libraries (
>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries )
>>>>> 
>>>> 
>>>> 
>>>> _______________________________________________
>>>> Libraries mailing list
>>>> Libraries@ haskell. org ( Libraries at haskell.org )
>>>> http:/ / mail. haskell. org/ cgi-bin/ mailman/ listinfo/ libraries (
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries )
>>>> 
>>> 
>>> -- 
>>> Hécate ✨
>>> IRC: Uniaika
>>> WWW: https:/ / glitchbra. in ( https://glitchbra.in )
>>> RUN: BSD
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries@ haskell. org ( Libraries at haskell.org )
>>> http:/ / mail. haskell. org/ cgi-bin/ mailman/ listinfo/ libraries (
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries )
>>> 
>> 
>> 
>> _______________________________________________
>> Libraries mailing list
>> Libraries@ haskell. org ( Libraries at haskell.org )
>> http:/ / mail. haskell. org/ cgi-bin/ mailman/ listinfo/ libraries (
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries )
>> 
> 
> 
> 
> _______________________________________________
> Libraries mailing list
> Libraries@ haskell. org ( Libraries at haskell.org )
> http:/ / mail. haskell. org/ cgi-bin/ mailman/ listinfo/ libraries (
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries )
> 
> 
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20201021/edb249e6/attachment.html>