FoldList

Every intermediate result of folding f over a list.

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

FoldList(f, x0, list)$\{x_0, f(x_0,a_1), f(f(x_0,a_1),a_2), \ldots\}$ — one longer than $list$.

FoldList(f, list)like the 3-argument form, using the first element of $list$ as $x_0$ and folding over the rest.

Typed signatures

Type	Package	Applies
((any, any) any -> any, any, collection<any>?) -> collection	combinatorics	always

Domain: Collections

Details

• The last element equals Fold($f$, $x_0$, $list$).
• See Accumulate for the common case $f = Add$.

Examples

Basic #

live ↗

In$\mathrm{FoldList}(\mathrm{Add}, 0, \bigl\lbrack1, 2, 3\bigr\rbrack)$Out$\bigl\lbrack0, 1, 3, 6\bigr\rbrack$

Each partial result nests to the left, starting from the seed

live ↗

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

With Add this gives the running sums, seeded at $0$

live ↗

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

Without a seed the first element starts the accumulation

live ↗

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

A non-associative operation shows the left-nested grouping explicitly

live ↗

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

Scope #

With no seed, the first element of the list is the seed

live ↗

In$\mathrm{FoldList}(\mathrm{Add}, \bigl\lbrack1, 2, 3\bigr\rbrack)$Out$\bigl\lbrack1, 3, 6\bigr\rbrack$

Running products, via Multiply instead of Add

live ↗

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

A lazy Range, not a materialised List -- see Length's own note on the same distinction

live ↗

In$\mathrm{FoldList}(\mathrm{LCM}, 1, 2..10)$Out$\bigl\lbrack1, 2, 6, 12, 60, 60, 420, 840, 2\,520, 2\,520\bigr\rbrack$

Known value · Hand-computed by iterated pairwise LCM of 2..10 (lcm(1,2)=2, lcm(2,3)=6, lcm(6,4)=12, ..., lcm(840,9)=2520, lcm(2520,10)=2520) -- an independent check that a lazy [[Range]] argument is walked element by element, not read off its own two constructor arguments (2 and 10)

Applies a sequence of permutations to a list, keeping each intermediate arrangement

live ↗

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

live ↗

In$\mathrm{FoldList}(\mathrm{Cross}, \bigl\lbrack\bigl\lbrack1, -1, 1\bigr\rbrack, \bigl\lbrack0, 1, 1\bigr\rbrack, \bigl\lbrack1, 1, -1\bigr\rbrack\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack1, -1, 1\bigr\rbrack, \bigl\lbrack-2, -1, 1\bigr\rbrack, \bigl\lbrack0, -1, -1\bigr\rbrack\bigr\rbrack$

Applications #

Running products of the first ten primes are the primorials

live ↗

In$\mathrm{FoldList}(\mathrm{Multiply}, 1, \mathrm{Array}(\mathrm{NthPrime}, 10))$Out$\bigl\lbrack1, 2, 6, 30, 210, 2\,310, 30\,030, 510\,510, 9\,699\,690, 223\,092\,870, 6\,469\,693\,230\bigr\rbrack$

A running maximum records each new record high and holds it between

live ↗

In$\mathrm{FoldList}(\mathrm{Max}, 0, \bigl\lbrack1, 3, 1, 2, 4, 1, 5, 3, 6, 2, 8, 11\bigr\rbrack)$Out$\bigl\lbrack0, 1, 3, 3, 3, 4, 4, 5, 5, 6, 6, 8, 11\bigr\rbrack$

Folding part extraction walks into an expression by successive indices

live ↗

In$\mathrm{FoldList}(\mathrm{At}, (a+b)(x^2+y^2), \bigl\lbrack2, 1, 1\bigr\rbrack)$Out$\bigl\lbrack(a+b)(x^2+y^2), x^2+y^2, x^2, x\bigr\rbrack$

Appending as it goes builds every prefix of the list

live ↗

In$\mathrm{FoldList}(\mathrm{Append}, \bigl\lbrack x\bigr\rbrack, \bigl\lbrack a, b, c, d\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack x\bigr\rbrack, \bigl\lbrack x, a\bigr\rbrack, \bigl\lbrack x, a, b\bigr\rbrack, \bigl\lbrack x, a, b, c\bigr\rbrack, \bigl\lbrack x, a, b, c, d\bigr\rbrack\bigr\rbrack$

Folding with List exposes the left-nested pairing as nested brackets

live ↗

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

Folding $10a + b$ turns a digit list into its running decimal prefixes

live ↗

In$\mathrm{FoldList}((\operatorname{\_1}, \operatorname{\_2})↦10\operatorname{\_1}+\operatorname{\_2}, 0, \bigl\lbrack4, 5, 1, 6, 7, 8\bigr\rbrack)$Out$\bigl\lbrack0, 4, 45, 451, 4\,516, 45\,167, 451\,678\bigr\rbrack$

Indexing each result by the next element gives the same walk as At

live ↗

In$\mathrm{FoldList}((\operatorname{\_1}, \operatorname{\_2})↦\operatorname{\_1}[\operatorname{\_2}], (a+b)(x^2+y^2), \bigl\lbrack2, 1, 1\bigr\rbrack)$Out$\bigl\lbrack(a+b)(x^2+y^2), x^2+y^2, x^2, x\bigr\rbrack$

Running products of $1..10$ are the factorials $0!$ through $10!$

live ↗

In$\mathrm{FoldList}(\mathrm{Multiply}, 1, 1..10)$Out$\bigl\lbrack1, 1, 2, 6, 24, 120, 720, 5\,040, 40\,320, 362\,880, 3\,628\,800\bigr\rbrack$

live ↗

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

live ↗

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

live ↗

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

live ↗

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

live ↗

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

Properties #

One longer than the input list

live ↗

In$\mathrm{Length}(\mathrm{FoldList}(\mathrm{Add}, 0, \bigl\lbrack1, 2, 3, 4, 5\bigr\rbrack))=\mathrm{Length}(\bigl\lbrack1, 2, 3, 4, 5\bigr\rbrack)+1$Out$\mathrm{True}$

The last element is what Fold alone would give

live ↗

In$\mathrm{Last}(\mathrm{FoldList}(\mathrm{Add}, 0, \bigl\lbrack1, 2, 3\bigr\rbrack))=\mathrm{Fold}(\mathrm{Add}, 0, \bigl\lbrack1, 2, 3\bigr\rbrack)$Out$\mathrm{True}$

An empty list leaves just the seed

live ↗

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

The result has one more entry than the list, the seed plus each step

live ↗

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

Cumulative sums of a list, one entry per element

live ↗

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

Ten elements and a seed give eleven results

live ↗

In$\mathrm{Length}(\mathrm{FoldList}(f, x, 1..10))$Out$11$

live ↗

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

Possible issues #

With no seed and no elements there is nothing to start from, so the result is empty

live ↗

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

About

Examples	31
Checked against	Wolfram Language 31 agreemathlib4 7 agree1 error
Crosswalk	Wolfram Language

Implementation

mappedmathlib4packages/oracle/src/mappings.ts

Every partial fold from the seed, one longer than the list. The seedless two-argument form is not bound.

See also: Fold, Accumulate