Fold (higher-order function)

Fold' (or reduce) is a family of higher-order functions in functional computer programming that process a data structure in some order. Generally, it deals with two things: a function and a list of elements. The function generally takes one or two arguments; so a common example given for a fold might be to

fold (+) (1,2,3,4,5)

Fold would add 1 to 2, then add that to 3, and then that to 4 and so on, finally evaluating to 15. In this instance, + is a commutative operation so it is irrelevant whether one begins the summation with 5 or 1.

With another function or list, this could be significant - if one were concatenating strings, for example, the operation would not be commutative, and so on would want to specify whether one starts on the left or right. In Haskell and other functional languages, when dealing with infinite lists, this difference is especially important: foldl will start with the last element of the list, but by definition for infinite lists, there is no last element.