leftfolds

Leftfolds, or left folds, are a family of higher‑order functions used to reduce a finite data structure from the left to the right. They take a binary function, an initial accumulator, and a sequence, and produce a single result by repeatedly applying the function to the accumulator and the next element in order. In many languages this operation is called foldl (for example, Haskell) or simply a left-to-right reduction.

Formally, for a function f, an initial value z, and a list [x1, x2, ..., xn], a left fold computes:

foldl f z [] = z

foldl f z (x:xs) = foldl f (f z x) xs

Thus the accumulator is threaded through the entire structure from the first element to the last. Examples: foldl (+) 0 [1,2,3] yields 6, and foldl (++) "" ["a","b","c"] yields "abc" (though string concatenation this way is often inefficient in some languages).

Left folds are typically strict in their accumulator, but many languages with laziness can accumulate thunks unless a strict version is used. For example, a strict left fold (often denoted foldl') helps avoid large build-up of unevaluated expressions and prevents excessive memory use on long lists. In languages with tail-call optimization, a well‑implemented foldl can be performed in constant space.

Left folds contrast with right folds, or foldr, which process elements from right to left. The two have different performance characteristics and semantics when the combining function is not associative. Related operations include foldl1, foldr1, and scanl, the latter producing a list of intermediate accumulator results. Left folds are foundational in functional programming and appear in many language libraries under various names.