haskell / haskell/core-libraries-committee
Fix foldl
- Dominant language
- Haskell
- Stars
- 109
- Forks
- 20
- PR merge metrics
- No merged PRs in 30d
Description
# Summary
`foldl` has been wrong in Haskell since Haskell 1.0, though it was correct in Orwell at around the same time. This should have been fixed in Haskell 1.4 and 98 but it never got done. We still live with this beginner foot gun to this day: every Haskell intro course has to teach how to avoid the common cause of space leaks with accumulating parameters and then has to add as an addendum to avoid using `foldl` and use `foldl'` instead.
It's not too late to fix it 36 years later!
I have a long explanation of why it's wrong, the history of how it ended up wrong in a blog post from 12 years ago: https://www.well-typed.com/blog/90/
The gist is that Haskell's foldl is defined the way it is (non-strictly) only for historical and inertia reasons, and not for any substantive reasons.
# The proposed change
Specify list `foldl` as:
```
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f !a [] = a
foldl f !a (x:xs) = foldl f (f a x) xs
```
The GHC implementation in ghc-internal can use a definition compatible with foldr/build fusion provided that it is semantically equivalent (including for partially defined values).
# Impact
It is a semantic change for some partially defined values. More specifically it is a semantic change in a subset of cases when `foldl` is used with an accumulator functions that is non-strict in its first argument.
## Positive impacts
* Teaching will be easier and beginners will have fewer foot guns and "why is it like this" questions.
* Performance in some cases will be better.
* The proposed definition of `foldl` will also subsume `foldl'` and generate better/smaller code than `foldl'` since the accumulator can be strict from iteration 0, rather than from iteration 1.
## Negative impacts:
This is hard to quantify precisely. This is arguably a PVP breaking change because it is a semantic change (in some narrow cases).
Almost all existing uses of `foldl` will have no negative difference. I provide examples and arguments in the blog post. I myself have only used `foldl` where `foldl'` would not work in one case, in around 25 years.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reviewing the proposed strict definition of foldl and the GHC implementation in ghc-internal, including its compatibility with foldr/build fusion. Examine the stated semantic changes for partially defined values and the relationship to foldl'. Done requires resolving the compatibility and specification questions before implementation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100