Differences Between `Foldl` and `Foldr`

Both functions traverse a list left-to-right; the real difference is how they associate applications. foldl produces left-associated expressions (((v⨂e0)⨂e1)⨂...) while foldr produces right-associated ones (e0⨂(e1⨂(e2⨂...))). In a strict language that difference only affects stack usage: foldl can be tail-recursive and constant-space, while foldr needs n stack frames. In lazy Haskell, however, foldl builds a large chain of suspended thunks (e.g. ⟨⟨⟨0+1⟩+2⟩+3⟩+4) and leaks memory; the correct remedy is foldl' which forces the accumulator at each step and preserves constant-space behavior. foldr’s right-associative expansion puts the recursive call in a leaf, so when the combining function is lazy in its second argument (for example (:) or other constructors) foldr can produce results in WHNF incrementally and even work on infinite lists or enable fusion.

Practical rules follow: if the accumulation function is strict, prefer foldl' to avoid thunk buildup; if the function is lazy in its second argument and you want streaming or partial consumption, use foldr. Avoid the plain foldl and foldr' on ordinary cons lists. These behaviors are list-specific: for other structures (snoc lists, trees) associativity flips or becomes ambiguous, and in performance-sensitive cases foldMap / strict foldMap variants are often the right choice.