Wikipedia

Fold (higher-order function): Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
→In various languages: Add Racket fold{l,r}
 
(19 intermediate revisions by 14 users not shown)
Line 1:
{{Short description|Family of higher-order functions}}
In [[functional programming]], a '''fold''' (also termed '''reduce''', '''accumulate''', '''aggregate''', '''compress''', or '''inject''') refers tois a family of [[higher-order function]]s that [[analysis|analyzeanalyzes]] a [[Recursive data type|recursive]] data structure and through use of a given combining operation, recombinerecombines 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 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 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 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 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 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;"
Line 202:
| <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;"
Line 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 251 ⟶ 242:
|- style="vertical-align: top;"
| [[Elixir (programming language)|Elixir]]
| <code>List.foldl(''list'', ''acc'', ''fun'')</code>
| <code>List.foldr(''list'', ''acc'', ''fun'')</code>
|
|
Line 278 ⟶ 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;"
▲| [[CurlGleam (programming language)|CurlGleam]]
| <code>list.fold(''list'', ''initial'', ''func'')</code><br><code>yielder.fold(''yielder'', ''initial'', ''func'')</code>
| <code>Listlist.fold_right ''func'' (''list'', ''initvalinitial''<br /> Array.fold_right, ''func'' ''array'' ''initval'')</code>▼
| <code>list.reduce(''list'', ''func'')</code><br><code>yielder.reduce(''yielder'', ''func'')</code>
|▼
| <code>''array''yielder.reduce<wbr/>unfold(''funcinitial'', ''initvalfunc'')</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 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 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 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 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 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 388:
| <code>foldl(''func'', ''initval'', ''sequence'')</code>
| <code>foldr(''func'', ''initval'', ''sequence'')</code>
| <code>foldl(''func'', ''sequence'')</code>
| <code>foldr(''func'', ''sequence'')</code>
|
|
Line 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 472 ⟶ 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 486 ⟶ 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 501 ⟶ 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 523 ⟶ 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 530 ⟶ 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 554 ⟶ 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 575 ⟶ 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 647 ⟶ 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 674 ⟶ 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)"