Re: [Proposal] Strict `sum` and `product`

Even worse, it’s using foldl on lists, when, to the best of my knowledge, only foldr and foldl’ ever make sense for finite Haskell lists. Not sure about infinite lists ;) On Wed, Oct 21, 2020 at 4:11 PM chessai wrote:

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 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 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@haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing listLibraries@haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing listLibraries@haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing listLibraries@haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

-- Hécate [image: ✨] IRC: Uniaika WWW: https://glitchbra.in RUN: BSD

_______________________________________________ Libraries mailing listLibraries@haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing listLibraries@haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries