Wikipedia

Fold (higher-order function): Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
 
(25 intermediate revisions by 20 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 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 160 ⟶ 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 174 ⟶ 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 183 ⟶ 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 192 ⟶ 193:
| <code>(''pack'' ''op'' ...)</code>
|
| Fold expression (only for [[variadic template]]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.io/clojure/clojure.core-api.html#clojure.core.reducers/fold clojure.core.reducers/fold]
Line 220 ⟶ 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 241 ⟶ 242:
|- style="vertical-align: top;"
| [[Elixir (programming language)|Elixir]]
| <code>List.foldl(''list'', ''acc'', ''fun'')</code>
| <code>List.foldr(''list'', ''acc'', ''fun'')</code>
|
|
Line 268 ⟶ 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 300 ⟶ 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 313 ⟶ 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 331 ⟶ 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 351 ⟶ 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 372 ⟶ 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 378 ⟶ 388:
| <code>foldl(''func'', ''initval'', ''sequence'')</code>
| <code>foldr(''func'', ''initval'', ''sequence'')</code>
| <code>foldl(''func'', ''sequence'')</code>
|
| <code>foldr(''func'', ''sequence'')</code>
|
|
|
Line 411 ⟶ 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 462 ⟶ 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 476 ⟶ 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 491 ⟶ 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 506 ⟶ 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 513 ⟶ 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 537 ⟶ 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 558 ⟶ 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 630 ⟶ 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 657 ⟶ 629:
* [[Prefix sum]]
* [[Recursive data type]]
* [[Reduction Operatoroperator]]
* [[Recursion (computer science)#Recursive data structures (structural recursion)|Structural recursion]]
 
Retrieved from "https://en.wikipedia.org/wiki/Fold_(higher-order_function)"