Foldl

Foldl is a higher-order function used to reduce a finite list by applying a binary function from the left. Given a function f, an initial accumulator z, and a list xs, foldl f z xs computes f (f (... (f z x1) x2) ... xn). In Haskell, the typical type is foldl :: (b -> a -> b) -> b -> [a] -> b, and a direct definition is: foldl f z [] = z; foldl f z (x:xs) = foldl f (f z x) xs. A common usage is summing numbers: foldl (+) 0 [1,2,3,4] yields 10.

Foldl processes the list from the left, in contrast to foldr, which processes from the right. While many functions yield the same result for associative operations, non-associative functions can produce different results depending on the folding order. Foldl is typically more natural for strictly accumulating state across a traversal.

In lazy languages such as Haskell, foldl can build up large chains of unevaluated expressions (thunks), leading to space leaks. To avoid this, strict variants are used, notably foldl' from Data.List, which evaluates the accumulator at each step. The general complexity is linear in the length of the list: time O(n). Memory usage depends on evaluation strategy: lazy foldl may use O(n) space due to thunks, whereas a strict foldl' uses O(1) additional space, aside from the input list and any final result.

Related constructs include foldl1, which uses the first element as the initial accumulator and requires a non-empty list, and foldr, which folds from the right. Fold maps and other reductions often rely on similar concepts in various functional languages.