[Proposal] Strict `sum` and `product`

Vanessa McHale vamchale at gmail.com
Sun Oct 18 18:46:34 UTC 2020

For my own edification, what happens in actual code? i.e. not GHCi

Vanessa McHale

On 10/18/20 1:13 PM, Hécate wrote:
> 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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 659 bytes
Desc: OpenPGP digital signature
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20201018/e69a849d/attachment.sig>

More information about the Libraries mailing list