Haskell foldr vs foldl and When to Use Each One

You wrote a fold over a list of ten million numbers, it worked in GHCi on a small input, and then the real run ate 1.5 GB of memory or died with a stack overflow. The choice of Haskell foldr vs foldl is usually the culprit, and the fix takes one character once you understand what each fold actually builds before it returns anything.

This guide traces both folds by hand, explains why the strict version from Data.List is the default you want for most accumulations, and shows the cases where foldr is not just acceptable but the only correct answer.

Haskell foldr vs foldl and what each one does

Both functions collapse a list into a single value with a binary function and a starting value. The difference is the direction the parentheses lean.

• foldr f z [1,2,3] becomes f 1 (f 2 (f 3 z)). The first element sits on the outside.
• foldl f z [1,2,3] becomes f (f (f z 1) 2) 3. The starting value sits deepest inside.

For addition, both give 6. For subtraction, foldr gives 2 and foldl gives -6. If your combining function is not associative, the direction changes the answer, not just the performance.

Why lazy foldl builds a tower of thunks

Here is the part that surprises people. Haskell evaluates lazily, so foldl (+) 0 [1..1000000] does not add anything as it walks the list. It builds an expression: (((0 + 1) + 2) + 3) and so on, one unevaluated thunk per element. Nothing collapses until the result is demanded.

On a 64-bit machine each thunk costs roughly 3 to 4 words, so a list of ten million integers can easily leave several hundred megabytes of pending work on the heap. Modern GHC grows the stack dynamically, so you usually see huge residency rather than a crash, which is worse because it hides.

The lazy foldl has almost no legitimate use. It walks the whole list before producing anything, so it cannot short-circuit, and it delays every step, so it cannot run in constant space. For the full model, see our article on why lazy evaluation in Haskell actually matters.

foldl' is the default for strict accumulation

The fix is foldl' with a trailing apostrophe, exported from Data.List and, since base 4.20 in GHC 9.10, also from the Prelude. It forces the accumulator to weak head normal form at every step, so the running total is an actual number rather than a promise of one.

Rewrite sum-like code like this: replace foldl (+) 0 xs with foldl' (+) 0 xs. In a quick benchmark on my laptop summing ten million Ints, the lazy version peaked at around 800 MB of maximum residency, while foldl' stayed under 1 MB and ran about four times faster. Exact numbers vary with GHC version and flags.

Use foldl' whenever all of these are true:

1. You need to consume the entire list anyway.
2. The result is a single small value such as a count, a sum, a maximum or a Map.
3. Each step can be computed from the previous accumulator and the current element.

Building a Data.Map from a list of pairs is a classic case, because every insert finishes before the next one starts.

The tuple trap

foldl' only forces the outermost constructor. If your accumulator is a pair like (count, total), forcing the pair does not force the numbers inside it, so you rebuild the same thunk tower one level down. Use a data type with strict fields or bang patterns on both components. This is the single most common reason a team says "we switched to foldl' and it still leaks."

When foldr is the right choice

foldr gets a bad reputation from the stack overflow stories, but it is the natural fold for a lazy language. Because the first element sits on the outside, a combining function that is lazy in its second argument can produce output before looking at the rest of the list.

• Building lists. map f = foldr (\x acc -> f x : acc) [] streams. Taking the first 5 elements of the result only evaluates 5 elements of the input, even on an infinite list.
• Short-circuiting. any p = foldr (\x acc -> p x || acc) False stops at the first True, because the second argument of || is never demanded.
• Fusion. GHC's foldr/build rules can remove intermediate lists entirely.

Try it: foldr (\x acc -> x > 10 || acc) False [1..] returns True after checking 11 elements. The same expression with foldl' never terminates, because it insists on reaching the end of an infinite list first.

The rule of thumb is short. If the combining function is lazy in the accumulator and you want a lazy result, use foldr. If the function is strict and you want one compact value, use foldl'. The approach of choosing evaluation order on purpose is a big part of how purely functional programming changes the way you think about loops.

The common advice that is wrong

A lot of tutorials say "never use foldr on large lists, it overflows the stack." That advice is half right and leads people to the wrong fix. foldr (+) 0 on a huge list does build deep recursion, because + is strict in both arguments and cannot produce anything until the right side is known. But the answer there is foldl', not avoiding foldr everywhere.

Teams that follow the blanket rule end up rewriting map-like and filter-like code with foldl' and then calling reverse at the end. That version cannot short-circuit, breaks on infinite input and defeats fusion. I once saw this turn a 20 MB streaming log parser into one that loaded a 2 GB file before emitting a line. The problem was never foldr. It was using a strict operator with a lazy fold.

Another weak piece of advice is "just add -O2 and it will be fine." Strictness analysis catches simple sums, but not accumulators stored in records or passed through unspecialised class methods. If you later suspect a fold is still holding memory, the walkthrough in how to find and fix a Haskell space leak in production shows how to confirm it with heap profiles.

A quick decision checklist

Frequently asked questions

Is foldl ever better than foldl' in Haskell?

Almost never. The lazy foldl can only help when the combining function ignores the accumulator in some cases and you want to avoid computing values that are later thrown away, which is rare in real code. That is why GHC 9.10 added foldl' to the Prelude, so the strict version is now as easy to reach as the lazy one.

Why does foldr work on infinite lists but foldl does not?

foldr puts the first element on the outside of the expression, so a lazy combining function can return a result after seeing only a prefix of the list. foldl has to reach the final element before it can hand back its outermost application, and an infinite list has no final element. The program simply keeps walking forever.

Does foldl' fully evaluate the accumulator?

No, it only forces weak head normal form, meaning the outermost constructor. A plain Int or Double is fully evaluated that way, but a tuple, a Maybe or a lazy record can still hide thunks inside. Use strict fields or bang patterns on the inner values to make the whole accumulator strict.