[Proposal] Strict `sum` and `product`

[Wander Hillen]

I think this is a very good idea. Non-strict `foldl` for summing and
multiplying introduces undesired space leaking behavior and is a very
surprising default both to beginners and even for more experienced
Haskellers.

If there was a Num type with lazy structure, something like `product
[<some_list_containing_zero>] == 0` would be able to short-circuit as soon
as it hits a zero. However since none of the Num types in base have a lazy
structure (and both sum and product have a Num constraint), there is not
really a way to take advantage of laziness anyway and therefore the best
implementation would be Olegs option A.

Best regards,
Wander

Op zo 18 okt. 2020 om 20:14 schreef Hécate <hecate at glitchbra.in>:

> My fellow Haskell developers, contributors and maintainers,
>
> I wish to present what is certainly a controversial proposal for the
> `base` library:
>     Making the `sum` and `product` functions from the `base` library
> strict.
>
> This is not a new question, the debate is old, but I am personally
> convinced that the existence of those two lazy functions is something
> that should never have happened.
> One of the first goals that led to the creation of Haskell was to enable
> collaboration and research in the domain of lazy (or non-strict)
> programming languages and techniques.
> While it led to the discovery of new methods and ways to represent
> programs, we also realised that this paradigm has proven to produce
> sub-optimal implementations for
> these functions.
>
> And while maintaining backward compatibility *is* important when
> designing and maintaining a programming language, we have thankfully
> developed deprecation mechanisms
> that can be used to signal that bad, or sub-optimal decisions of the
> past can be corrected.
>
> To refresh our collective memory, here is the current state of things,
> regarding `sum`:
>
> ```
> ❯ ghci +RTS -M1024m
> GHCi, version 8.10.1: https://www.haskell.org/ghc/  :? for help
> λ❯ sum [1..10^9]
> *** Exception: heap overflow
> ```
> Whereas, with an alternative implementation, such as `foldl'`:
> ```
> λ❯ foldl' (+) 0 [1..10^9]
> 500000000500000000
> (31.35 secs, 88,000,076,288 bytes)
> ```
>
> I do not think a heap overflow, and the underlying space leak occasioned
> by the laziness of `foldl`, are behaviours we should aim to preserve for
> the sake of backward compatibility.
>
> And actually, I think that moving these two functions to a strict, space
> leak-free implementation would benefit the lazy PL research domain by
> showing a good counter-example
> of why it is not necessarily suitable for every kind of computation.
> I also think, and this is rooted from experience, that we must strive to
> empower our users with the power of laziness. Not burden them with it.
> Standing on the shoulders of giants is what made Haskell so great, but
> this should not prevent us from spreading our wings to go higher.
>
> ———
>
> Now, there have been Prelude replacements (such as Relude) and companion
> libraries (like `strict`) who have been shipping such alternative
> implementations for quite some time now.
>
> A point that can be raised is: Why should we bother? Isn't `strict`
> already enough?
> To this I answer: `strict` and Relude, ultimately, patches on an tire's
> inner tube. We may be able to roll with them for some distance, but
> their very existence is a response to an abnormal situation that we have
> grown to accept.
> However, any bicycle rider who has the means to change their tire should
> do so.
> I believe we have the means to do so.
>
> Another point that could be raised as well is the fact that this
> implementation change would deviate from the 2010 Haskell Report[0].
> If we want to stay true to the spirit and letter of the Report, this is
> actually a non-issue. Indeed, it is noted that:
>
> > This  report  defines  the  syntax  for Haskell  programs and  an
> informal  abstract  semantics  for  the  meaning of such programs.  We
> leave as implementation dependent the ways in which Haskell programs are
> to be manipulated, interpreted, compiled, etc. This includes such issues
> as the nature of programming environments and the error messages
> returned for undefined programs (i.e. programs that formally evaluate
> to⊥).[1]
>
> As well as in chapter 9:
>
> > In this chapter the entire Haskell Prelude is given. It constitutes a
> specification for the Prelude. Many of the definitions are written with
> clarity rather than efficiency in mind, and it is not required that the
> specification be implemented as shown here.[2]
>
> And finally, regarding the non-strict nature of Haskell, the Report
> references strict evaluation to avoid "unneeded laziness."[3]
> Thus it was expected that laziness would not be a silver bullet, and it
> could harm performance.
>
> ———
>
> Regarding the implementation detail, `sum` and `product` would
> piggy-back on the already-present `foldMap'` function.
>
>
> Thank you very much for reading,
> I believe we can all go together towards improving the experience of
> Haskell developers, starting with this.
>
> [0]: Haskell 2010 Language Report,
> https://www.haskell.org/definition/haskell2010.pdf
> [1]: Haskell 2010 Language Report, page 3
> [2]: Haskell 2010 Language Report, Chapter 9 Standard Prelude, page 105
> [3]: Haskell 2010 Language Report, Section 6.2 Strict Evaluation, page 75
>
> --
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20201019/22935ec4/attachment.html>