Understanding the Distinctions Between foldl and foldr

Editor's Note: This piece is a rewritten version of a foundational guide regarding the differences between foldr and foldl (including their strict and lazy variants). Originally appearing in a GitHub pull request for hasura/graphql-engine on September 26, 2019, this explanation has become a staple for onboarding newcomers. We are grateful to Alexis King for permitting its publication here.

The Fundamental Misconception

To begin, we must clear up a common misunderstanding: foldl and foldr are not "folds from the left" and "folds from the right." In reality, both functions traverse the data structure in the exact same direction. For lists, this means they both move from the head to the tail (left to right).

The actual difference lies in the grouping (associativity) of the operations.

Visualizing the Association

If we have a list $[ e_0, e_1, e_2, \dots, e_n ]$, a starting value $v$, and a combining function $\otimes$, the two folds expand as follows:

1. foldl (Left-Associated): $\text{foldl } (\otimes) \ v \ [e_0, \dots, e_n] \implies (\dots((v \otimes e_0) \otimes e_1) \dots \otimes e_n)$

2. foldr (Right-Associated): $\text{foldr } (\otimes) \ v \ [e_0, \dots, e_n] \implies (e_0 \otimes (e_1 \otimes (\dots (e_{n-1} \otimes (e_n \otimes v))\dots)))$

---

Behavior in Strict Languages

In a strict (eager) language, expressions are evaluated from the inside out. The most deeply nested operation is resolved first.

Consider the expression foldl (+) 0 [1, 2, 3, 4]. It expands to: (((0 + 1) + 2) + 3) + 4

The reduction sequence looks like this:

If we used foldr (+) 0 [1, 2, 3, 4], the expansion is 1 + (2 + (3 + (4 + 0))). While the result is the same (because addition is commutative and associative), the evaluation order is reversed.

The Practical Impact: Space Complexity

• foldl: To begin reducing, it only needs the first element. This allows it to be implemented as a tail-recursive loop, operating in constant space.
• foldr: It must reach the very end of the list before the first addition (4 + 0) can occur. For a list of size $n$, the program must push $n$ frames onto the call stack. This is why people mistakenly call it "folding from the right."

---

Behavior in Lazy Languages (Haskell)

In lazy languages, the rules change. Evaluation happens from the outside in, triggered only when a value is actually demanded.

The Problem with Lazy foldl

In Haskell, foldl (+) 0 [1, 2, 3, 4] does not immediately execute a loop. Instead, it builds a massive chain of suspended computations called thunks. If we represent thunks with ⟨ ⟩, the expression becomes:

⟨⟨⟨⟨ 0 + 1 ⟩ + 2 ⟩ + 3 ⟩ + 4 ⟩

Because (+) is strict in both arguments, the outermost thunk cannot be resolved until the innermost one is. This creates a linear-space thunk tree.

• The Danger: In a strict language, the list itself takes linear space. In a lazy language, lists can be streams (constant space). By using lazy foldl, you might accidentally turn a constant-space stream process into a linear-space memory hog.

The Solution: foldl'

To fix this, Haskell provides foldl', the strict version. It forces the evaluation of the accumulator at each step.

• Instead of building ⟨⟨0 + 1⟩ + 2⟩, it evaluates 0 + 1 immediately to get 1, then builds ⟨1 + 2⟩.
• This restores the constant space efficiency of strict languages.

Lazy foldr and Strict Operations

Even in a lazy language, if you use foldr with a strict operation like (+), you still face linear space requirements.

Looking at the expansion: foldr (+) 0 [1, 2, 3, 4] = 1 + (2 + (3 + (4 + 0)))

To compute the final sum, the program must still traverse to the end of the list to find the (4 + 0) base case before it can start collapsing the expression.

---

Summary Checklist

• Traversal Order: Both foldl and foldr move left-to-right.
• Associativity: foldl is left-associated; foldr is right-associated.
• Strict Languages: foldl is efficient (tail-recursive); foldr uses stack space.
• Lazy Languages:
  • foldl is dangerous (builds thunks).
  • foldl' is the preferred strict alternative for efficiency.
  • foldr is necessary for certain lazy patterns (though linear space for strict ops).