[Proposal] Strict `sum` and `product`

Hécate hecate at glitchbra.in
Sun Oct 18 18:13:33 UTC 2020

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]
(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 

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, 
[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

More information about the Libraries mailing list