Fold (higher-order function)

In functional programming, a fold is a higher-order function that analyzes a recursive data structure and, through use of a given combining operation, recombines the results of recursively processing its constituent parts, building up a return value. Fold is also termed as reduce, accumulate, aggregate, compress, or inject. 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. The fold then proceeds to combine elements of the data structure's hierarchy, using the function in a systematic way.

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).