Fold (higher-order function)

In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the results of recursively processing its constituent parts, building up a return value.

Typically, a fold is presented with a combining function, a top node of a data structure, and possibly some default values to be used under certain conditions.

Folds are in a sense dual to unfolds, which take a seed value and apply a function corecursively to decide how to progressively construct a corecursive data structure, whereas a fold recursively breaks that structure down, replacing it with the results of applying a combining function at each node on its terminal values and the recursive results (catamorphism, versus anamorphism of unfolds).

These replacements can be viewed as a diagram: There's another way to perform the structural transformation in a consistent manner, with the order of the two links of each node flipped when fed into the combining function: These pictures illustrate right and left fold of a list visually.

This way of looking at things provides a simple route to designing fold-like functions on other algebraic data types and structures, like various sorts of trees.

In the general case of non-associative binary functions, the order in which the elements are combined may influence the final result's value.

Having reached the end of the list, an expression is in effect built by foldl of nested left-deepening f-applications, which is then presented to the caller to be evaluated.

On finite lists, that means that left-fold and reverse can be composed to perform a right fold in a tail-recursive way (cf.

The extraneous intermediate list structure can be eliminated with the continuation-passing style technique, foldr f z xs == foldl (\k x-> k .

This can lead to stack overflows when one reaches the end of the list and tries to evaluate the resulting potentially gigantic expression.

For this reason, such languages often provide a stricter variant of left folding which forces the evaluation of the initial parameter before making the recursive call.

Combined with tail recursion, such folds approach the efficiency of loops, ensuring constant space operation, when lazy evaluation of the final result is impossible or undesirable.

Using a Haskell interpreter, the structural transformations which fold functions perform can be illustrated by constructing a string: Infinite tree-like folding is demonstrated e.g., in recursive primes production by unbounded sieve of Eratosthenes in Haskell: where the function union operates on ordered lists in a local manner to efficiently produce their set union, and minus their set difference.

A finite prefix of primes is concisely defined as a folding of set difference operation over the lists of enumerated multiples of integers, as For finite lists, e.g., merge sort (and its duplicates-removing variety, nubsort) could be easily defined using tree-like folding as with the function merge a duplicates-preserving variant of union.