haskell / haskell/core-libraries-committee

Fix foldl

Open
#439 32 comments 10 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.