[Proposal] Strict `sum` and `product`

Wed Oct 21 20:10:52 UTC 2020

I'm pretty strongly in favour of a sum implemented using foldMap'. The
status quo is atrocious (cf. Oleg's emails), and the utility of a lazy
right fold is low in practise.

On Wed, Oct 21, 2020, 14:38 Emily Pillmore <emilypi at cohomolo.gy> wrote:

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