Fold (higher-order function)
   HOME

TheInfoList




In
functional programming In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , ...
, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of
higher-order function In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
s that
analyze
analyze
a
recursive Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics Linguistics is the science, scientific study of language. It e ...
data structure and through use of a given combining operation, recombine the results of
recursively Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...

recursively
processing its constituent parts, building up a return value. Typically, a fold is presented with a combining
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
, a top
node In general, a node is a localized swelling (a "knot A knot is an intentional complication in cordage which may be practical or decorative, or both. Practical knots are classified by function, including hitches, bend Bend or bends may refer t ...
of a
data structure In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of ...

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 A hierarchy (from the Greek: , from , 'president of sacred rites') is an arrangement of items (objects, names, values, categories, etc.) in which the items are represented as being "above", "below", or "at the same level as" one another. Hierarch ...

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


As structural transformations

Folds can be regarded as consistently replacing the structural components of a data structure with functions and values.
Lists A ''list'' is any set of items. List or lists may also refer to: People * List (surname)List or Liste is a European surname. Notable people with the surname include: List * Friedrich List (1789–1846), German economist * Garrett List (1943 ...
, for example, are built up in many functional languages from two primitives: any list is either an empty list, commonly called ''nil''  ([]), or is constructed by prefixing an element in front of another list, creating what is called a ''cons'' 
node In general, a node is a localized swelling (a "knot A knot is an intentional complication in cordage which may be practical or decorative, or both. Practical knots are classified by function, including hitches, bend Bend or bends may refer t ...
Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil))))) ), resulting from application of a cons function (written down as a colon (:) in
Haskell Haskell may refer to: People * Haskell (surname) * Haskell (given name) Places United States * Haskell, Arkansas, a city * Haskell, Indiana, an unincorporated community * Haskell, New Jersey, an unincorporated community * Haskell, Oklahoma ...
). One can view a fold on lists as ''replacing''  the ''nil'' at the end of the list with a specific value, and ''replacing'' each ''cons'' with a specific function. 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. They also highlight the fact that foldr (:) [] is the identity function on lists (a ''shallow copy'' in Lisp (programming language), Lisp parlance), as replacing ''cons'' with cons and ''nil'' with nil will not change the result. The left fold diagram suggests an easy way to reverse a list, foldl (flip (:)) []. Note that the parameters to cons must be flipped, because the element to add is now the right hand parameter of the combining function. Another easy result to see from this vantage-point is to write the higher-order map function in terms of foldr, by composing the function to act on the elements with cons, as: map f = foldr ((:) . f) [] where the period (.) is an operator denoting Function composition (computer science), function composition. This way of looking at things provides a simple route to designing fold-like functions on other
algebraic data type In computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a particular task. Programming involves tasks such as analysis, gener ...
s and structures, like various sorts of trees. One writes a function which recursively replaces the constructors of the datatype with provided functions, and any constant values of the type with provided values. Such a function is generally referred to as a catamorphism.


On lists

The folding of the list ,2,3,4,5/code> with the addition operator would result in 15, the sum of the elements of the list ,2,3,4,5/code>. To a rough approximation, one can think of this fold as replacing the commas in the list with the + operation, giving 1 + 2 + 3 + 4 + 5. In the example above, + is an
associative operation In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a Validity (logic), valid rule ...
, so the final result will be the same regardless of parenthesization, although the specific way in which it is calculated will be different. In the general case of non-associative binary functions, the order in which the elements are combined may influence the final result's value. On lists, there are two obvious ways to carry this out: either by combining the first element with the result of recursively combining the rest (called a right fold), or by combining the result of recursively combining all elements but the last one, with the last element (called a left fold). This corresponds to a binary ''operator'' being either right-associative or left-associative, in
Haskell Haskell may refer to: People * Haskell (surname) * Haskell (given name) Places United States * Haskell, Arkansas, a city * Haskell, Indiana, an unincorporated community * Haskell, New Jersey, an unincorporated community * Haskell, Oklahoma ...
's or
Prolog Prolog is a logic programming Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some ...

Prolog
's terminology. With a right fold, the sum would be parenthesized as 1 + (2 + (3 + (4 + 5))), whereas with a left fold it would be parenthesized as (((1 + 2) + 3) + 4) + 5. In practice, it is convenient and natural to have an initial value which in the case of a right fold is used when one reaches the end of the list, and in the case of a left fold is what is initially combined with the first element of the list. In the example above, the value 0 (the
additive identity In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...
) would be chosen as an initial value, giving 1 + (2 + (3 + (4 + (5 + 0)))) for the right fold, and ((((0 + 1) + 2) + 3) + 4) + 5 for the left fold. For multiplication, an initial choice of 0 wouldn't work: 0 * 1 * 2 * 3 * 4 * 5 = 0. The
identity element In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
for multiplication is 1. This would give us the outcome 1 * 1 * 2 * 3 * 4 * 5 = 120 = 5!.


Linear vs. tree-like folds

The use of an initial value is necessary when the combining function ''f''  is asymmetrical in its types (e.g. a → b → b), i.e. when the type of its result is different from the type of the list's elements. Then an initial value must be used, with the same type as that of ''f'' 's result, for a ''linear'' chain of applications to be possible. Whether it will be left- or right-oriented will be determined by the types expected of its arguments by the combining function. If it is the second argument that must be of the same type as the result, then ''f''  could be seen as a binary operation that ''associates on the right'', and vice versa. When the function is a
magma Magma () is the molten or semi-molten natural material from which all igneous rock Igneous rock (derived from the Latin word ''ignis'' meaning fire), or magmatic rock, is one of the three main The three types of rocks, rock types, the others ...
, i.e. symmetrical in its types (a → a → a), and the result type is the same as the list elements' type, the parentheses may be placed in arbitrary fashion thus creating a ''tree'' of nested sub-expressions, e.g., ((1 + 2) + (3 + 4)) + 5. If the binary operation ''f''  is associative this value will be well-defined, i.e., same for any parenthesization, although the operational details of how it is calculated will be different. This can have significant impact on efficiency if ''f''  is non-strict. Whereas linear folds are node-oriented and operate in a consistent manner for each
node In general, a node is a localized swelling (a "knot A knot is an intentional complication in cordage which may be practical or decorative, or both. Practical knots are classified by function, including hitches, bend Bend or bends may refer t ...
of a
list A ''list'' is any set of items. List or lists may also refer to: People * List (surname)List or Liste is a European surname. Notable people with the surname include: List * Friedrich List (1789–1846), German economist * Garrett List (194 ...
, tree-like folds are whole-list oriented and operate in a consistent manner across ''groups'' of nodes.


Special folds for non-empty lists

One often wants to choose the
identity element In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
of the operation ''f'' as the initial value ''z''. When no initial value seems appropriate, for example, when one wants to fold the function which computes the maximum of its two parameters over a non-empty list to get the maximum element of the list, there are variants of foldr and foldl which use the last and first element of the list respectively as the initial value. In Haskell and several other languages, these are called foldr1 and foldl1, the 1 making reference to the automatic provision of an initial element, and the fact that the lists they are applied to must have at least one element. These folds use type-symmetrical binary operation: the types of both its arguments, and its result, must be the same. Richard Bird in his 2010 book proposesRichard Bird, "Pearls of Functional Algorithm Design", Cambridge University Press 2010, , p. 42 "a general fold function on non-empty lists" foldrn which transforms its last element, by applying an additional argument function to it, into a value of the result type before starting the folding itself, and is thus able to use type-asymmetrical binary operation like the regular foldr to produce a result of type different from the list's elements type.


Implementation


Linear folds

Using Haskell as an example, foldl and foldr can be formulated in a few equations. foldl :: (b -> a -> b) -> b -> -> b foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs If the list is empty, the result is the initial value. If not, fold the tail of the list using as new initial value the result of applying f to the old initial value and the first element. foldr :: (a -> b -> b) -> b -> -> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) If the list is empty, the result is the initial value z. If not, apply f to the first element and the result of folding the rest.


Tree-like folds

Lists can be folded over in a tree-like fashion, both for finite and for indefinitely defined lists: foldt f z [] = z foldt f z = f x z foldt f z xs = foldt f z (pairs f xs) foldi f z [] = z foldi f z (x:xs) = f x (foldi f z (pairs f xs)) pairs f (x:y:t) = f x y : pairs f t pairs _ t = t In the case of foldi function, to avoid its runaway evaluation on ''indefinitely'' defined lists the function f must ''not always'' demand its second argument's value, at least not all of it, or not immediately (see
example Example may refer to: * ''exempli gratia Notes and references Notes References Sources * * * Further reading * * {{Latin phrases E ...'' (e.g.), usually read out in English as "for example" * .example, reserved as a domain na ...
below).


Folds for non-empty lists

foldl1 f = x foldl1 f (x:y:xs) = foldl1 f (f x y : xs) foldr1 f = x foldr1 f (x:xs) = f x (foldr1 f xs) foldt1 f = x foldt1 f (x:y:xs) = foldt1 f (f x y : pairs f xs) foldi1 f = x foldi1 f (x:xs) = f x (foldi1 f (pairs f xs))


Evaluation order considerations

In the presence of lazy, or non-strict evaluation, foldr will immediately return the application of ''f'' to the head of the list and the recursive case of folding over the rest of the list. Thus, if ''f'' is able to produce some part of its result without reference to the recursive case on its "right" i.e., in its ''second'' argument, and the rest of the result is never demanded, then the recursion will stop (e.g., ). This allows right folds to operate on infinite lists. By contrast, foldl will immediately call itself with new parameters until it reaches the end of the list. This
tail recursion In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of compu ...
can be efficiently compiled as a loop, but can't deal with infinite lists at all — it will recurse forever in an
infinite loop In computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a particular task. Programming involves tasks such as analysis, ge ...
. 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. Were the function f to refer to its second argument first here, and be able to produce some part of its result without reference to the recursive case (here, on its ''left'' i.e., in its ''first'' argument), then the recursion would stop. This means that while foldr recurses ''on the right'', it allows for a lazy combining function to inspect list's elements from the left; and conversely, while foldl recurses ''on the left'', it allows for a lazy combining function to inspect list's elements from the right, if it so chooses (e.g., ). Reversing a list is also tail-recursive (it can be implemented using ). On ''finite'' lists, that means that left-fold and reverse can be composed to perform a right fold in a tail-recursive way (cf.  ), with a modification to the function f so it reverses the order of its arguments (i.e., ), tail-recursively building a representation of expression that right-fold would build. The extraneous intermediate list structure can be eliminated with the
continuation-passing style In functional programming, continuation-passing style (CPS) is a style of programming in which control flow, control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. G ...
technique, ; similarly, ( flip is only needed in languages like Haskell with its flipped order of arguments to the combining function of foldl unlike e.g., in Scheme where the same order of arguments is used for combining functions to both foldl and ). Another technical point is that, in the case of left folds using lazy evaluation, the new initial parameter is not being evaluated before the recursive call is made. 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. In Haskell this is the foldl' (note the apostrophe, pronounced 'prime') function in the Data.List library (one needs to be aware of the fact though that forcing a value built with a lazy data constructor won't force its constituents automatically by itself). 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.


Examples

Using a
Haskell Haskell may refer to: People * Haskell (surname) * Haskell (given name) Places United States * Haskell, Arkansas, a city * Haskell, Indiana, an unincorporated community * Haskell, New Jersey, an unincorporated community * Haskell, Oklahoma ...
interpreter, the structural transformations which fold functions perform can be illustrated by constructing a string: λ> foldr (\x y -> concat (",x,"+",y,")" "0" (map show ..13 "(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))" λ> foldl (\x y -> concat (",x,"+",y,")" "0" (map show ..13 "(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)" λ> foldt (\x y -> concat (",x,"+",y,")" "0" (map show ..13 "(((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)" λ> foldi (\x y -> concat (",x,"+",y,")" "0" (map show ..13 "(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))" Infinite tree-like folding is demonstrated e.g., in
recursive Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics Linguistics is the scientific study of language A lan ...
primes production by unbounded sieve of Eratosthenes in
Haskell Haskell may refer to: People * Haskell (surname) * Haskell (given name) Places United States * Haskell, Arkansas, a city * Haskell, Indiana, an unincorporated community * Haskell, New Jersey, an unincorporated community * Haskell, Oklahoma ...

Haskell
: primes = 2 : _Y ((3 :) . minus ,7... foldi (\(x:xs) ys -> x : union xs ys) [] . map (\p-> [p*p, p*p+2*p..])) _Y g = g (_Y g) -- = g . g . g . g . ... where the function Haskell features#union, union operates on ordered lists in a local manner to efficiently produce their Union (set theory), set union, and Haskell features#minus, minus their Complement (set theory)#Relative complement, set difference. For finite lists, e.g., merge sort (and its duplicates-removing variety, nubsort) could be easily defined using tree-like folding as mergesort xs = foldt merge [] [ , x <- xs] nubsort xs = foldt union [] [ , x <- xs] with the function Haskell 98 features#Mergesort, merge a duplicates-preserving variant of union. Functions head and last could have been defined through folding as head = foldr (\x r -> x) (error "head: Empty list") last = foldl (\a x -> x) (error "last: Empty list")


In various languages

, '' , '' , , also DefaultListModel and HashTable implement to-Iterator , - style="vertical-align: top;" , D (programming language), D , reduce!''func''(''initval'', ''list'') , reduce!''func''(''initval'', ''list''.reverse) , reduce!''func''(''list'') , reduce!''func''(''list''.reverse) , , in module std.algorithm , - style="vertical-align: top;" , Elixir (programming language), Elixir , List.foldl(list, acc, fun) , List.foldr(list, acc, fun) , , , , Se
documentation
for example usage , - style="vertical-align: top;" , Elm (programming language), Elm , List.foldl(''Fun'', ''Accumulator'', ''List'') , List.foldr(''Fun'', ''Accumulator'', ''List'') , , , , See also List AP

, - style="vertical-align: top;" , Erlang (programming language), Erlang , lists:foldl(''Fun'', ''Accumulator'', ''List'') , lists:foldr(''Fun'', ''Accumulator'', ''List'') , , , , , - style="vertical-align: top;" , F Sharp (programming language), F# , Seq/List.fold ''func'' ''initval'' ''list'' , List.foldBack ''func'' ''list'' ''initval'' , Seq/List.reduce ''func'' ''list'' , List.reduceBack ''func'' ''list'' , Seq.unfold ''func'' ''initval'' , , - style="vertical-align: top;" , Gosu (programming language), Gosu , ''Iterable''.fold(''f''(agg, e))''Iterable''.reduce(init, ''f''(agg, e)) ''Iterable''.partition(''f''(e)) , , , , , All are extension methods on Java's Iterable interface, arrays are also supported , - style="vertical-align: top;" , Groovy (programming language), Groovy , ''list''.inject(''initval'', ''func'') , ''list''.reverse().inject(''initval'', ''func'') , ''list''.inject(''func'') , ''list''.reverse().inject(''func'') , , , - style="vertical-align: top;" ,
Haskell Haskell may refer to: People * Haskell (surname) * Haskell (given name) Places United States * Haskell, Arkansas, a city * Haskell, Indiana, an unincorporated community * Haskell, New Jersey, an unincorporated community * Haskell, Oklahoma ...
, foldl ''func'' ''initval'' ''list'' , foldr ''func'' ''initval'' ''list'' , foldl1 ''func'' ''list'' , foldr1 ''func'' ''list'' , unfoldr ''func'' ''initval'' , For foldl, the folding function takes arguments in the opposite order as that for foldr. , - style="vertical-align: top;" , Haxe , Lambda.fold(''iterable'', ''func'', ''initval'') , , , , , , - style="vertical-align: top;" , J (programming language), J , ''verb''~/, . ''initval'',''array'' , ''verb''/ ''array'',''initval'' , ''verb''~/, . ''array'' , ''verb''/ ''array'' , , u/y applies the dyad u between the items of y
"J Dictionary: Insert"
, - style="vertical-align: top;" , Java (programming language), Java 8+ , ''stream''.reduce(''initval'', ''func'') , , ''stream''.reduce(''func'') , , , , - style="vertical-align: top;" , JavaScript 1.8
ECMAScript 5 , ''array''.reduce(''func'', ''initval'') , , ''array''.reduce(''func'') , , , , - style="vertical-align: top;" , Julia (programming language), Julia , foldl(''op'', ''itr''; [init]) , foldr(''op'', ''itr''; [init]) , foldl(''op'', ''itr'') , foldr(''op'', ''itr'') , , , - , Kotlin (programming language), Kotlin , ''Iterable''.fold(''initval'', ''func'') , ''Iterable''.foldRight(''initval'', ''func'') , ''Iterable''.reduce''(func'') , ''Iterable''.reduceRight''(func'') , , Other collections also support fold and reduce. There is also Result.fold(onSuccess, onFailure), which reduces a Result (either success or failure) to the return type of onSuccess and onFailure. , - style="vertical-align: top;" , LFE (programming language), LFE , (lists:foldl ''func'' ''accum'' ''list'') , (lists:foldr ''func'' ''accum'' ''list'') , , , , , - style="vertical-align: top;" , Logtalk , fold_left(Closure, Initial, List, Result) , fold_right(Closure, Initial, List, Result) , , , , Meta-predicates provided by the ''meta'' standard library object. The abbreviations ''foldl'' and ''foldr'' may also be used. , - style="vertical-align: top;" , Maple (software), Maple , foldl(''func'', ''initval'', ''sequence'') , foldr(''func'', ''initval'', ''sequence'') , , , , , - style="vertical-align: top;" , Mathematica , Fold[''func'', ''initval'', ''list''] , Fold[''func'', ''initval'', Reverse[''list'' , Fold[''func'', ''list''] , Fold[''func'', Reverse[''list'' , NestWhileList[''func,'', ''initval'', ''predicate''] , Fold without an initial value is supported in versions 10.0 and higher. , - style="vertical-align: top;" , MATLAB , fold(@''func'', ''list'', ''defaultVal'') , fold(@''func'', flip(''list''), ''defaultVal'') , fold(@''func'', ''list'') , fold(@''func'', flip(''list'')) , , Requires Symbolic Math Toolbox, supported from R2016b. , - style="vertical-align: top;" , Maxima (software), Maxima , lreduce(''func'', ''list'', ''initval'') , rreduce(''func'', ''list'', ''initval'') , lreduce(''func'', ''list'') , rreduce(''func'', ''list'') , , , - style="vertical-align: top;" , Mythryl , fold_left ''func'' ''initval'' ''list''
vector::fold_left ''func'' ''initval'' ''vector''
, fold_right ''func'' ''initval'' ''list''
vector::fold_right ''func'' ''initval'' ''vector''
, , , , The supplied function takes its arguments in a tuple. , - style="vertical-align: top;" , OCaml , List.fold_left ''func'' ''initval'' ''list''
Array.fold_left ''func'' ''initval'' ''array''
, List.fold_right ''func'' ''list'' ''initval''
Array.fold_right ''func'' ''array'' ''initval''
, , , Base.Sequence.unfold ''~init'' ''~f'' , , - style="vertical-align: top;" , Oz (programming language), Oz , , , , , , , - style="vertical-align: top;" , PARI/GP , fold( ''f'', ''A'' ) , , , , , , - style="vertical-align: top;" , Perl , reduce ''block'' ''initval'', ''list'' , , reduce ''block'' ''list'' , , , in List::Util module , - style="vertical-align: top;" , PHP , array_reduce(''array'', ''func'', ''initval'') , array_reduce(array_reverse(''array''), ''func'', ''initval'') , array_reduce(''array'', ''func'') , array_reduce(array_reverse(''array''), ''func'') , , When ''initval'' is not supplied, NULL is used, so this is not a true foldl1. Before PHP 5.3, ''initval'' can only be integer. "func" is
callback
Tr
array_reduce
online. , - style="vertical-align: top;" , Python (programming language), Python 2.x , reduce(''func'', ''list'', ''initval'') , reduce(lambda x,y: ''func''(y,x), reversed(''list''), ''initval'') , reduce(''func'', ''list'') , reduce(lambda x,y: ''func''(y,x), reversed(''list'')) , , , - style="vertical-align: top;" , Python (programming language), 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
'. , - style="vertical-align: top;" , R (programming language), R , Reduce(''func'', ''list'', ''initval'') , Reduce(''func'', ''list'', ''initval'', right=TRUE) , Reduce(''func'', ''list'') , Reduce(''func'', ''list'', right=TRUE) , , R supports right folding and left or right folding with or without an initial value through the ''right'' and ''init'' arguments to the Reduce function. , - style="vertical-align: top;" , Ruby (programming language), Ruby , ''enum''.inject(''initval'', ''&block'')
''enum''.reduce(''initval'', ''&block'')
, ''enum''.reverse_each.inject(''initval'', ''&block'')
''enum''.reverse_each.reduce(''initval'', ''&block'')
, ''enum''.inject(''&block'')
''enum''.reduce(''&block'')
, ''enum''.reverse_each.inject(''&block'')
''enum''.reverse_each.reduce(''&block'')
, , In Ruby 1.8.7+, can also pass a symbol representing a function instead of a block.
''enum'' is an Enumeration
Please notice that these implementations of right folds are wrong for non-commutative ''&block'' (also initial value is put on wrong side). , - style="vertical-align: top;" , Rust (programming language), Rust , ''iterator''.fold(''initval'', ''func'') , ''iterator''.rev().fold(''initval'', ''func'') , , , , ''iterator''.rev() requires ''iterator'' to be a DoubleEndedIterator. , - style="vertical-align: top;" , Scala (programming language), Scala , ''list''.foldLeft(''initval'')(''func'')
(''initval'' /: ''list'')(''func'') , ''list''.foldRight(''initval'')(''func'')
(''list'' :\ ''initval'')(''func'') , ''list''.reduceLeft(''func'') , ''list''.reduceRight(''func'') , , Scala's symbolic fold syntax was intended to resemble the left- or right-leaning tree commonly used to explain the fold operation, but has since been reinterpreted as an illustration of a toppling domino. The colon comes from a general Scala syntax mechanism whereby the apparent infix operator is invoked as a method on the left operand with the right operand passed as an argument, or vice versa if the operator's last character is a colon, here applied symmetrically. Scala also features the tree-like folds using the method list.fold(z)(op). , - style="vertical-align: top;" , Scheme (programming language), Scheme R6RS , (fold-left ''func'' ''initval'' ''list'')
(vector-fold ''func'' ''initval'' ''vector'')
, (fold-right ''func'' ''initval'' ''list'')
(vector-fold-right ''func'' ''initval'' ''vector'')
, (reduce-left ''func'' ''defaultval'' ''list'') , (reduce-right ''func'' ''defaultval'' ''list'') , (unfold ''p'' ''f'' ''g'' ''seed'' ''[tail-gen]'')
unfold-right ''p'' ''f'' ''g'' ''seed'' ''[tail]''
(vector-unfold ''f'' ''length'' ''initial-seed'' ''···'')
(vector-unfold-right ''f'' ''length'' ''initial-seed'' ''···'') , srfi/1 srfi/43 , - style="vertical-align: top;" , Smalltalk , ''aCollection'' inject: ''aValue'' into: ''aBlock'' , , ''aCollection'' reduce: ''aBlock'' , , , ANSI Smalltalk doesn't define #reduce: but many implementations do. , - style="vertical-align: top;" , Standard ML , foldl ''func'' ''initval'' ''list''
Array.foldl ''func'' ''initval'' ''array''
, foldr ''func'' ''initval'' ''list''
Array.foldr ''func'' ''initval'' ''array''
, , , , The supplied function takes its arguments in a tuple. For foldl, the folding function takes arguments in the same order as for foldr. , - style="vertical-align: top;" , Swift (programming language), Swift , ''array''.reduce(''initval'', ''func'')
reduce(''sequence'', ''initval'', ''func'')
, ''array''.reverse().reduce(''initval'', ''func'') , , , , , - style="vertical-align: top;" , XPath 3, XPath 3.1 , } , } , , , , In XPath 3.1 due to historical reasons the array and sequence types are incompatible -- thus the need for separate fold functions for array and for sequence The difference in the signatures is due to the fact that the value of an array item can be a sequence, while XPath doesn't have sequence of sequences , - style="vertical-align: top;" , Xtend , ''iterable''.fold(''initval'',[''func'']) , , ''iterable''.reduce[''func''] , , ,


Universality

Fold is a Type polymorphism, polymorphic function. For any ''g'' having a definition g [] = v g (x:xs) = f x (g xs) then ''g'' can be expressed as g = foldr f v Also, in a lazy language with infinite lists, a fixed point combinator can be implemented via fold, proving that iterations can be reduced to folds: y f = foldr (\_ -> f) undefined (repeat undefined)


See also

* Aggregate function * Iterated binary operation * Catamorphism, a generalization of fold * Homomorphism * Map (higher-order function) * Prefix sum * Recursive data type * Reduction Operator * Recursion (computer science)#Recursive data structures (structural recursion), Structural recursion


References


External links


"Higher order functions — map, fold and filter"



"Fold in Tcl"

"Constructing List Homomorphism from Left and Right Folds"

"The magic foldr"
{{Data structures and algorithms Higher-order functions Recursion Programming language comparisons Articles with example Haskell code Articles with example Scheme (programming language) code Iteration in programming