Wikipedia

Fold (higher-order function): Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
Ytaki (talk | contribs)
6 edits
Added unfold functions to Scheme column
 
(34 intermediate revisions by 27 users not shown)
Line 1:
{{Short description|Family of higher-order functions}}
In [[functional programming]], '''fold''' (also termed '''reduce''', '''accumulate''', '''aggregate''', '''compress''', or '''inject''') refers to a family of [[higher-order function]]s that [[analysis|analyze]] a [[Recursive data type|recursive]] data structure and through use of a given combining operation, recombine the results of [[recursion|recursively]] processing its constituent parts, building up a return value. Typically, a fold is presented with a combining [[Subroutine|function]], a top [[Node (computer science)|node]] of a [[data structure]], and possibly some default values to be used under certain conditions. The fold then proceeds to combine elements of the data structure's [[hierarchy]], using the function in a systematic way.
In [[functional programming]], a '''fold''' is a [[higher-order function]] that [[analysis|analyzes]] a [[Recursive data type|recursive]] data structure and through use of a given combining operation, recombines the results of [[recursion|recursively]] processing its constituent parts, building up a return value. Fold also termed as '''reduce''', '''accumulate''', '''aggregate''', '''compress''', or '''inject'''. Typically, a fold is presented with a combining [[Subroutine|function]], a top [[Node (computer science)|node]] of a [[data structure]], and possibly some default values to be used under certain conditions. The fold then proceeds to combine elements of the data structure's [[hierarchy]], using the function in a systematic way.
 
Folds are in a sense dual to [[Unfold (higher-order function)|unfolds]], which take a ''seed'' value and apply a function [[corecursion|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 and nonterminal symbols|terminal]] values and the recursive results ([[catamorphism]], versus [[anamorphism]] of unfolds).
Line 24 ⟶ 25:
 
==On lists==
The folding of the list <code>[1,2,3,4,5]</code> with the addition operator would result in 15, the sum of the elements of the list <code>[1,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 <code>1 + 2 + 3 + 4 + 5</code>.<ref>{{Cite web |title=Haskell unit 6: The higher-order fold functions {{!}} Antoni Diller |url=https://www.cantab.net/users/antoni.diller/haskell/units/unit06.html |access-date=2023-04-04 |website=www.cantab.net}}</ref>
 
In the example above, + is an [[associative 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 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 (programming language)|Haskell]]'s or [[Prolog]]'s terminology. With a right fold, the sum would be parenthesized as <code>1 + (2 + (3 + (4 + 5)))</code>, whereas with a left fold it would be parenthesized as <code>(((1 + 2) + 3) + 4) + 5</code>.
Line 33 ⟶ 34:
The use of an initial value is necessary when the combining function ''f''&thinsp; is asymmetrical in its types (e.g. <code>a → b → b</code>), 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''&thinsp;'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''&thinsp; could be seen as a binary operation that ''associates on the right'', and vice versa.
 
When the function is a [[Magma (algebra)|magma]], i.e. symmetrical in its types (<code>a → a → a</code>), 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'']] of nested sub-expressions, e.g., <code>((1 + 2) + (3 + 4)) + 5</code>. If the binary operation ''f''&thinsp; 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''&thinsp; is [[non-strict semantics|non-strict]].
 
Whereas linear folds are [[Recursion (computer science)#Recursive data structures (structural recursion)|node-oriented]] and operate in a consistent manner for each [[Node (computer science)|node]] of a [[List (computing)|list]], tree-like folds are whole-list oriented and operate in a consistent manner across ''groups'' of nodes.
Line 40 ⟶ 41:
One often wants to choose the [[identity element]] 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 <code>foldr</code> and <code>foldl</code> which use the last and first element of the list respectively as the initial value. In Haskell and several other languages, these are called <code>foldr1</code> and <code>foldl1</code>, 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 (computer scientist)|Richard Bird]] in his 2010 book proposes<ref name="foldrn">Richard Bird, "Pearls of Functional Algorithm Design", Cambridge University Press 2010, {{ISBN|978-0-521-51338-8}}, p. 42</ref> "a general fold function on non-empty lists" <code>foldrn</code> 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 <code>foldr</code> to produce a result of type different from the list's elements type.
 
===Implementation===
Line 130 ⟶ 131:
where the function [[Haskell features#union|<code>union</code>]] operates on ordered lists in a local manner to efficiently produce their [[Union (set theory)|set union]], and [[Haskell features#minus|<code>minus</code>]] their [[Complement (set theory)#Relative complement|set 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
<syntaxhighlight lang="haskell">
primesTo n = foldl1 minus [[2*x,3*x..n] | x <- [1..n]]
</syntaxhighlight>
For finite lists, e.g., [[merge sort]] (and its duplicates-removing variety, <code>nubsort</code>) could be easily defined using tree-like folding as
<syntaxhighlight lang="haskell">
Line 156 ⟶ 161:
|- style="vertical-align: top;"
| [[APL (programming language)|APL]]
| <code>''func''<syntaxhighlight lang="apl" inline>⍨/⌽</syntaxhighlight>''initval'',''vector''</code>
| <code>''func''/''vector'',''initval''</code>
| <code>''func''<syntaxhighlight lang="apl" inline>⍨/⌽</syntaxhighlight>''vector''</code>
| <code>''func''/''vector''</code>
|
Line 170 ⟶ 175:
| <code>''ienum''.Reverse()<wbr/>.Aggregate(''func'')</code>
|
| <code>Aggregate</code> is an [[extension method]]<br /> <code>''ienum''</code> is an <code>IEnumerable<T></code><br /> Similarly in all .NET languages
 
|- style="vertical-align: top;"
Line 179 ⟶ 184:
|
|
| in header <code><numeric></code><br /><code>''begin''</code>, <code>''end''</code>, <code>''rbegin''</code>, <code>''rend''</code> are iterators<br /><code>''func''</code> can be a [[function pointer]] or a [[function object]]
 
|- style="vertical-align: top;"
Line 188 ⟶ 193:
| <code>(''pack'' ''op'' ...)</code>
|
| Fold expression (only for [[variadic function templatestemplate]]s): <code>''op''</code> is a binary operator (both <code>''op''</code>s must be the same, e.g., {{code|2=cpp|(std::cout << ... << args)}}), <code>''pack''</code> is an unexpanded parameter pack.
 
|- style="vertical-align: top;"
| [[C++23]]
| <code>std::ranges::fold_left(''range'', ''initval'', ''func'')</code>
| <code>std::ranges::fold_right(''range'', ''initval'', ''func'')</code>
| <code>std::ranges::fold_left_first(''range'', ''func'')</code>
| <code>std::ranges::fold_right_last(''range'', ''func'')</code>
|
| Both <code>std::ranges::fold_left_first</code> and <code>std::ranges::fold_right_last</code> return <code>std::optional</code> considering the emptiness of <code>''range''</code>.
 
|- style="vertical-align: top;"
| [[CFML]]
| <code>''obj''.reduce(''func'', ''initial'')</code>
|
| <code>''obj''.reduce(''func'')</code>
|
|
| Where <code>''func''</code> receives as arguments the result of the previous operation (or the <code>''initial''</code> value on the first iteration); the current item; the current item's index or key; and a reference to the <code>''obj''</code>
 
|- style="vertical-align: top;"
| [[Clojure]]
| <code>(reduce ''func'' ''initval'' ''list'')</code>
| <code>(reduce ''func'' ''initval'' (reverse ''list''))</code>
| <code>(reduce ''func'' ''list'')</code>
| <code>(reduce ''func"'' (reverse ''list''))</code>
|
| See also [https://clojure.github.comio/clojure/branch-master/clojure.core-api.html#clojure.core.reducers/fold clojure.core.reducers/fold]
 
|- style="vertical-align: top;"
Line 216 ⟶ 230:
|
|
 
|- style="vertical-align: top;"
| [[Curl (programming language)|Curl]]
| <code>{{TreeNode.''default'' ''treeNode'' ...} ''.to-Iterator''}</code>
| <code>{{TreeNode.''default'' ''treeNode'' ...} ''.reverse}<wbr/>.{{nobr|to-Iterator}}''}</code>
| <code>{for {treeNode''<wbr/>.{{nobr|to-Iterator}}}'' ''do}''</code>
| <code>{for {{treeNode.reverse}''<wbr/>.{{nobr|to-Iterator}}}'' ''do}''</code>
|
| also DefaultListModel and HashTable implement <code>to-Iterator</code>
 
|- style="vertical-align: top;"
Line 237 ⟶ 242:
|- style="vertical-align: top;"
| [[Elixir (programming language)|Elixir]]
| <code>List.foldl(''list'', ''acc'', ''fun'')</code>
| <code>List.foldr(''list'', ''acc'', ''fun'')</code>
|
|
Line 264 ⟶ 269:
|- style="vertical-align: top;"
| [[F Sharp (programming language)|F#]]
| <code>Seq/List.fold ''func'' ''initval'' ''list''</code><br><code>Seq.fold ''func'' ''initval'' ''sequence''</code>
| <code>List.foldBack ''func'' ''list'' ''initval''</code>
| <code>Seq/List.reduce ''func'' ''list''</code><br><code>Seq.reduce ''func'' ''sequence''</code>
| <code>List.reduceBack ''func'' ''list''</code>
| <code>Seq.unfold ''func'' ''initval''</code>
|
 
|- style="vertical-align: top;"
| [[Gleam (programming language)|Gleam]]
| <code>list.fold(''list'', ''initial'', ''func'')</code><br><code>yielder.fold(''yielder'', ''initial'', ''func'')</code>
| <code>list.fold_right(''list'', ''initial'', ''func'')</code>
| <code>list.reduce(''list'', ''func'')</code><br><code>yielder.reduce(''yielder'', ''func'')</code>
|
| <code>yielder.unfold(''initial'', ''func'')</code>
|
 
|- style="vertical-align: top;"
| [[Gosu (programming language)|Gosu]]
| <code>''Iterable''.fold(''f''(agg, e))<wbr/code><br><code>''Iterable''.reduce(init, ''f''(agg, e)) <wbr/code><br><code>''Iterable''.partition(''f''(e))</code>
|
|
|
|
| All are [[extension methods]] on Java's <code>Iterable</code> interface, arrays are also supported
 
|- style="vertical-align: top;"
Line 296 ⟶ 310:
| <code>foldr1 ''func'' ''list''</code>
| <code>unfoldr ''func'' ''initval''</code>
| For <code>foldl</code>, the folding function takes arguments in the opposite order as that for <code>foldr</code>.
 
|- style="vertical-align: top;"
Line 309 ⟶ 323:
|- style="vertical-align: top;"
| [[J (programming language)|J]]
| <code>''verb''<nowikisyntaxhighlight lang="j" inline>~/|.</nowikisyntaxhighlight> ''initval'',''array''</code>
| <code>''verb''/ ''array'',''initval''</code>
| <code>''verb''<nowikisyntaxhighlight lang="j" inline>~/|.</nowikisyntaxhighlight> ''array''</code>
| <code>''verb''/ ''array''</code>
|
Line 327 ⟶ 341:
|- style="vertical-align: top;"
| [[JavaScript]] 1.8<br>[[ECMAScript]] 5
| <code>''array''.reduce<wbr/>(''func'', ''initval'')</code><ref>{{Cite web |date=2023-12-11 |title=Array.prototype.reduce() - JavaScript {{!}} MDN |url=https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce |access-date=2024-01-16 |website=developer.mozilla.org |language=en-US}}</ref>
| <code>''array''.reduce<wbr/>(''func'', ''initval'')</code>
| <code>array.reduceRight(func,initVal)</code>
|
| <code>''array''.reduce<wbr/>(''func'')</code>
| <code>array.reduceRight(func)</code>
|
| The reducer main arguments are accumulator and current value, and we can use optional arguments like index and array. {{code|2=javascript|1=array.reduceRight((acc, value, idx, array)=>{}, initvalue)}}
|
|
 
|- style="vertical-align: top;"
Line 347 ⟶ 361:
| <code>''Iterable''.fold<wbr />(''initval'', ''func'')</code>
| <code>''Iterable''.foldRight<wbr />(''initval'', ''func'')</code>
| <code>''Iterable''.reduce(''(func'')</code>
| ''<code>''Iterable</code>''<code>.reduceRight(''(func'')</code>
|
| Other collections also support <code>fold</code><ref>{{cite web |title=fold - Kotlin Programming Language |url=https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/fold.html |website=Kotlin |publisher=Jetbrains |access-date=29 March 2019 |ref=fold.kt}}</ref> and <code>reduce</code>.<ref>{{cite web |title=reduce - Kotlin Programming Language |url=https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/reduce.html |website=Kotlin |publisher=Jetbrains |access-date=29 March 2019 |ref=reduce.kt}}</ref> There is also <code>Result.fold(onSuccess, onFailure)</code>,<ref>{{cite web |title=Result - Kotlin Programming Language |url=https://kotlinlang.org/api/latest/jvm/stdlib/kotlin/-result/index.html |website=Kotlin |publisher=Jetbrains |access-date=29 March 2019 |ref=Result.kt}}</ref> which reduces a <code>Result<T></code> (either success or failure) to the return type of <code>onSuccess</code> and <code>onFailure</code>.
Line 368 ⟶ 382:
|
|
| Meta-predicates provided by the ''<code>meta''</code> standard library object. The abbreviations ''<code>foldl''</code> and ''<code>foldr''</code> may also be used.
 
|- style="vertical-align: top;"
Line 374 ⟶ 388:
| <code>foldl(''func'', ''initval'', ''sequence'')</code>
| <code>foldr(''func'', ''initval'', ''sequence'')</code>
| <code>foldl(''func'', ''sequence'')</code>
|
| <code>foldr(''func'', ''sequence'')</code>
|
|
|
Line 407 ⟶ 421:
 
|- style="vertical-align: top;"
| [[MythrylOCaml]]
| <code>List.fold_left ''func'' ''initval'' ''list''<br /code> vector::<br><code>Array.fold_left ''func'' ''initval'' ''vectorarray''</code>
| <code>List.fold_right ''func'' ''initvallist'' ''listinitval''<br /code> vector::<br><code>Array.fold_right ''func'' ''initvalarray'' ''vectorinitval''</code>
|
|
|
| The supplied function takes its arguments in a tuple.
 
|- style="vertical-align: top;"
| [[OCaml]]
| <code>List.fold_left ''func'' ''initval'' ''list''<br /> Array.fold_left ''func'' ''initval'' ''array''</code>
| <code>List.fold_right ''func'' ''list'' ''initval''<br /> Array.fold_right ''func'' ''array'' ''initval''</code>
|
|
| <code>Base.Sequence.unfold ''~init'' ''~f''</code> <ref>{{cite web|url=https://opensource.janestreet.com/base/|title = Base|publisher = Jane Street Capital|access-date = February 26, 2019}}</ref>
|
 
Line 458 ⟶ 463:
| <code>array_reduce(<wbr/>array_reverse(''array''), ''func'')</code>
|
| When <code>''initval''</code> is not supplied, NULL is used, so this is not a true foldl1. Before PHP 5.3, <code>''initval''</code> can only be integer. "<code>''func"''</code> is a [http://php.net/manual/en/language.pseudo-types.php#language.types.callback callback] {{Webarchive|url=https://web.archive.org/web/20201128173922/https://www.php.net/manual/en/language.pseudo-types.php#language.types.callback |date=2020-11-28 }}. Try [http://micmap.org/php-by-example/en/function/array_reduce array_reduce] online.
 
|- style="vertical-align: top;"
| [[Python (programming language)|Python]] 2.x
| <code>reduce(''func'', ''list'', ''initval'')</code>
| <code>{{codett|2=python2|reduce(lambda x, y:}} ''func''(y, x), reversed(''list''), ''initval'')</code>
| <code>reduce(''func'', ''list'')</code>
| <code>{{codett|2=python2|reduce(lambda x, y:}} ''func''(y, x), reversed(''list''))</code>
|
|
Line 472 ⟶ 477:
| [[Python (programming language)|Python]] 3.x
| <code>functools.reduce(''func'', ''list'', ''initval'')</code>
| <code>{{codett|2=python|functools.reduce(lambda x, y:}} ''func''(y, x), reversed(''list''), ''initval'')</code>
| <code>functools.reduce(''func'', ''list'')</code>
| <code>{{codett|2=python|functools.reduce(lambda x, y:}} ''func''(y, x), reversed(''list''))</code>
|
| In module ''[https://docs.python.org/3/library/functools.html functools]''.<ref>
For reference <code>''functools.reduce''</code>: <code>import functools</code><BR /br>
For reference <code>''reduce''</code>: <code>from functools import reduce</code></ref>
 
|- style="vertical-align: top;"
Line 487 ⟶ 492:
| <code>Reduce(''func'', ''list'', right=TRUE)</code>
|
| R supports right folding and left or right folding with or without an initial value through the ''<code>right''</code> and ''<code>init''</code> arguments to the <code>Reduce</code> function.
 
|-
| [[Racket (programming language)|Racket]]
| <code>(foldl ''func'' initval ''list'')</code>
| <code>(foldr ''func'' initval ''list'')</code>
|
|
|
|
 
|- style="vertical-align: top;"
| [[Ruby (programming language)|Ruby]]
| <code>''enum''<wbr/>.inject(''initval'', ''&block'')<br /code><br><code> ''enum''<wbr/>.reduce(''initval'', ''&block'')</code>
| <code>''enum''.reverse_each<wbr/>.inject(''initval'', ''&block'')<br /code><br><code> ''enum''.reverse_each<wbr/>.reduce(''initval'', ''&block'')</code>
| <code>''enum''<wbr/>.inject(''&block'')<br /code><br><code> ''enum''.reduce(''&block'')</code>
| <code>''enum''.reverse_each<wbr/>.inject(''&block'')<br /code><br><code> ''enum''.reverse_each<wbr/>.reduce(''&block'')</code>
|
| In Ruby 1.8.7+, can also pass a symbol representing a function instead of a block. <br /> <code>''enum''</code> is an Enumeration <br /> Please notice that these implementations of right folds are wrong for non-commutative <code>''&block''</code> (also initial value is put on wrong side).
 
|- style="vertical-align: top;"
Line 502 ⟶ 516:
| <code>''iterator''.fold(''initval'', ''func'')</code>
| <code>''iterator''.rev().fold(''initval'', ''func'')</code>
| <code>''iterator''.reduce(''func'')</code>
|
| <code>''iterator''.rev().reduce(''func'')</code>
|
|
| <code>''iterator''.rev()</code> requires <code>''iterator''</code> to be a <code>DoubleEndedIterator</code>.<ref>{{cite web |title=Iterator in core::iter |url=https://doc.rust-lang.org/nightly/core/iter/trait.Iterator.html#method.rev |website=Rust |publisher=Rust Team |access-date=2021-06-22}}</ref>
Line 509 ⟶ 523:
|- style="vertical-align: top;"
| [[Scala (programming language)|Scala]]
| <code>''list''.foldLeft(''initval'')(''func'')</code><br /><code>(''initval'' /: ''list'')(''func'')</code>
| <code>''list''.foldRight(''initval'')(''func'')</code><br /><code>(''list'' :\ ''initval'')(''func'')</code>
| <code>''list''.reduceLeft(''func'')</code>
| <code>''list''.reduceRight(''func'')</code>
|
| Scala's symbolic fold syntax was intended to resemble the left- or right-leaning tree commonly used to explain the fold operation,<ref>{{cite newsgroup |title= Re: Blog: My verdict on the Scala language |author= Odersky, Martin |date= 2008-01-05 |newsgroup= comp.scala.lang |url= http://permalink.gmane.org/gmane.comp.lang.scala/9557 |access-date= 14 October 2013 |archive-url= https://web.archive.org/web/20150514122827/http://permalink.gmane.org/gmane.comp.lang.scala/9557 |archive-date= 14 May 2015}}</ref> but has since been reinterpreted as an illustration of a toppling domino.<ref>{{cite web|last1=Sterling|first1=Nicholas|title=An intuitive feel for Scala’sScala's /: operator (foldLeft)|date=28 July 2010 |url=https://nicholassterling.wordpress.com/2010/07/28/an-intuition-about-scalas-operator-foldleft/|access-date=24 June 2016}}</ref> 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 <code>list.fold(z)(op)</code>.<ref>{{Cite web|url=https://www.scala-lang.org/api/current/scala/collection/Seq.html#fold%5BA1%3E:A%5D(z:A1)(op:(A1,A1)=%3EA1):A1|title=Fold API - Scala Standard Library|website=www.scala-lang.org|access-date=2018-04-10}}</ref>
 
|- style="vertical-align: top;"
| [[Scheme (programming language)|Scheme]] R<sup>6</sup>RS
| <code>(fold-left ''func'' ''initval'' ''list'')<br /code><br><code> (vector-fold ''func'' ''initval'' ''vector'')</code>
| <code>(fold-right ''func'' ''initval'' ''list'')<br /code><br><code> (vector-fold-right ''func'' ''initval'' ''vector'')</code>
| <code>(reduce-left ''func'' ''defaultval'' ''list'')</code>
| <code>(reduce-right ''func'' ''defaultval'' ''list'')</code>
| <code>(unfold ''p'' ''f'' ''g'' ''seed'' ''[tail-gen]'')</code><br /><code>unfold-right ''p'' ''f'' ''g'' ''seed'' ''[tail]''</code><br /><code>(vector-unfold ''f'' ''length'' ''initial-seed'' ''···'')</code><br /><code>(vector-unfold-right ''f'' ''length'' ''initial-seed'' ''···'')</code>
|
| srfi/1 srfi/43
 
Line 534 ⟶ 547:
|
|
| ANSI Smalltalk doesn't define <code>#reduce:</code> but many implementations do.
 
|- style="vertical-align: top;"
| [[Standard ML]]
| <code>foldl ''func'' ''initval'' ''list''<br /code><br><code> Array.foldl ''func'' ''initval'' ''array''</code>
| <code>foldr ''func'' ''initval'' ''list''<br /code><br><code> Array.foldr ''func'' ''initval'' ''array''</code>
|
|
|
| The supplied function takes its arguments in a tuple. For <code>foldl</code>, the folding function takes arguments in the same order as for <code>foldr</code>.
 
|- style="vertical-align: top;"
| [[Swift (programming language)|Swift]]
| <code>''array''.reduce(''initval'', ''func'')<br /code><br><code> reduce(''sequence'', ''initval'', ''func'')</code>
| <code>''array''.reverse()<wbr/>.reduce(''initval'', ''func'')</code>
|
Line 555 ⟶ 568:
 
|- style="vertical-align: top;"
| [[XPath 3|XPath 3.1]]
| {{code|fold-left($input, $zero, $action)|xquery}}<br>{{code|array:fold-left($input, $zero, $action)|xquery}}
| {{sxhl|2=xquery|
| {{code|fold-right($input, $zero, $action)|xquery}}<br>{{code|array:fold-right($input, $zero, $action)|xquery}}
array:fold-left(
$array as array(*),
$zero as item()*,
$f as function(
item()*, item()*
} as item()*
) as item()*
}}<ref>[https://www.w3.org/TR/xpath-functions-31/#func-array-fold-left ''array'':fold-left]</ref>
 
{{sxhl|2=xquery|
fn:fold-left(
$seq as item()*,
$zero as item()*,
$f as function(
item()*, item()
) as item()*
) as item()*
}}<ref>[https://www.w3.org/TR/xpath-functions-31/#func-fold-left fold-left]</ref>
 
| {{sxhl|2=xquery|
array:fold-right(
$array as array(*),
$zero as item()*,
$f as function(
item()*, item()*
} as item()*
) as item()*
}}<ref>[https://www.w3.org/TR/xpath-functions-31/#func-array-fold-right ''array'':fold-right]</ref>
 
{{sxhl|2=xquery|
fn:fold-right(
$seq as item()*,
$zero as item()*,
$f as function(
item(), item()*
) as item()*
) as item()*
}}<ref>[https://www.w3.org/TR/xpath-functions-31/#func-fold-right fold-right]</ref>
 
|
|
|
| Two functions exist for each case because XPath offers ''sequences'' for unstructured and ''arrays'' for structured data.
| In XPath 3.1 due to historical reasons the <code>array</code> and <code>sequence</code> types are incompatible -- thus the need for separate <code>fold</code> functions for <code>array</code> and for <code>sequence</code>
 
 
The difference in the signatures is due to the fact that the value of an <code>array</code> item can be a <code>sequence</code>, while XPath doesn't have <code>sequence</code> of <code>sequence</code>s
 
|- style="vertical-align: top;"
Line 627 ⟶ 599:
|title= A tutorial on the universality and expressiveness of fold
|journal= Journal of Functional Programming
|issuedate= 9 (4)1999
|volume= 9
|issue= 4
|pages= 355–372
|doi= 10.1017/S0956796899003500
|url= http://www.cs.nott.ac.uk/~gmh/fold.pdf
|access-date= March 26, 2009}}</ref>
Line 635 ⟶ 610:
</syntaxhighlight>
 
Also, in a [[lazy language]] with infinite lists, a [[fixed point combinator]] can be implemented via fold,<ref>{{cite journal
|last= Pope
|first= Bernie
Line 654 ⟶ 629:
* [[Prefix sum]]
* [[Recursive data type]]
* [[Reduction Operatoroperator]]
* [[Recursion (computer science)#Recursive data structures (structural recursion)|Structural recursion]]
 
Line 666 ⟶ 641:
* [http://www.iis.sinica.edu.tw/~scm/2008/constructing-list-homomorphism/ "Constructing List Homomorphism from Left and Right Folds"]
* [http://ulissesaraujo.wordpress.com//2007/11/20/foldr-the-magic-function/ "The magic foldr"]
 
{{Data structures and algorithms}}
[[Category:Higher-order functions]]
[[Category:Recursion]]
Retrieved from "https://en.wikipedia.org/wiki/Fold_(higher-order_function)"