Accumulator iterators

Accumulator iterators apply a function repeatedly.

The two accumulator iterators Scan \ and Over / derive functions that apply successively to the (first) argument. The result of one iteration becomes the (first) argument of the next.

For unary f:

f/[x]   <===>   f f f .. x   <===>   f[f[f[..f[x]]]]

Scan and Over

For all f the derived functions f\ and f/ perform the same computation.¹ Scan returns the results of each iteration; Over only the last.

f/[x]   <===>   last f\[x]

Unary iterator argument

Where the iterator argument f is unary the derived function f\ or f/ is variadic.

It has three forms. Applied as a unary, Converge; as a binary, either Do or While.

Converge

Applied as a unary f\ and f/ repeat until the result matches either

the result of the previous iteration (convergence)
the initial value

q)(.000000000000000001*)\[1.]
1 1e-18 1e-36 1e-54 1e-72 1e-90 1e-108 1e-126 1e-144 1e-162 1e-180 1e-198 1e-..
q)(.000000000000000001*)/[1.]
0f
q)not\[1b]
10b

Notice that the result of the last iteration of the evaluation – that matches either the previous or the initial value – is not returned.

If the result does not converge or repeat, iteration does not terminate

Do

Applied as a binary with a positive integer left argument N, N f\y applies f to y successively N times.

q)3(.000000000000000001*)\1.
1 1e-18 1e-36 1e-54
q)3 not\1b
1010b
q)11{x,sum -2#x}/0 1   / Fibonacci sequence
0 1 1 2 3 5 8 13 21 34 55 89 144

The items of the result correspond to til N+1 successive applications of f to y. Thus N f\y has N+1 items; and the first item of f\ is the result of 0 applications of f to y; i.e. y.

While

Applied as a binary with a unary applicable value left argument, T f\y applies f to y successively until T applied to the result returns 0. In other words, T is a test applied to the result r of each iteration; iteration stops when T r is zero.

q){100>last x}{x,sum -2#x}/0 1
0 1 1 2 3 5 8 13 21 34 55 89 144

The last item is the first iteration result that fails the test.

If the test does not fail, iteration does not terminate.

Lambdas are the most common tests; but projections, compositions, dictionaries and lists will also serve.

q)(0^til[100]last@){x,sum -2#x}/0 1
0 1 1 2 3 5 8 13 21 34 55 89 144

Binary iterator argument

Where the iterator argument f is a binary, f\ and f/ iterate it successively through the items of its right argument/s.

Evaluation terminates after count y iterations.

The derived function f\ or f/ is variadic.

Unary application

For r:f\[x]

r[0]     x@0
r[1]   f[r@0;x@1]
r[2]   f[r@1;x@2]
..

q)mod\[(6 7; 5 4)]
6 7
1 3

For unary application, good style prefers prefer keywords.

q)(mod) scan (6 7;5 4)
6 7
1 3
q)(mod) over (6 7;5 4)
1 3

Binary application

For r:x f\y

r[0]   f[  x; y@0]
r[1]   f[r@0; y@1]
r[2]   f[r@1; y@2]
..

The first iteration applies f to all of x but only to the first item of y.

q)1000 2000+\3 4 5
1003 2003
1007 2007
1012 2012

Nulls

Where f is one of the four operators + - * &, for x f\y, x f/y, f\[y] and f/[y] null items in y are replaced by the operator’s right-identity element I:

f   +   -   *   &
I   0   0   1   0W

q){x+y}\[3 0N 5]
3 0N 0N
q)+\[3 0N 5]
3 3 8

For binary application this is true only when x is an atom.

q)1000+\3 0N 5
1003 1003 1008
q)1000 2000+\3 0N 5
1003 2003

Nulls in the left arguments can return unintuitive results.

q)0N+\3 4 5
-9223372036854775805 -9223372036854775801 -9223372036854775796
q)0N*\3 4 5
0N 0 0

Nulls are never replaced in x.

Higher-rank argument

Where the iterator argument f has rank 3 or more, f\ and f/ have the same rank as f. They iterate it successively through the items of its right argument/s.²

For r:f\[x;y;z]

r[0]   f[  x; y@0; z@0]
r[1]   f[r@0; y@1; z@1]
r[2]   f[r@1; y@2; z@2]
..

Right arguments of f\ or f/ must conform: i.e. be atoms or same-length lists.

q){x*y+z}\[1000 2000;3;5 6 7]
8000   16000
72000  144000
720000 1440000

Evaluation terminates after max count each(y;z;..) iterations.

Exercises

No peeking.

Attempt each exercise before looking at its answer.

The exercises clarify your thinking. Reading answers does not.

The following three applications of f\ return the same vector.
```
q)f:{ctr+:1; 0|x-.25}

q)ctr:0; show f\[1.]; show ctr
1 0.75 0.5 0.25 0
5
q)ctr:0; show 4 f\1.; show ctr
1 0.75 0.5 0.25 0
4
q)ctr:0; show (0<) f\1.; show ctr
1 0.75 0.5 0.25 0
4
```
The values of ctr vary. Why is that?

Answer

The Do form 4 f\1. performed exactly four iterations, as specified by the left argument of f\.

The While form (0<) f\1. iterated four times. The result of the fourth iteration was 0, so the test 0< failed and iteration stopped.

The Converge form stopped when the result of the fifth iteration matched the result of the fourth: 0.

Write an expression that returns all and only the terms of the Fibonacci sequence less than 2000.

Answer

The Fibonacci sequence is extended by appending the sum of its last two items. A q lambda expresses that concisely and precisely.

q)fib:{x,sum -2#x}
q)20 fib/0 1
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
q)sum 2000>20 fib/0 1
18i
q)16 fib/0 1               / Do
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597

Oh, was that cheating?

So test for when we have already passed 2000. (And drop the last one.)

q)-1_ (2000>last@)fib/0 1  / While
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597

For ternary f compare f\[x;y;z] and f'[x;y;z].
Answer

Compare Scan rs:f\[x;y;z] to Each re:f'[x;y;z].
1. In Each, arguments x, y, and z must conform. In Scan, arguments y and z must conform.
2. Both expressions will perform max count each(y;z) evaluations.
3. With Each re[i] is the result of f[x@i;y@i;z@i] and the evaluations are independent and can be performed in parallel.
4. With Scan, rs[i] is the result of f[r@i-1;y@i;z@i] and the evaluations must be successive.

Chinese Whispers: Use Scan or Over to transform Going to advance. Please send me reinforcements. into Going to a dance. Please lend me three-and-fourpence.

Answer

q)s:"Going to advance. Please send me reinforcements."
q)heard:("send";"reinforcements";"advance") / heard
q)said:("lend";"three and fourpence";"a dance")
q)ssr\[s;heard;said]
"Going to advance. Please lend me reinforcements."
"Going to advance. Please lend me three and fourpence."
"Going to a dance. Please lend me three and fourpence."

Because Over does not need to retain results of intermediate iterations, it can in some cases execute faster than Scan and require less memory. ↩
Usage: The first and second arguments of a binary are its left and right arguments – whether it has infix syntax or not. For a higher-rank function, its first argument is the left argument and the rest are its right arguments. ↩