reduce() and scan(): Folding an Array Down to One Value, or Running It Up

reduce() and scan(): The Folding Functions

reduce(x, op) folds an array down to one value by applying an operation between the elements, left to right; scan(x, op) does the same but keeps every intermediate result — the running values. They take the same third-slot op as outer() (outer(): Every Element of One Array Against Every Element of Another): an operator written bare, or a built-in or one of your own routines with its parentheses. Read the Arrays page (Arrays) first.

1. Reduce: Fold to One Value

dim v(*) fill v with 3, 1, 6, 2, 5 print reduce(v, +) ! 17 -- the sum print reduce(v, *) ! 180 -- the product print reduce(v, max()) ! 6 print reduce(v, min()) ! 1 print reduce(v, -) ! -11 -- ((((3 - 1) - 6) - 2) - 5), left to right

reduce(v, +) is what stats$sum(v) gives you; the point of reduce is everything stats$ does not have — any operator, any built-in, any routine. The result is an ordinary value: assign it, test it, use it inside an expression:

total = reduce(v, +) average = reduce(v, +) / size(v) ! 3.4 if reduce(v, max()) > 5 then print "something big"

The fold runs left to right, which is the reading order and what scan shows step by step. (APL, where these functions come from, folds the other way — its -/3 1 6 2 5 is 11, not -11.)

A real fold: compound growth. An investment of 1000 grows by a different amount each year — up 5%, up 3%, down 2%, up 8%. Each year multiplies what came before, so chaining the yearly factors with a * fold gives the total growth in one line — and in exact decimal it holds every cent across the whole chain, where a run of floating-point multiplications would drift:

dim factors(*) fill factors with 1.05, 1.03, 0.98, 1.08 ! +5%, +3%, -2%, +8% print reduce(factors, *) ! 1.1446596 -- the total growth factor print 1000 * reduce(factors, *) ! 1144.6596 -- what the 1000 becomes

A running product like that is exactly what stats$ has no name for — the reason reduce takes any operator you like.

2. Scan: The Running Values

print scan(v, +) ! 3 4 10 12 17 -- running total print scan(v, max()) ! 3 3 6 6 6 -- running maximum print scan(v, -) ! 3 2 -4 -6 -11 dim balance(*) balance = scan(amounts, +) ! a running bank balance, one statement

scan keeps the shape: as many elements as the input, element k being the reduce of the first k.

3. Strings and Booleans Fold Too

dim names$(*) fill names$ with "apples", "pears", "oranges" print reduce(names$, +) ! applespearsoranges print reduce(names$, longer_of$()) ! oranges -- your own routine picks per pair print scan(names$, +) ! apples applespears applespearsoranges dim mask(*) mask = v > 2 print reduce(mask, and) ! 0 -- are they ALL above 2? print reduce(mask, or) ! 1 -- is ANY above 2? routine longer_of$ with a$, b$, returning r$ if len(b$) > len(a$) then r$ = b$ else r$ = a$ end routine

On a string array the one operator is + (the strings are joined); anything else takes a string function or routine. A mask of ones and zeros folds with and (all?) and or (any?).

4. Your Own Routines

Any routine with two with parameters and one returning parameter is a fold. The running value fills its first parameter, the next element its second; extras inside the parentheses fill parameter three onward, by position or by name, or come from defaults:

print reduce(v, weighted_add()) ! 17 -- w defaults to 1 print reduce(v, weighted_add(2)) ! 31 -- 3 + 2 * (1 + 6 + 2 + 5) print reduce(v, weighted_add(w = 10)) ! 143 print scan(v, weighted_add(2)) ! 3 5 17 21 31 routine weighted_add with a, b, w = 1, returning c c = a + b * w end routine

5. An Axis on a Multi-Dimensional Array

On a multi-dimensional array, reduce with no axis folds along the last dimension — on a matrix, one value per row — and that dimension disappears. That is APL's rule, and the natural reading of "reduce a table". axis: n picks a different dimension; all: true folds every cell, in storage order, down to one value.

dim g(2, 3) fill g with 1, 2, 3, 4, 5, 6 print reduce(g, +) ! 6 15 -- the last axis: one value per row print reduce(g, +, axis: 1) ! 5 7 9 -- down the rows: one value per column print reduce(g, max(), axis: 2) ! 3 6 print reduce(g, +, all: true) ! 21 -- every cell print scan(g, +, axis: 2) ! 1 3 6 -- scan keeps the shape ! 4 9 15

axis: takes one dimension; fold twice to collapse two. The shape that governs is the one the array has at run time — a dim z(*) holding a 2 by 3 result folds exactly as a 2 by 3 array does. What the surrounding code asks for sets the result's kind: in an array spot (an array assignment, a print) you get the array; in a scalar spot (total = reduce(z, +)) a result that is still an array raises a catchable error telling you to assign it to an expandable array instead.

6. With outer()

dim x(4), y(3) fill x with seq(1, 4) fill y with seq(1, 3) print reduce(outer(x, y, *), +, all: true) ! 60 -- the whole table summed print reduce(outer(x, y, >), +, all: true) ! 6 -- how many pairs have x > y print reduce(outer(x, y, *), +, axis: 2) ! 6 12 18 24 -- row by row

7. Big Numbers

Sheerpower's REAL is exact decimal up to 54 integer digits and floats with 64 significant digits beyond that, out to exponents of a billion. So this is one statement:

dim big(*) fill big with seq(1, 100_000) print reduce(big, *)

2.824229407960347874293421578024535518477494926091224850578917944e+456573

That is 100000 factorial: 456,574 digits long. The exponent is exact and so are the first 60 of the 64 digits shown; past 10⁵⁴ every one of the hundred thousand multiplications rounds at the 64th digit, and the accumulated rounding shows in the last four. (A double overflows at 170!.) Through 43! the product stays in the exact range, and every digit of it is real.

The rules, in one place. The fold runs left to right. With no axis, a declared multi-dimensional array folds its last axis; a 1-D array folds to a scalar; all: true folds every cell. An operator is bare (+ - * / ^, the six comparisons, and, or); a function or routine carries its parentheses. The op must give back the same type it takes — numbers to a number, strings to a string — because the running value feeds back in; numeric arrays fold as REAL. An empty array reduces to the operator's identity where it has one (+ 0, * 1, and 1, or 0) and otherwise raises the catchable exception EMPTYFOLD; scan of an empty array is empty. _integer is the number of pairs folded. The old scan(string, substring) search is untouched — the fold reading applies only when the first argument is an array.

The bigger picture. An expandable array is reshaped by whatever is assigned to it, and every array function honors the shape it holds right now. So a pair of declarations like dim z(*), r(*) gives you variables that behave like APL's: r can receive the result of any function that returns a 0-to-n dimensional array — outer() raising the rank, reduce() lowering it, scan(), reshape(), filter() keeping or reshaping it — with the shape travelling with the value, not the declaration. (Rank 0 lands in an array variable as a one-element array; a plain scalar variable is what you use in a scalar spot.)