Scan and Over

DRAFT

Over and Scan provide Map-Reduce and Fold as single-character operators.¹

The accumulators, Scan and Over, perform the same computations. They share the same Do, Converge and While forms for unary arguments.

They differ only in that

Scan (f\) returns the result of every iteration
Over (f/) returns the final result

Number of iterations

For long int n and test expression t

rank of f	expression	i (#iterations)	count[r]	r[0]
1	`r:f\[y]`	≥1 (Converge)	`i`	`y`
1	`r:n f\y`	`n` (Do)	`1+i`	`y`
1	`r:t f\y`	≥0 (While)	`1+i`	`y`
2	`r:x f\y`	`count y`	`i`	`f[x;first y]`
3–8	`r:f\[x;y;z;…]`	`max count(y;z;…)`	`i`	`f[x;first y;first z;…]`

In each of the forms above, f/ performs the same computation as f\, with the same number of iterations.

Zero iterations

The Converge, Do, and While forms all return a result in which the first item is the result of zero iterations; i.e. y.

q)0{'`ouch}\100      / zero iterations
,100
q)(til 6;5(.1*)\3.)  / (# iterations;result)
0 1   2    3     4      5
3 0.3 0.03 0.003 0.0003 3e-05

Data type change

Where f returns a result of different type than its argument/s the result of f\ is a mixed list.

q)5(.1*)\3.   / argument and results are all floats
3 0.3 0.03 0.003 0.0003 3e-05
q)5(.1*)\3    / iteration 1 changes type
3
0.3
0.03
0.003
0.0003
3e-05

q)(11>) (1+)\100
,100

Above, the test 11> is applied to the 0th iteration, i.e. y, the argument 100. The test fails, and the composition 1+ is not applied.

q){'`ouch} 100        / evaluation of the lambda signals an error
'ouch
  [0]  {'`ouch} 100
q)(11>){'`ouch}\100   / no evaluation of the lambda
,100

Converge

For Converge, the result of the evaluation that terminates iteration is not returned.

q)(neg\)1
1 -1

Do

Do as Cond

Suppose you have a test result test that is not a boolean but a long int; i.e. 0 or 1. You could use it in a conditional – or as a left argument to Do.

{$[test;f x;x]}   <==>   test f/x

In Jeff Borrors’ classic textbook Q for Mortals you will find frequent references to moments of “Zen meditation” leading to flashes of insight into the workings of q.

My teacher Myokyo-ni liked to quote the Third Patriarch:

The Great Way is not difficult. It avoids only picking and choosing.

The Do form of the Scan iterator has a pattern sometimes called ‘the Zen monks’.

The pattern is to apply a function and not to apply it.

Consider the trim keyword. It must find the spaces in a string, then the continuous spaces from each end. If we had to write trim in q it might be

q){b:x<>" ";(b?1b)_ neg[reverse[b]?1b] _ x}"   Trim the spaces.  " 
"Trim the spaces."

We notice the repetitions:

both b and reverse[b] are searched for 1b
two uses of the Drop operator

We want to do the search/drop thing from both ends of the string.

q){x{y _ x}/1 -1*(1 reverse\" "<>x)?'1b}"   Trim the spaces.  " 
"Trim the spaces."

Applying a series of left arguments

Notice the {y _ x}/ reduction above. Lambda {y f x} commutes an operator f by switching its arguments. The pattern R{y f x}/L successively applies a list of left arguments L to an argument R.

Here we use 1 reverse\ to get the boolean vector and its reversal. The 1 f\ pattern is known as the ‘Zen monks’. (Of course, we could write {(x;f x)} but where’s the fun in that?)

Zen monks

Here is another use for it, in finding the shape (rows and columns) of a matrix.

q)show m:{max[count each x]$'x}string`avoids`picking`and`choosing 
"avoids  " 
"picking " 
"and     " 
"choosing" 
q)shp:{count each 1 first\x} / shape of a matrix 
q)shp m 
4 8

The Zen Buddhist pension plan

A day without work is a day without food. — Baizhang Huaihai

Can you find any other work for the monks?

While

Final iteration

For the While form of Scan, the result of the evaluation that terminates iteration is returned.

q)(11>) (1+)\1
1 2 3 4 5 6 7 8 9 10 11

The test expression t is applied to the result of every iteration (even the 0th); so

t last t f\y   <==>   0

Test expression

The test expression t in t f/y and t f\y is any applicable value that could return a zero when applied to the result of an iteration. That is, a

keyword
projection
lambda
dictionary
list

And the zero is any value that casts to zero.

q)show bd:`bob`ted`sue`carol`mary`tom`dick!2000.01.01+1000* -3+til 7 /birthdays
bob  | 1991.10.15
ted  | 1994.07.11
sue  | 1997.04.06
carol| 2000.01.01
mary | 2002.09.27
tom  | 2005.06.23
dick | 2008.03.19
q)show likes:.[!]reverse 1 (1 rotate)\key bd / who likes whom
ted  | bob
sue  | ted
carol| sue
mary | carol
tom  | mary
dick | tom
bob  | dick
q)likes\[`tom] / chain of likes
`tom`mary`carol`sue`ted`bob`dick
q)bd likes\`tom / follow chain of likes to someone born 1/1/2000
`tom`mary`carol

Above, both f and the test expression are dictionaries, and the zero is 2000.01.01.

Higher-rank arguments

FIXME

Exercises

In x f/y and x f\y what is the rank of f?
Answer

In x f/y and x f\y the rank of f can be only 1 or 2.
- If 1, x is either a non-negative integer or a test expression.
- If 2, x is the left value for iteration 1, which is f[x;y 0].

Predict the value of t and f:

test:{t+:1;11>x}
fn:{f+:1;1+x}
(t;f):0 0
test fn\1

Answer

q)test:{t+:1;11>x}
q)fn:{f+:1;1+x}
q)(t;f):0 0;test fn\1
1 2 3 4 5 6 7 8 9 10 11
q)(t;f)
11 10

test was evaluated 11 times and fn 10.

Write a binary f so that for atom x and vector y, x f\y is a general list, not a vector.
Answer

The result of x f\y will be a vector as long as f[a;b] returns an atom for atoms a and b. Any other result will have x f\y evaluate to some other kind of list.
```
q)3{y?x}\2 4 5 4 2
2 0
0 0 2 2
0 0 0 0 2
0 0 0 2
0 0
```
If test is a long 0 or 1, the lambda {$[test;f x;x]} could be replaced by test f/x. Explain why this is not a smart substitution.

Answer

The two expressions are equivalent provided test is either long 0 or 1. But if it were, say, 100 then, while the lambda would still apply f once, test f/x would apply it 100 times.
Above, shp returns the shape of a matrix – rows followed by columns. That is, the shape of a 2-dimensional array. Write a version that returns as a vector the shape of an $N$-dimensional array.
Answer

Keep applying first – Converge will stop when it reaches an atom. Ignore the count of the atom.
```
shp:{-1_ count each first\[x]}  /lambda
shp: -1_ (count') (first\) ::   /composition
```

Find simpler equivalents for:

first 1 f\x
last  1 f\x
last  5 f\x

Answer

x
f x
5 f/x

Where f has rank 3, compare f\[x;y;z] to f'[x;y;z]. Compare f'[x;y;z] to f[x]'[y;z]. Is f\[x;y;z] equivalent to f[x]\[y;z]? Explain.
Answer

In f'[x;y;z] all three arguments must conform; in f\[x;y;z] only the right arguments must conform.

In f[x]'[y;z] the binary projection f[x;;] is applied to corresponding items of y and z. In each iteration the left argument is the full value of x.

Similarly in f[x]\[y;z] the value of the first argument is fixed as x; it is the value of the second argument that iterates successively. The items of result r:
```
r[0]   <==>   f[x;   y; z@0]
r[1]   <==>   f[x; r@0; z@1]
r[2]   <==>   f[x; r@1; z@2]
```

Scan and Over descend from the very first implementation of Iverson Notation in the 1960s. APL had Map-Reduce when computer programs were still punched on cards. ↩