Fold
infogalactic Fold (higher-order function)
In functional programming, fold – also known variously as 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. The fold then proceeds to combine elements of the data structure's hierarchy, using the function in a systematic way.
Folds in various languages
| Language | Left fold | Right fold | Left fold without initial value | Right fold without initial value | Notes |
|---|---|---|---|---|---|
| C++ | std::accumulate(begin, end, initval, func) |
std::accumulate(rbegin, rend, initval, func) |
in header <numeric> begin, end, rbegin, rend are iterators func can be a function pointer or a function object |
||
| Python 3.x | functools.reduce(func, list, initval) |
functools.reduce(lambda x,y: func(y,x), reversed(list), initval) |
functools.reduce(func, list) |
functools.reduce(lambda x,y: func(y,x), reversed(list)) |
In module functools.[2] |