Infunctional programming, afold is ahigher-order function thatanalyzes arecursive data structure and, through use of a given combining operation, recombines the results ofrecursively processing its constituent parts, building up a return value. Fold is also termed asreduce,accumulate,aggregate,compress, orinject. Typically, a fold is presented with a combiningfunction, a topnode of adata structure, and possibly some default values to be used under certain conditions. The fold then proceeds to combine elements of the data structure'shierarchy, using the function in a systematic way.
Folds are in a sense dual tounfolds, which take aseed value and apply a functioncorecursively 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 itsterminal values and the recursive results (catamorphism, versusanamorphism of unfolds).
 | This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(June 2013) (Learn how and when to remove this message) |
Folds can be regarded as consistently replacing the structural components of a data structure with functions and values.Lists, for example, are built up in many functional languages from two primitives: any list is either an empty list, commonly callednil ([]), or is constructed by prefixing an element in front of another list, creating what is called acons node ( Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil))))) ), resulting from application of acons function (written down as a colon(:) inHaskell). One can view a fold on lists asreplacing thenil at the end of the list with a specific value, andreplacing eachcons 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 illustrateright andleft fold of a list visually. They also highlight the fact thatfoldr (:) [] is the identity function on lists (ashallow copy inLisp parlance), as replacingcons withcons andnil withnil 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-ordermap function in terms offoldr, by composing the function to act on the elements withcons, as:
mapf=foldr((:).f)[]
where the period (.) is an operator denotingfunction composition.
This way of looking at things provides a simple route to designing fold-like functions on otheralgebraic data types 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 acatamorphism.
The folding of the list[1,2,3,4,5] with the addition operator would result in 15, the sum of the elements of the list[1,2,3,4,5]. To a rough approximation, one can think of this fold as replacing the commas in the list with the + operation, giving1 + 2 + 3 + 4 + 5.[1]
In the example above, + is anassociative operation, 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 aright fold), or by combining the result of recursively combining all elements but the last one, with the last element (called aleft fold). This corresponds to a binaryoperator being either right-associative or left-associative, inHaskell's orProlog's terminology. With a right fold, the sum would be parenthesized as1 + (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 (theadditive identity) would be chosen as an initial value, giving1 + (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. Theidentity element for multiplication is 1. This would give us the outcome1 * 1 * 2 * 3 * 4 * 5 = 120 = 5!.
The use of an initial value is necessary when the combining functionf 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 off 's result, for alinear 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, thenf could be seen as a binary operation thatassociates on the right, and vice versa.
When the function is amagma, 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 abinary tree of nested sub-expressions, e.g.,((1 + 2) + (3 + 4)) + 5. If the binary operationf 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 iff isnon-strict.
Whereas linear folds arenode-oriented and operate in a consistent manner for eachnode of alist, tree-like folds are whole-list oriented and operate in a consistent manner acrossgroups of nodes.
One often wants to choose theidentity element of the operationf as the initial valuez. 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 offoldr andfoldl which use the last and first element of the list respectively as the initial value. In Haskell and several other languages, these are calledfoldr1 andfoldl1, 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 proposes[2] "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 regularfoldr to produce a result of type different from the list's elements type.
Using Haskell as an example,foldl andfoldr can be formulated in a few equations.
foldl::(b->a->b)->b->[a]->bfoldlfz[]=zfoldlfz(x:xs)=foldlf(fzx)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->[a]->bfoldrfz[]=zfoldrfz(x:xs)=fx(foldrfzxs)
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.
Lists can be folded over in a tree-like fashion, both for finite and for indefinitely defined lists:
foldtfz[]=zfoldtfz[x]=fxzfoldtfzxs=foldtfz(pairsfxs)foldifz[]=zfoldifz(x:xs)=fx(foldifz(pairsfxs))pairsf(x:y:t)=fxy:pairsftpairs_t=t
In the case offoldi function, to avoid its runaway evaluation onindefinitely defined lists the functionf mustnot always demand its second argument's value, at least not all of it, or not immediately (seeexample below).
foldl1f[x]=xfoldl1f(x:y:xs)=foldl1f(fxy:xs)foldr1f[x]=xfoldr1f(x:xs)=fx(foldr1fxs)foldt1f[x]=xfoldt1f(x:y:xs)=foldt1f(fxy:pairsfxs)foldi1f[x]=xfoldi1f(x:xs)=fx(foldi1f(pairsfxs))
In the presence oflazy, ornon-strict evaluation,foldr will immediately return the application off to the head of the list and the recursive case of folding over the rest of the list. Thus, iff is able to produce some part of its result without reference to the recursive case on its "right" i.e., in itssecond argument, and the rest of the result is never demanded, then the recursion will stop (e.g.,head==foldr(\ab->a)(error"empty list")). 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. Thistail recursion can be efficiently compiled as a loop, but can't deal with infinite lists at all — it will recurse forever in aninfinite loop.
Having reached the end of the list, anexpression is in effect built byfoldl of nested left-deepeningf-applications, which is then presented to the caller to be evaluated. Were the functionf 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 itsleft i.e., in itsfirst argument), then the recursion would stop. This means that whilefoldr recurseson the right, it allows for a lazy combining function to inspect list's elements from the left; and conversely, whilefoldl recurseson the left, it allows for a lazy combining function to inspect list's elements from the right, if it so chooses (e.g.,last==foldl(\ab->b)(error"empty list")).
Reversing a list is also tail-recursive (it can be implemented usingrev=foldl(\ysx->x:ys)[]). Onfinite lists, that means that left-fold and reverse can be composed to perform a right fold in a tail-recursive way (cf. 1+>(2+>(3+>0))==((0<+3)<+2)<+1), with a modification to the functionf so it reverses the order of its arguments (i.e.,foldrfz==foldl(flipf)z.foldl(flip(:))[]), tail-recursively building a representation of expression that right-fold would build. The extraneous intermediate list structure can be eliminated with thecontinuation-passing style technique,foldrfzxs==foldl(\kx->k.fx)idxsz; similarly,foldlfzxs==foldr(\xk->k.flipfx)idxsz ( flip is only needed in languages like Haskell with its flipped order of arguments to the combining function offoldl unlike e.g., in Scheme where the same order of arguments is used for combining functions to bothfoldl andfoldr).
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 thefoldl' (note the apostrophe, pronounced 'prime') function in theData.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.
Using aHaskell interpreter, the structural transformations which fold functions perform can be illustrated by constructing a string:
λ>foldr(\xy->concat["(",x,"+",y,")"])"0"(mapshow[1..13])"(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))"λ>foldl(\xy->concat["(",x,"+",y,")"])"0"(mapshow[1..13])"(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)"λ>foldt(\xy->concat["(",x,"+",y,")"])"0"(mapshow[1..13])"(((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)"λ>foldi(\xy->concat["(",x,"+",y,")"])"0"(mapshow[1..13])"(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))"
Infinite tree-like folding is demonstrated e.g., inrecursive primes production byunbounded sieve of Eratosthenes inHaskell:
primes=2:_Y((3:).minus[5,7..].foldi(\(x:xs)ys->x:unionxsys)[].map(\p->[p*p,p*p+2*p..]))_Yg=g(_Yg)-- = g . g . g . g . ...
where the functionunion operates on ordered lists in a local manner to efficiently produce theirset union, andminus theirset difference.
A finite prefix of primes is concisely defined as a folding of set difference operation over the lists of enumerated multiples of integers, as
primesTon=foldl1minus[[2*x,3*x..n]|x<-[1..n]]
For finite lists, e.g.,merge sort (and its duplicates-removing variety,nubsort) could be easily defined using tree-like folding as
mergesortxs=foldtmerge[][[x]|x<-xs]nubsortxs=foldtunion[][[x]|x<-xs]
with the functionmerge a duplicates-preserving variant ofunion.
Functionshead andlast could have been defined through folding as
head=foldr(\xr->x)(error"head: Empty list")last=foldl(\ax->x)(error"last: Empty list")
| Language | Left fold | Right fold | Left fold without initial value | Right fold without initial value | Unfold | Notes |
|---|---|---|---|---|---|---|
| APL | func | func/vector,initval | func | func/vector | ||
| C#3.0 | ienum | ienum.Reverse() | ienum | ienum.Reverse() | Aggregate is anextension methodienum is anIEnumerable<T>Similarly in all .NET languages | |
| C++ | std::accumulate( | std::accumulate( | in header<numeric>begin,end,rbegin,rend are iteratorsfunc can be afunction pointer or afunction object | |||
| C++17 | (initvalop ...oppack) | (packop ...opinitval) | (...oppack) | (packop ...) | Fold expression (only forvariadic templates):op is a binary operator (bothops must be the same, e.g.,(std::cout<<...<<args)),pack is an unexpanded parameter pack. | |
| C++23 | std::ranges::fold_left(range,initval,func) | std::ranges::fold_right(range,initval,func) | std::ranges::fold_left_first(range,func) | std::ranges::fold_right_last(range,func) | Bothstd::ranges::fold_left_first andstd::ranges::fold_right_last returnstd::optional considering the emptiness ofrange. | |
| CFML | obj.reduce(func,initial) | obj.reduce(func) | Wherefunc receives as arguments the result of the previous operation (or theinitial value on the first iteration); the current item; the current item's index or key; and a reference to theobj | |||
| Clojure | (reducefuncinitvallist) | (reducefuncinitval (reverselist)) | (reducefunclist) | (reducefunc (reverselist)) | See alsoclojure.core.reducers/fold | |
| Common Lisp | (reducefunclist :initial-valueinitval) | (reducefunclist :from-end t :initial-valueinitval) | (reducefunclist) | (reducefunclist :from-end t) | ||
| D | reduce!func(initval,list) | reduce!func(initval,list | reduce!func(list) | reduce!func( | in modulestd.algorithm | |
| Elixir | List.foldl(list,acc,fun) | List.foldr(list,acc,fun) | Seedocumentation for example usage | |||
| Elm | List.foldl(Fun,Accumulator,List) | List.foldr(Fun,Accumulator,List) | See also List API[1] | |||
| Erlang | lists:foldl(Fun,Accumulator,List) | lists:foldr(Fun,Accumulator,List) | ||||
| F# | List.foldfuncinitvallistSeq.foldfuncinitvalsequence | List.foldBackfunclistinitval | List.reducefunclistSeq.reducefuncsequence | List.reduceBackfunclist | Seq.unfoldfuncinitval | |
| Gleam | list.fold(list,initial,func)yielder.fold(yielder,initial,func) | list.fold_right(list,initial,func) | list.reduce(list,func)yielder.reduce(yielder,func) | yielder.unfold(initial,func) | ||
| Gosu | Iterable.fold(f(agg, e))Iterable.reduce(init,f(agg, e))Iterable.partition(f(e)) | All areextension methods on Java'sIterable interface, arrays are also supported | ||||
| Groovy | list | list.reverse() | list | list.reverse() | ||
| Haskell | foldlfuncinitvallist | foldrfuncinitvallist | foldl1funclist | foldr1funclist | unfoldrfuncinitval | Forfoldl, the folding function takes arguments in the opposite order as that forfoldr. |
| Haxe | Lambda.fold(iterable,func,initval) | |||||
| J | verb | verb/array,initval | verb | verb/array | u/y applies the dyad u between the items of y."J Dictionary: Insert" | |
| Java 8+ | stream.reduce | stream.reduce | ||||
| JavaScript 1.8 ECMAScript 5 | array.reduce[3] | array.reduceRight(func,initVal) | array.reduce | array.reduceRight(func) | The reducer main arguments are accumulator and current value, and we can use optional arguments like index and array.array.reduceRight((acc,value,idx,array)=>{},initvalue) | |
| Julia | foldl(op,itr; [init]) | foldr(op,itr; [init]) | foldl(op,itr) | foldr(op,itr) | ||
| Kotlin | Iterable.fold | Iterable.foldRight | Iterable.reduce(func) | Iterable.reduceRight(func) | Other collections also supportfold[4] andreduce.[5] There is alsoResult.fold(onSuccess, onFailure),[6] which reduces aResult<T> (either success or failure) to the return type ofonSuccess andonFailure. | |
| LFE | (lists:foldlfuncaccumlist) | (lists:foldrfuncaccumlist) | ||||
| Logtalk | fold_left(Closure, Initial, List, Result) | fold_right(Closure, Initial, List, Result) | Meta-predicates provided by themeta standard library object. The abbreviationsfoldl andfoldr may also be used. | |||
| Maple | foldl(func,initval,sequence) | foldr(func,initval,sequence) | foldl(func,sequence) | foldr(func,sequence) | ||
| 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. |
| MATLAB | fold(@func,list,defaultVal) | fold(@func, flip(list),defaultVal) | fold(@func,list) | fold(@func, flip(list)) | | Requires Symbolic Math Toolbox, supported from R2016b. |
| Maxima | lreduce(func,list,initval) | rreduce(func,list,initval) | lreduce(func,list) | rreduce(func,list) | ||
| OCaml | List.fold_leftfuncinitvallistArray.fold_leftfuncinitvalarray | List.fold_rightfunclistinitvalArray.fold_rightfuncarrayinitval | ||||
| Oz | {FoldLListFuncInitVal} | {FoldRListFuncInitVal} | ||||
| PARI/GP | fold(f,A ) | |||||
| Perl | reduceblockinitval,list | reduceblocklist | inList::Util module | |||
| PHP | array_reduce(array,func,initval) | array_reduce( | array_reduce(array,func) | array_reduce( | Wheninitval is not supplied, NULL is used, so this is not a true foldl1. Before PHP 5.3,initval can only be integer.func is acallbackArchived 2020-11-28 at theWayback Machine. Tryarray_reduce online. | |
| Python 2.x | reduce(func,list,initval) | | reduce(func,list) | | ||
| Python 3.x | functools.reduce(func,list,initval) | | functools.reduce(func,list) | | In modulefunctools.[7] | |
| 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 theright andinit arguments to theReduce function. | |
| Racket | (foldlfunc initvallist) | (foldrfunc initvallist) | ||||
| Ruby | enumenum | enum.reverse_eachenum.reverse_each | enumenum.reduce(&block) | enum.reverse_eachenum.reverse_each | In Ruby 1.8.7+, can also pass a symbol representing a function instead of a block.enum is an EnumerationPlease notice that these implementations of right folds are wrong for non-commutative &block (also initial value is put on wrong side). | |
| Rust | iterator.fold(initval,func) | iterator.rev().fold(initval,func) | iterator.reduce(func) | iterator.rev().reduce(func) | iterator.rev() requiresiterator to be aDoubleEndedIterator.[8] | |
| 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,[9] but has since been reinterpreted as an illustration of a toppling domino.[10] 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 | |
| Scheme R6RS | (fold-leftfuncinitvallist)(vector-foldfuncinitvalvector) | (fold-rightfuncinitvallist)(vector-fold-rightfuncinitvalvector) | (reduce-leftfuncdefaultvallist) | (reduce-rightfuncdefaultvallist) | (unfoldpfgseed[tail-gen])unfold-rightpfgseed[tail](vector-unfoldflengthinitial-seed···)(vector-unfold-rightflengthinitial-seed···) | srfi/1 srfi/43 |
| Smalltalk | aCollection inject:aValue into:aBlock | aCollection reduce:aBlock | ANSI Smalltalk doesn't define#reduce: but many implementations do. | |||
| Standard ML | foldlfuncinitvallistArray.foldlfuncinitvalarray | foldrfuncinitvallistArray.foldrfuncinitvalarray | The supplied function takes its arguments in a tuple. Forfoldl, the folding function takes arguments in the same order as forfoldr. | |||
| Swift | array.reduce(initval,func)reduce(sequence,initval,func) | array.reverse() | ||||
| XPath | fold-left($input,$zero,$action)array:fold-left($input,$zero,$action) | fold-right($input,$zero,$action)array:fold-right($input,$zero,$action) | Two functions exist for each case because XPath offerssequences for unstructured andarrays for structured data. | |||
| Xtend | iterable.fold(initval,[func]) | iterable.reduce[func] |
Fold is apolymorphic function. For anyg having a definition
g[]=vg(x:xs)=fx(gxs)
theng can be expressed as[12]
g=foldrfv
Also, in alazy language with infinite lists, afixed point combinator can be implemented via fold,[13] proving that iterations can be reduced to folds:
yf=foldr(\_->f)undefined(repeatundefined)
functools.reduce:import functoolsreduce:from functools import reduce