Where the parentheses go: a foldl vs foldr deep read
Alexis King's explanation, reissued on the Haskell blog on 25 September 2026, shows that foldl and foldr walk a list the same way and differ only in how they group the operator — and why that makes foldl' the constant-space choice for a strict accumulator and foldr the one that can stream.
Alexis King published Differences between
foldl and foldr on the Haskell blog on 25 September 2026. 1 The editor's note above the text says the blog is reproducing an explanation King first wrote on 26 September 2019, in a comment on a pull request to graphql-engine, and that the community has used it to teach folds ever since. Its subject is the distinction every Haskell newcomer meets and most get half right. foldl and foldr both walk a list from the first element to the last; what differs is how the fold groups the operator as it goes. In a lazy language that grouping decides whether the fold runs in constant space, streams on demand, or builds a chain of suspended work as long as the input.How the fold groups the operator
The post opens with the two computations side by side. For a list
[e0, e1, …, en−1, en], a starting value v, and an operator (⊗):foldl (⊗) v [e0, e1, …, en] = (… (((v ⊗ e0) ⊗ e1) ⊗ e2) ⊗ … ⊗ en−1) ⊗ en
foldr (⊗) v [e0, e1, …, en] = e0 ⊗ (e1 ⊗ (e2 ⊗ … ⊗ (en−1 ⊗ (en ⊗ v)) … ))The elements stand in the same left-to-right order in both lines; only the parentheses move.
foldl associates the operator to the left, foldr to the right. That is the whole difference in the abstract, and it becomes a practical difference only once you ask what the machine does with each shape.![Two binary trees for foldl (+) 0 [1,2,3,4] and foldr (+) 0 [1,2,3,4]. The same five elements sit in the same left-to-right leaf order in both; the four internal + nodes nest to the left in the first tree and to the right in the second.](https://storage.neodrop.ai/grains/images/_fRJwzZKNklF_baINbPQT.webp?w=640)
Our own diagram, not from the post. The same five elements sit in the same left-to-right order in both trees; the four internal
+ nodes nest to the left for foldl and to the right for foldr. The shape of the tree sets when the first reduction can happen.What the grouping changes in a strict language
A strict language evaluates from the inside out, reducing the most deeply nested expression first.
foldl (+) 0 [1, 2, 3, 4] expands to (((0 + 1) + 2) + 3) + 4, whose innermost piece 0 + 1 sits beside the first element of the list. The fold can reduce that piece as soon as the element arrives, carry the running total forward, and never hold more than the accumulator, which is why foldl is tail-recursive in a strict language and runs in constant space. 1foldr (+) 0 [1, 2, 3, 4] expands to 1 + (2 + (3 + (4 + 0))). The innermost piece 4 + 0 sits beside the last element, so the machine has to reach the end of the list before it can reduce anything. A list of length n costs n stack frames before the first reduction starts. 1In a lazy language, foldl stalls the work
Haskell evaluates from the outside in, forcing an expression only when its result is demanded. Under that rule,
foldl (+) 0 [1, 2, 3, 4] stops behaving like the tail-recursive loop above. The evaluation builds the nested expression first, suspending each (+) application in a thunk; writing thunks as ⟨⟩, the accumulator becomes ⟨⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ + 4⟩. 1Those thunks are forced when the outermost one is demanded, and
(+) is strict in both arguments, so forcing one forces the next in line. The answer comes out right, and the space cost is wrong. Where the strict foldl held a single accumulator, the lazy one holds a chain of thunks linear in the length of the list. In a lazy language the input list behaves more like a stream, one that can be produced and consumed in constant space, so the lazy foldl can turn a constant-space algorithm into a linear-space one. 1foldl', the strict left fold, restores the constant-space behaviour. It demands the new accumulator before moving to the next element, so instead of growing ⟨⟨0 + 1⟩ + 2⟩ it builds ⟨1 + 2⟩ and releases the previous thunk. foldl' walks the list holding never more than a single application of the operator. 12Why lazy foldr can stream
foldr looks like the loser in all of this, because a strict operator makes it hold the whole list. The post shows where it wins. Expand foldr (+) 0 [1, 2, 3, 4] one step at a time and it becomes 1 + foldr (+) 0 [2, 3, 4], then 1 + (2 + foldr (+) 0 [3, 4]), and so on. A lazy language can return the first step as 1 + ⟨foldr (+) 0 [2, 3, 4]⟩ and postpone the rest until (+) demands it. Because (+) is strict, that particular fold still walks the whole list. 1A lazy operator changes the result.
foldr (:) [] [1, 2, 3, 4] reduces to 1 : ⟨foldr (:) [] [2, 3, 4]⟩, which is already in weak-head normal form, the form at which evaluation can stop while the rest stays unforced, so nothing more happens until something asks for the tail. Give the operator a little work and the same shape holds: let f x xs = (x * 2) : xs in foldr f [] [1, 2, 3, 4] becomes ⟨1 * 2⟩ : ⟨foldr f [] [2, 3, 4]⟩ and stops there. Consume only part of the result, as in sum (take 2 (foldr f [] [1, 2, 3, 4])), and the thunk for the tail is never forced, so the list is never fully traversed. 1Three consequences follow. When the accumulator function is lazy in its second argument and the result is not fully consumed,
foldr can save work. foldr can operate on infinite lists, where foldl needs a list that ends. And foldr may fuse with surrounding list operations more readily than foldl; list fusion is the compiler transformation that removes the intermediate lists between a producer and its consumer, and the post sets that topic aside. 1Three rules for choosing
The post reduces its two cases to three rules:
- When the accumulator function is strict, use
foldl', which consumes the list in constant space; the whole list will be traversed anyway. - When the accumulator function is lazy in its second argument, use
foldr, which works incrementally and can leave part of the list unvisited. - On lists, reach for
foldl'orfoldr;foldlandfoldr'are worse than both.
The question that produced the explanation asked which fold to use when accumulating
Map.delete over a list of keys. Map.delete is strict in its accumulator, so the first rule applies and the answer is foldl'. 1King adds a caution about scale. On a list that is not large the choice is usually a micro-optimization that changes nothing measurable, worth learning as a habit and worth understanding as a concrete case of laziness at work. 1
The boundary: this holds for cons lists
All of the above concerns ordinary cons lists, where
(:) is right-associative and the rest of the list sits on the right. The post closes with what changes elsewhere. A snoc list, data SnocList a = Nil | Snoc (SnocList a) a, is left-associative, and the advice inverts: foldr' takes the place foldl' holds on ordinary lists, and foldl the place foldr holds. Trees sit between the two extremes, with some elements on each side and neither fold clearly better; there foldMap and foldMap' are usually the better choice, since they leave the associativity of the combining operation open. 13The post's aside that
foldMap' had to wait for base-4.13.0.0 and GHC 8.8.1 belongs to the 2019 original; both landed that year, and foldMap' ships in base today. 3Verbatim quotes
"To start, you have to understand thatfoldlandfoldrare not folds 'from the left' and 'from the right.' Bothfoldlandfoldrtraverse the structure in the same order, which in the case of lists means left to right. The difference is the fold's associativity.""When the accumulation function is strict, usefoldl'to consume the list in constant space, since the whole list is going to have to be traversed, anyway.""Never usefoldlorfoldr'; they're always worse on lists."— Alexis King, Differences betweenfoldlandfoldr
References
- 1Differences between foldl and foldr
blog.haskell.org
- 2Data.List
hackage.haskell.org
- 3Data.Foldable
hackage.haskell.org
This story was produced automatically by a channel. One sentence is all it takes for Neodrop to keep producing for you.