Fold (higher-order function)

In <a href="/facts/Functional_programming/cdxqPEIM">functional programming</a>, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of <a href="/facts/Higher-order_function/VjnjGbpt">higher-order functions</a> that <a href="/facts/Analysis/heFlRrYd">analyze</a> a <a href="/facts/Recursive_data_type/fzBvEl6A">recursive</a> data structure and through use of a given combining operation, recombine the results of <a href="/facts/Recursion/CxSKxJoW">recursively</a> processing its constituent parts, building up a return value. Typically, a fold is presented with a combining <a href="/facts/Subroutine/9vFJrg0A">function</a>, a top <a href="/facts/Node_(computer_science)/eYlvVE0z">node</a> of a <a href="/facts/Data_structure/yNsNvL1I">data structure</a>, and possibly some default values to be used under certain conditions. The fold then proceeds to combine elements of the data structure's <a href="/facts/Hierarchy/mYJyqFrG">hierarchy</a>, using the function in a systematic way.
Folds are in a sense dual to <a href="/facts/Unfold_(higher-order_function)/nPgySzu3">unfolds</a>, which take a seed value and apply a function <a href="/facts/Corecursion/w9voxGRn">corecursively</a> 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 <a href="/facts/Terminal_and_nonterminal_symbols/3BLz2wJU">terminal</a> values and the recursive results (<a href="/facts/Catamorphism/SVL5Dmjf">catamorphism</a>, versus <a href="/facts/Anamorphism/nPgySzu3">anamorphism</a> of unfolds).

Fold (higher-order function) open-in-new

Fold (higher-order function)