Fold

Reduce a collection to one value, combining left to right from a seed.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageFold!↗

Fold(f, init, xs)$f(\ldots f(f(init, x_1), x_2)\ldots, x_n)$ — $init$ combined with each element of $xs$ in turn.

Fold(f)the operator form, $\mathrm{Fold}(f)(xs) = \mathrm{Fold}(f, xs)$.

Fold(f, xs)the same fold with no seed, starting from $xs$'s own first element: $f(\ldots f(x_1, x_2)\ldots, x_n)$.

Typed signatures

Type	Package	Applies
(any) -> any	combinatoricsreplaces compute-engine	always
(reducer: (unknown, T) any -> unknown, initial: value, collection<T>) -> value where T	compute-engine	always

Domain: Collections

Examples

Basic #

live ↗

In$\mathrm{Fold}(\mathrm{Add}, 0, \bigl\lbrack1, 2, 3, 4\bigr\rbrack)$Out$10$

live ↗

In$\mathrm{Fold}(\mathrm{Multiply}, 1, \bigl\lbrack1, 2, 3, 4\bigr\rbrack)$Out$24$

The shape of a left fold

live ↗

In$\mathrm{Fold}(f, x, \bigl\lbrack a, b, c\bigr\rbrack)$Out$f(f(f(x, a), b), c)$

live ↗

In$\mathrm{Fold}(\mathrm{Max}, 0, \bigl\lbrack3, 1, 4, 1, 5\bigr\rbrack)$Out$5$

Shows the left-nested shape that a fold builds

live ↗

In$\operatorname{Reduce}\left(\bigl\lbrack a, b, c, d\bigr\rbrack, \mathrm{List}, x\right)$Out$\bigl\lbrack\bigl\lbrack\bigl\lbrack\bigl\lbrack x, a\bigr\rbrack, b\bigr\rbrack, c\bigr\rbrack, d\bigr\rbrack$

A fold with an unknown $f$ makes the nesting visible

live ↗

In$\operatorname{Reduce}\left(\bigl\lbrack a, b, c, d\bigr\rbrack, f, x\right)$Out$f(f(f(f(x, a), b), c), d)$

Folding Multiply with seed 1 is the product

live ↗

In$\operatorname{Reduce}\left(\bigl\lbrack a, b, c, d\bigr\rbrack, \mathrm{Multiply}, 1\right)$Out$abcd$

Seeding with the first element folds over the rest

live ↗

In$\operatorname{Reduce}\left(\mathrm{Rest}(\bigl\lbrack a, b, c, d\bigr\rbrack), f, \mathrm{First}(\bigl\lbrack a, b, c, d\bigr\rbrack)\right)$Out$f(f(f(a, b), c), d)$

Scope #

Symbolic elements

live ↗

In$\mathrm{Fold}(\mathrm{Add}, 0, \bigl\lbrack a, b, c\bigr\rbrack)$Out$a+b+c$

Any two-argument function, here one that nests pairs

live ↗

In$\mathrm{Fold}((\operatorname{\_1}, \operatorname{\_2})↦\bigl\lbrack\operatorname{\_1}, \operatorname{\_2}\bigr\rbrack, x, \bigl\lbrack a, b\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack x, a\bigr\rbrack, b\bigr\rbrack$

Without a seed, folding starts from the first element

live ↗

In$\mathrm{Fold}(f, \bigl\lbrack a, b, c\bigr\rbrack)$Out$f(f(a, b), c)$

A two-argument function scales each side differently as it nests

live ↗

In$\operatorname{Reduce}\left(\bigl\lbrack a, b, c, d\bigr\rbrack, (\operatorname{\_1}, \operatorname{\_2})↦\bigl\lbrack2\operatorname{\_1}, 3\operatorname{\_2}\bigr\rbrack, x\right)$Out$\bigl\lbrack\bigl\lbrack\bigl\lbrack\bigl\lbrack16x, 24a\bigr\rbrack, 12b\bigr\rbrack, 6c\bigr\rbrack, 3d\bigr\rbrack$

Composes a list of permutations onto a starting arrangement

live ↗

In$\operatorname{Reduce}\left(\bigl\lbrack\bigl\lbrack1, 4, 3, 2\bigr\rbrack, \bigl\lbrack3, 2, 4, 1\bigr\rbrack\bigr\rbrack, \mathrm{Permute}, \bigl\lbrack a, b, c, d\bigr\rbrack\right)$Out$\bigl\lbrack b, d, a, c\bigr\rbrack$

Power folds left, giving $((a^b)^c)^d$

live ↗

In$\operatorname{Reduce}\left(\mathrm{Rest}(\bigl\lbrack a, b, c, d\bigr\rbrack), \mathrm{Power}, \mathrm{First}(\bigl\lbrack a, b, c, d\bigr\rbrack)\right)$Out$((a^{b})^{c})^{d}$

live ↗

In$\mathrm{Fold}(f)\lhd\bigl\lbrack a, b, c, d\bigr\rbrack$Out$f(f(f(a, b), c), d)$

live ↗

In$\operatorname{Reduce}\left(\mathrm{Rest}(\bigl\lbrack\bigl\lbrack1, -1, 1\bigr\rbrack, \bigl\lbrack0, 1, 1\bigr\rbrack, \bigl\lbrack1, 1, -1\bigr\rbrack\bigr\rbrack), \mathrm{Cross}, \mathrm{First}(\bigl\lbrack\bigl\lbrack1, -1, 1\bigr\rbrack, \bigl\lbrack0, 1, 1\bigr\rbrack, \bigl\lbrack1, 1, -1\bigr\rbrack\bigr\rbrack)\right)$Out$\bigl\lbrack0, -1, -1\bigr\rbrack$

live ↗

In$\mathrm{Catch}(\mathrm{Fold}((\operatorname{\_1}, \operatorname{\_2})↦\text{if }\operatorname{\_1}\gt10^6\text{ then }\mathrm{Throw}(\operatorname{\_1})\text{ else }\operatorname{\_1}^2+\operatorname{\_2}, 2, 1..6))$Out$287\,111\,645\,589$

Applications #

Assemble a number from its decimal digits

live ↗

In$\mathrm{Fold}((\operatorname{\_1}, \operatorname{\_2})↦10\operatorname{\_1}+\operatorname{\_2}, 0, \bigl\lbrack1, 2, 3, 4\bigr\rbrack)$Out$1\,234$

...or from its binary digits: $1011_2 = 11$

live ↗

In$\mathrm{Fold}((\operatorname{\_1}, \operatorname{\_2})↦2\operatorname{\_1}+\operatorname{\_2}, 0, \bigl\lbrack1, 0, 1, 1\bigr\rbrack)$Out$11$

Horner's rule for $ax^2 + bx + c$

live ↗

In$\mathrm{Fold}((\operatorname{\_1}, \operatorname{\_2})↦x\operatorname{\_1}+\operatorname{\_2}, 0, \bigl\lbrack a, b, c\bigr\rbrack)$Out$x×(ax+b)+c$

Evaluate the continued fraction $[1; 2, 2, 2]$ from the inside out -- a convergent of $\sqrt{2}$

live ↗

In$\mathrm{Fold}((\operatorname{\_1}, \operatorname{\_2})↦\operatorname{\_2}+\frac{1}{\operatorname{\_1}}, 2, \bigl\lbrack2, 2, 1\bigr\rbrack)$Out$\frac{17}{12}$

A continued fraction built from the reversed list

live ↗

In$\operatorname{Reduce}\left(\mathrm{Reverse}(\bigl\lbrack a, b, c, d\bigr\rbrack), (\operatorname{\_1}, \operatorname{\_2})↦\frac{1}{\operatorname{\_1}+\operatorname{\_2}}, x\right)$Out$\frac{1}{a+\frac{1}{b+\frac{1}{c+\frac{1}{d+x}}}}$

Digits to number: $10x+d$ at each step

live ↗

In$\operatorname{Reduce}\left(\bigl\lbrack4, 5, 1, 6, 7, 8\bigr\rbrack, (\operatorname{\_1}, \operatorname{\_2})↦10\operatorname{\_1}+\operatorname{\_2}, 0\right)$Out$451\,678$

Swapping arguments nests to the right instead

live ↗

In$\operatorname{Reduce}\left(\bigl\lbrack a, b, c, d\bigr\rbrack, (\operatorname{\_1}, \operatorname{\_2})↦\bigl\lbrack\operatorname{\_2}, \operatorname{\_1}\bigr\rbrack, x\right)$Out$\bigl\lbrack d, \bigl\lbrack c, \bigl\lbrack b, \bigl\lbrack a, x\bigr\rbrack\bigr\rbrack\bigr\rbrack\bigr\rbrack$

Repeated partition builds a nested block structure

live ↗

In$\operatorname{Reduce}\left(\bigl\lbrack2, 4, 3\bigr\rbrack, \mathrm{Partition}, 1..30\right)$Out$\bigl\lbrack\bigl\lbrack\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack3, 4\bigr\rbrack, \bigl\lbrack5, 6\bigr\rbrack, \bigl\lbrack7, 8\bigr\rbrack\bigr\rbrack, \bigl\lbrack\bigl\lbrack9, 10\bigr\rbrack, \bigl\lbrack11, 12\bigr\rbrack, \bigl\lbrack13, 14\bigr\rbrack, \bigl\lbrack15, 16\bigr\rbrack\bigr\rbrack, \bigl\lbrack\bigl\lbrack17, 18\bigr\rbrack, \bigl\lbrack19, 20\bigr\rbrack, \bigl\lbrack21, 22\bigr\rbrack, \bigl\lbrack23, 24\bigr\rbrack\bigr\rbrack\bigr\rbrack\bigr\rbrack$

Horner's rule for a polynomial in $x$

live ↗

In$\operatorname{Reduce}\left(\bigl\lbrack a, b, c, d, k\bigr\rbrack, (\operatorname{\_1}, \operatorname{\_2})↦\operatorname{\_1}x+\operatorname{\_2}, 0\right)$Out$x×(x×(x×(ax+b)+c)+d)+k$

An alternating sum from a fold with negation

live ↗

In$\operatorname{Reduce}\left(\mathrm{Reverse}(\bigl\lbrack a, b, c, d, k\bigr\rbrack), (\operatorname{\_1}, \operatorname{\_2})↦\operatorname{\_2}-\operatorname{\_1}, 0\right)$Out$a-b+c-d+k$

Properties #

Folding an empty list returns the seed

live ↗

In$\mathrm{Fold}(f, x, \bigl\lbrack\bigr\rbrack)$Out$x$

Folding with Add is a sum: $1 + 2 + \cdots + 100$

live ↗

In$\mathrm{Fold}(\mathrm{Add}, 0, 1..100)$Out$5\,050$

Folding the reversed list reverses the nesting

live ↗

In$\operatorname{Reduce}\left(\mathrm{Reverse}(\bigl\lbrack a, b, c, d\bigr\rbrack), g, x\right)$Out$g(g(g(g(x, d), c), b), a)$

Appending each element to an empty list rebuilds the list

live ↗

In$\operatorname{Reduce}\left(\bigl\lbrack1, 2, 3, 4, 5\bigr\rbrack, \mathrm{Append}, \bigl\lbrack\bigr\rbrack\right)$Out$\bigl\lbrack1, 2, 3, 4, 5\bigr\rbrack$

A single element folds to itself, with no call to $f$

live ↗

In$\operatorname{Reduce}\left(\mathrm{Rest}(\bigl\lbrack a\bigr\rbrack), f, \mathrm{First}(\bigl\lbrack a\bigr\rbrack)\right)$Out$a$

The general left fold: $g(g(g(g(x,a),b),c),d)$

live ↗

In$\operatorname{Reduce}\left(\bigl\lbrack a, b, c, d\bigr\rbrack, g, x\right)$Out$g(g(g(g(x, a), b), c), d)$

Possible issues #

live ↗

In$\operatorname{Reduce}\left(\mathrm{Rest}(\bigl\lbrack\bigr\rbrack), f, \mathrm{First}(\bigl\lbrack\bigr\rbrack)\right)$Out$\mathrm{Missing}$

Neat examples #

live ↗

In$\operatorname{Reduce}\left(\bigl\lbrack a, b, c\bigr\rbrack, (s, k)↦\mathrm{Join}(s, \mathrm{Map}(\operatorname{\_1}↦\mathrm{Append}(\operatorname{\_1}, k), s)), \bigl\lbrack\bigl\lbrack\bigr\rbrack\bigr\rbrack\right)$Out$\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack a\bigr\rbrack, \bigl\lbrack b\bigr\rbrack, \bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack c\bigr\rbrack, \bigl\lbrack a, c\bigr\rbrack, \bigl\lbrack b, c\bigr\rbrack, \bigl\lbrack a, b, c\bigr\rbrack\bigr\rbrack$

live ↗

In$\mathrm{Array}(\operatorname{\_1}↦\operatorname{Reduce}\left(1..2..\operatorname{\_1}, (\operatorname{\_1}, \operatorname{\_2})↦\operatorname{Reduce}\left(1..2..\operatorname{\_1}, (\operatorname{\_1}, \operatorname{\_2})↦-\operatorname{\_1}+(\operatorname{\_2}+2)×2^{\lceil\log_{2}(\lceil(\operatorname{\_1}+2)/(\operatorname{\_2}+2)\rceil)\rceil}-2, \operatorname{\_2}\right), 0\right), 100)$Out$\bigl\lbrack1, 2, 1, 0, 5, 2, 3, 3, 2, 2, 3, 4, 1, 8, 5, 4, 2, 2, 3, 3, 2, 2, 7, 2, 9, 5, 2, 12, 9, 7, 5, 4, 2, 2, 3, 4, 1, 8, 5, 4, 2, 2, 3, 3, 2, 2, 15, 8, 5, 1, 43, 20, 13, 10, 3, 14, 7, 3, 11, 8, 3, 8, 5, 4, 2, 2, 3, 4, 1, 24, 13, 5, 4, 2, 11, 4, 5, 5, 4, 1, 13, 6, 5, 5, 4, 2, 7, 5, 3, 1, 3, 3, 2, 2, 31, 14, 10, 3, 3, 2\bigr\rbrack$

About

Examples	36
Checked against	Wolfram Language 35 agree1 differmathlib4 6 agree1 error
Crosswalk	Wolfram Language

Implementation

mappedmathlib4packages/oracle/src/mappings.ts

A left fold from the seed, as ours, so f(acc, element). The seedless two-argument form is not bound.

See also: Scan