As structural transformations
Folds can be regarded as consistently replacing the structural components of a data structure with functions and values.[]
), or is constructed by prefixing an element in front of another list, creating what is called a ''cons'' Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil)))))
), resulting from application of a cons
function (written down as a colon (:)
in 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:
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 valid rule of replacement f ...
, 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 () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
's or Prolog
Prolog is a logic programming language associated with artificial intelligence and computational linguistics.
Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primarily ...
'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, the additive identity of a set that is equipped with the operation of addition is an element which, when added to any element ''x'' in the set, yields ''x''. One of the most familiar additive identities is the number 0 from elemen ...
) 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, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
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 rocks are formed. Magma is found beneath the surface of the Earth, and evidence of magmatism has also been discovered on other terrestrial planets and some natural sa ...
, 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 binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
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") or a point of intersection (a vertex).
Node may refer to:
In mathematics
* Vertex (graph theory), a vertex in a mathematical graph
*Vertex (geometry), a point where two or more curves, lines ...
of a list
A ''list'' is any set of items in a row. List or lists may also refer to:
People
* List (surname)
Organizations
* List College, an undergraduate division of the Jewish Theological Seminary of America
* SC Germania List, German rugby union ...
, 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, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
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'' (e.g.), usually read out in English as "for example"
* .example, reserved as a domain name that may not be installed as a top-level domain of the Internet
** example.com, example.net, example.org, ex ...
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, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
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, an infinite loop (or endless loop) is a sequence of instructions that, as written, will continue endlessly, unless an external intervention occurs ("pull the plug"). It may be intentional.
Overview
This differs from:
* ...
.
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 is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Suss ...
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 () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
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 to logic. The most common application of recursion is in mathematics ...
primes production by unbounded sieve of Eratosthenes in Haskell
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
:
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 set union
In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection. It is one of the fundamental operations through which sets can be combined and related to each other.
A refers to a union of ze ...
, and minus
their set difference
In set theory, the complement of a set , often denoted by (or ), is the set of elements not in .
When all sets in the universe, i.e. all sets under consideration, are considered to be members of a given set , the absolute complement of is the ...
.
A finite prefix of primes is concisely defined as a folding of set difference operation over the lists of enumerated multiples of integers, as
primesTo n = foldl1 minus 2*x,3*x..n, x <- ..n
For finite lists, e.g., merge sort
In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same ...
(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 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
, 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
ELIXIR (the European life-sciences Infrastructure for biological Information) is an initiative that will allow life science laboratories across Europe to share and store their research data as part of an organised network. Its goal is to bring t ...
, List.foldl(list, acc, fun)
, List.foldr(list, acc, fun)
,
,
,
, Se
documentation
for example usage
, - style="vertical-align: top;"
, Elm
Elms are deciduous and semi-deciduous trees comprising the flowering plant genus ''Ulmus'' in the plant family Ulmaceae. They are distributed over most of the Northern Hemisphere, inhabiting the temperate and tropical-montane regions of North ...
, 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#
, 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
Gosu (고수) is a Korean term used to refer to a highly skilled person. In computer gaming the term is usually used to refer to a person who dominated games like ''StarCraft'', ''Counter-Strike'', Tekken, ''Warcraft III'', ''Diablo II
''D ...
, ''Iterable''.fold(''f''(agg, e)) ''Iterable''.reduce(init, ''f''(agg, e)) ''Iterable''.partition(''f''(e))
,
,
,
,
, All are extension methods
In object-oriented computer programming, an extension method is a method added to an object after the original object was compiled. The modified object is often a class, a prototype or a type. Extension methods are features of some object-orie ...
on Java's Iterable interface, arrays are also supported
, - style="vertical-align: top;"
, Groovy
''Groovy'' (or, less commonly, ''groovie'' or ''groovey'') is a slang colloquialism popular during the 1950s, '60s and '70s. It is roughly synonymous with words such as "excellent", "fashionable", or "amazing", depending on context.
History
The ...
, ''list'' .inject(''initval'', ''func'')
, ''list''.reverse() .inject(''initval'', ''func'')
, ''list'' .inject(''func'')
, ''list''.reverse() .inject(''func'')
,
,
, - style="vertical-align: top;"
, Haskell
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
, 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
Haxe is an open source high-level cross-platform programming language and compiler that can produce applications and source code, for many different computing platforms from one code-base. It is free and open-source software, released under the ...
, Lambda.fold(''iterable'', ''func'', ''initval'')
,
,
,
,
,
, - style="vertical-align: top;"
, 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
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's List ...
8+
, ''stream''.reduce (''initval'', ''func'')
,
, ''stream''.reduce (''func'')
,
,
,
, - style="vertical-align: top;"
, JavaScript
JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of Website, websites use JavaScript on the Client (computing), client side ...
1.8
ECMAScript
ECMAScript (; ES) is a JavaScript standard intended to ensure the interoperability of web pages across different browsers. It is standardized by Ecma International in the documenECMA-262
ECMAScript is commonly used for client-side scripting o ...
5
, ''array''.reduce (''func'', ''initval'')
,
, ''array''.reduce (''func'')
,
,
,
, - style="vertical-align: top;"
, Julia
Julia is usually a feminine given name. It is a Latinate feminine form of the name Julio and Julius. (For further details on etymology, see the Wiktionary entry "Julius".) The given name ''Julia'' had been in use throughout Late Antiquity (e.g ...
, foldl(''op'', ''itr''; nit
, foldr(''op'', ''itr''; nit
, foldl(''op'', ''itr'')
, foldr(''op'', ''itr'')
,
,
, -
, 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
, (lists:foldl ''func'' ''accum'' ''list'')
, (lists:foldr ''func'' ''accum'' ''list'')
,
,
,
,
, - style="vertical-align: top;"
, Logtalk
Logtalk is an object-oriented logic programming language that extends and leverages the Prolog language with a feature set suitable for programming in the large.Paulo Moura (2003). Logtalk: Design of an Object-Oriented Logic Programming Language. ...
, 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
''Acer'' () is a genus of trees and shrubs commonly known as maples. The genus is placed in the family Sapindaceae.Stevens, P. F. (2001 onwards). Angiosperm Phylogeny Website. Version 9, June 2008 nd more or less continuously updated since http ...
, foldl(''func'', ''initval'', ''sequence'')
, foldr(''func'', ''initval'', ''sequence'')
,
,
,
,
, - style="vertical-align: top;"
, Mathematica
, Fold 'func'', ''initval'', ''list''/code>
, Fold 'func'',_''initval'',_Reverse[''list''
.html" ;"title="'list''.html" ;"title="'func'', ''initval'', Reverse 'func'',_''initval'',_Reverse[''list''
">_Fold[''func'',_''list''/code>
.html" ;"title="'list''">'func'', ''initval'', Reverse _Fold[''func'',_''list''
/code>
">_Fold[''func'',_Reverse[''list''
.html" ;"title="'list''
"> Fold _Fold[''func'',_Reverse[''list''
">_NestWhileList[''func,'',_''initval'',_''predicate''/code>
.html" ;"title="'func'', ''list''/code>
"> Fold[''func'', Reverse[''list''
"> NestWhileList[''func,'', ''initval'', ''predicate''/code>
"> 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
OCaml ( , formerly Objective Caml) is a general-purpose programming language, general-purpose, multi-paradigm programming language which extends the Caml dialect of ML (programming language), ML with object-oriented programming, object-oriented ...
, 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
,
,
,
,
,
,
, - style="vertical-align: top;"
, PARI/GP
PARI/GP is a computer algebra system with the main aim of facilitating number theory computations. Versions 2.1.0 and higher are distributed under the GNU General Public License. It runs on most common operating systems.
System overview
The ...
, fold( ''f'', ''A'' )
,
,
,
,
,
, - style="vertical-align: top;"
, Perl
Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offici ...
, reduce ''block'' ''initval'', ''list''
,
, reduce ''block'' ''list''
,
,
, in List::Util
module
, - style="vertical-align: top;"
, PHP
PHP is a general-purpose scripting language geared toward web development. It was originally created by Danish-Canadian programmer Rasmus Lerdorf in 1993 and released in 1995. The PHP reference implementation is now produced by The PHP Group. ...
, 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
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
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
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
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
, 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
A ruby is a pinkish red to blood-red colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called sa ...
, ''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
Rust is an iron oxide, a usually reddish-brown oxide formed by the reaction of iron and oxygen in the catalytic presence of water or air moisture. Rust consists of hydrous iron(III) oxides (Fe2O3·nH2O) and iron(III) oxide-hydroxide (FeO(OH ...
, ''iterator''.fold(''initval'', ''func'')
, ''iterator''.rev().fold(''initval'', ''func'')
,
,
,
, ''iterator''.rev()
requires ''iterator''
to be a DoubleEndedIterator
.
, - style="vertical-align: top;"
, 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 A scheme is a systematic plan for the implementation of a certain idea.
Scheme or schemer may refer to:
Arts and entertainment
* ''The Scheme'' (TV series), a BBC Scotland documentary series
* The Scheme (band), an English pop band
* ''The Schem ...
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'' '' ail-gen')
unfold-right ''p'' ''f'' ''g'' ''seed'' ''ail
Ail or AIL may refer to:
* Illness, a state of poor health
* Ail (''Sailor Moon''), a character in the ''Sailor Moon'' anime series
* Acceptance in lieu, an arrangement in the UK for accepting works of art etc. in lieu of tax
* Agilus, a Frankis ...
'
(vector-unfold ''f'' ''length'' ''initial-seed'' ''···'')
(vector-unfold-right ''f'' ''length'' ''initial-seed'' ''···'')
, srfi/1 srfi/43
, - style="vertical-align: top;"
, Smalltalk
Smalltalk is an object-oriented, dynamically typed reflective programming language. It was designed and created in part for educational use, specifically for constructionist learning, at the Learning Research Group (LRG) of Xerox PARC by Alan Ka ...
, ''aCollection'' inject: ''aValue'' into: ''aBlock''
,
, ''aCollection'' reduce: ''aBlock''
,
,
, ANSI Smalltalk doesn't define #reduce: but many implementations do.
, - style="vertical-align: top;"
, Standard ML
Standard ML (SML) is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of the ...
, 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
Swift or SWIFT most commonly refers to:
* SWIFT, an international organization facilitating transactions between banks
** SWIFT code
* Swift (programming language)
* Swift (bird), a family of birds
It may also refer to:
Organizations
* SWIFT, ...
, ''array''.reduce(''initval'', ''func'')
reduce(''sequence'', ''initval'', ''func'')
, ''array''.reverse() .reduce(''initval'', ''func'')
,
,
,
,
, - style="vertical-align: top;"
, 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 sequence
s
, - style="vertical-align: top;"
, Xtend
Xtend is a general-purpose high-level programming language for the Java Virtual Machine. Syntactically and semantically Xtend has its roots in the Java programming language but focuses on a more concise syntax and some additional functionality ...
, ''iterable''.fold(''initval'', 'func''
,
, ''iterable''.reduce 'func''/code>
,
,
,
Universality
Fold is a 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
In mathematics and computer science in general, a '' fixed point'' of a function is a value that is mapped to itself by the function.
In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order f ...
can be implemented via fold, proving that iterations can be reduced to folds:
y f = foldr (\_ -> f) undefined (repeat undefined)
See also
* Aggregate function
In database management, an aggregate function or aggregation function is a function where the values of multiple rows are grouped together to form a single summary value.
Common aggregate functions include:
* Average (i.e., arithmetic mean)
* C ...
* Iterated binary operation
In mathematics, an iterated binary operation is an extension of a binary operation on a set ''S'' to a function on finite sequences of elements of ''S'' through repeated application. Common examples include the extension of the addition operation ...
* Catamorphism
In category theory, the concept of catamorphism (from the Ancient Greek: "downwards" and "form, shape") denotes the unique homomorphism from an initial algebra into some other algebra.
In functional programming, catamorphisms provide generalizat ...
, a generalization of fold
* Homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
* Map (higher-order function)
In many programming languages, map is the name of a higher-order function that applies a given function to each element of a collection, e.g. a list or set, returning the results in a collection of the same type. It is often called ''apply-t ...
* Prefix sum In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers is a second sequence of numbers , the sums of prefixes ( running totals) of the input sequence:
:
:
:
:...
For instance, the prefix sums ...
* Recursive data type
In computer programming languages, a recursive data type (also known as a recursively-defined, inductively-defined or inductive data type) is a data type for values that may contain other values of the same type. Data of recursive types are usuall ...
* Reduction Operator
In computer science, the reduction operator is a type of Operator (computer programming), operator that is commonly used in Parallel computing, parallel programming to reduce the elements of an array into a single result. Reduction operators are A ...
* Structural recursion Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural nu ...
References
{{Reflist
External links
"Higher order functions — map, fold and filter"
"Fold in Tcl"
"Constructing List Homomorphism from Left and Right Folds"
"The magic foldr"
Higher-order functions
Recursion
Programming language comparisons
Articles with example Haskell code
Articles with example Scheme (programming language) code
Iteration in programming