Understanding foldl and foldr in Haskell: Associativity, Evaluation, and Space Usage

Both `foldl` and `foldr` process a list from the first element to the last, but they differ in how they associate the combining operation. With `foldl`, the operation is left‑associated, building the expression (((v ⊗ e0) ⊗ e1) ⊗ e2) …, while `foldr` is right‑associated, producing e0 ⊗ (e1 ⊗ (e2 ⊗ … (en ⊗ v)…)). The list elements appear in the same order in both expressions; only the grouping of applications changes. (source: primary)

In a strict language, evaluation proceeds from the inside out. For `foldl`, the first list element is needed immediately, allowing a tail‑recursive implementation that uses constant stack space. In contrast, `foldr` must reach the end of the list before any reduction can start, so it necessarily builds a call stack proportional to the list length. When the combining operation is associative and commutative (e.g., (+)), both functions yield the same final result, but the reduction sequences differ. (source: primary)

In a lazy language like Haskell, evaluation proceeds from the outside in, demanding results only as needed. Here `foldl` becomes problematic: each step creates a thunk for the partially applied operation, and because the outermost thunk is not forced until the end, a chain of thunks linear in the list size accumulates, leading to linear space consumption. The strict variant `foldl'` forces the accumulator at each step, preventing thunk buildup and restoring constant‑space behavior. Conversely, `foldr` can be lazy in its second argument; if the combining function is lazy there, `foldr` can return a result in weak‑head normal form without traversing the whole list, enabling work‑saving and the ability to operate on infinite lists. (source: primary)

As a rule of thumb, use `foldl'` when the accumulation function is strict, and use `foldr` when the function is lazy in its second argument; avoid plain `foldl` and `foldr'` on lists. For other data structures the optimal choice depends on their associativity, and `foldMap`/`foldMap'` are often better when associativity is irrelevant. (source: primary)