Scan and Over
DRAFT
Over and Scan provide MapReduce and Fold as singlecharacter operators.^{1}
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 3e05
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 3e05
q)5(.1*)\3 / iteration 1 changes type
3
0.3
0.03
0.003
0.0003
3e05
q)(11>) (1+)\100
,100
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 Myokyoni 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
andreverse[b]
are searched for1b
 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?)
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
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
f
and the test expression are dictionaries, and the zero is 2000.01.01
.
Higherrank arguments
FIXME
Exercises

In
x f/y
andx f\y
what is the rank off
?Answer
In
x f/y
andx f\y
the rank off
can be only 1 or 2. If 1,
x
is either a nonnegative integer or a test expression.  If 2,
x
is the left value for iteration 1, which isf[x;y 0]
.
 If 1,

Predict the value of
t
andf
: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 andfn
10. 
Write a binary
f
so that for atomx
and vectory
,x f\y
is a general list, not a vector.Answer
The result of
x f\y
will be a vector as long asf[a;b]
returns an atom for atomsa
andb
. Any other result will havex 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 bytest 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 applyf
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 2dimensional 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, comparef\[x;y;z]
tof'[x;y;z]
. Comparef'[x;y;z]
tof[x]'[y;z]
. Isf\[x;y;z]
equivalent tof[x]\[y;z]
? Explain.Answer
In
f'[x;y;z]
all three arguments must conform; inf\[x;y;z]
only the right arguments must conform.In
f[x]'[y;z]
the binary projectionf[x;;]
is applied to corresponding items ofy
andz
. In each iteration the left argument is the full value ofx
.Similarly in
f[x]\[y;z]
the value of the first argument is fixed asx
; it is the value of the second argument that iterates successively. The items of resultr
: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 MapReduce when computer programs were still punched on cards. ↩