[Proposal] Strict `sum` and `product`

[Jon Fairbairn]

Sylvain Henry <sylvain at haskus.fr> writes:

> Do we have an actual example of the use of a lazy sum in the
> wild?

That’s not a very good argument, though I’ve seen it used quite
a lot.  The problem is that just because no-one can currently
think of a “real” example it doesn’t mean that there are no
cases where laziness is required.

For a forced example, consider a wrapping of Double with a test
for infinity on the left argument

…
 a + b | isInfinite a = a
…

which doesn’t evaluate it’s second argument if the first is
infinite.

> If the most common case is the strict one, making `sum`
> strict would be a better default.

Haskell should remain a lazy language, so the defaults should be
lazy unless they can be proved strict anyway.

> If need be we could also provide `lazySum` or something, but
> is there really a need?

Who can truly say? I’d support sum' as the strict version as
that is consistent with other usages.

  — Jón

>
> 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
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

-- 
Jón Fairbairn                                 Jon.Fairbairn at cl.cam.ac.uk
http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html  (updated 2014-04-05)