Fold (higher-order function): Difference between revisions

Revision as of 03:35, 1 March 2024

Latest revision as of 04:15, 31 August 2025

(9 intermediate revisions by 7 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 274:

| <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>

|

Line 314 ⟶ 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 333 ⟶ 342:

| [[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.reduceRight(func,initVal)</code>

| <code>''array''.reduceRight<wbr />(''func'', ''initval'')</code><ref>{{Cite web |date=2023-12-11 |title=Array.prototype.reduceRight() - JavaScript {{!}} MDN |url=https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduceRight |access-date=2024-01-16 |website=developer.mozilla.org |language=en-US}}</ref>

| <code>''array''.reduce<wbr/>(''func'')</code>

| <code>''array''.reduceRight<wbr />(''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 459 ⟶ 468:

| [[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 468 ⟶ 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>

Line 519 ⟶ 528:

| <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>

Line 560 ⟶ 569:

|- style="vertical-align: top;"

| [[XPath]]

| <{{code>|fold-left($input, $zero, $action)</code>|xquery}}<br><{{code>|array:fold-left($input, $zero, $action)</code>|xquery}}

| <{{code>|fold-right($input, $zero, $action)</code>|xquery}}<br><{{code>|array:fold-right($input, $zero, $action)</code>|xquery}}

|

|

Line 590 ⟶ 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>