Skip to content

Implicit iteration

One of the most common qbie errors is to specify iteration unnecessarily.

Many of us have had our brains trained by other programming languages to loop through data structures. It’s close to a reflex.

One potato, two potato.

And this is a problem? Not at all. Exactly what you should do in C-style programming languages. You can probably write for-loops in your sleep.

You can probably write for-loops in your sleep.
You can probably write for-loops in your sleep.

We need you to wake up.

Waking up

Zen master Zuigan called out to himself each day.1

— Master!
— Yes, sir.
— Become sober.
— Yes, sir.
— Do not be deceived by others.
— Yes, sir; yes, sir.

First off, most binary operators iterate implicitly.

Scalar extension

No doubt you are familiar with examples such as

q)10 20 30 + 3 4 5
13 24 35
q)1000 + 3 4 5
1003 1004 1005

In the first, Add is applied between corresponding items of the two vectors. Two same-length vectors conform, and all is well.

In the second, atom 1000 is added to each item of the vector 3 4 5.

The conformists

Two data structures conform if

  • they are lists with the same number of items and corresponding items conform; or
  • one or both of them is an atom

This definition recurses. So let’s begin with the terminating case, when one is an atom.

The latter is sometimes described as ‘scalar extension’: an atom (scalar in the terms of an ancestor language) gets paired with every item of a list. So the following are identities:

3 4 5+1000
3 4 5+1000 1000 1000

That is true as far as it goes, but there is a good deal more going on here.

Atomic iteration

In atomic iteration scalar extension is applied recursively until atoms are reached.

q)L:(1 2 3;(4 5;(6;7 8));9;(10 11;12))
q)L+1000
1001 1002 1003
(1004 1005;(1006;1007 1008))
1009
(1010 1011;1012)

Since 1000 is an atom it conforms to any list, so winds up added to every atom in L.

You could think of atomic iteration here as an atomiser, spraying a cloud of atoms that settle onto every leaf of the L tree but the oversimplification obscures how atomic iteration actually works.

q)L+1000 2000 3000 4000
1001 1002 1003
(2004 2005;(2006;2007 2008))
3009
(4010 4011;4012)

Above we see the four items of L paired with the four ints.

  • 1000 adds to each of 1 2 3
  • 2000 adds to each of 4 5; to 6; to each of 7 8
  • 3000 adds to 9
  • 4000 adds to each of 10 11; to 12
q)L*(10;(10b);100b;1000)
10 20 30
(4 5;(0;0 0))
9 0 0
(10000 11000;12000)

Above

  • 10 multiplies 1 2 3
  • 1b multiplies 4 5; 0b multiplies 6 then 7 8
  • 100b multiplies 9
  • 1000 multiplies each of 10 11 then 12

Notice that in atomic iteration if one argument is an atom or vector the result mirrors the structure of the other argument.

But in the general case, as immediately above, you can count only on the top-level structure being replicated. That is, the result will have as many items as the argument list/s.

It will also conform to both.

Which operators and keywords iterate atomically?

  • Arithmetic operators +, -, *, %
  • Comparison operators =, <>, <, <=, >=, >
  • Logical operators |, &, or and and
  • Math keywords: abs, acos, asin, atan, ceiling, cos, div, exp, floor, log, mod, neg, rand, reciprocal, signum, sin, sqrt, tan, xexp, xlog
  • null and Fill ^
  • Index At @
  • Cast and Tok $, string
  • upper, lower

Some of these will be more familiar than others.

q)ceiling L*1.5
2 3 5
(6 8;(9;11 12))
14
(15 17;18)

q)acos neg (11b;(1b;(111b;11b);11b);1b)
3.141593 3.141593
(3.141593;(3.141593 3.141593 3.141593;3.141593 3.141593);3.141593 3.141593)
3.141593

q)(3 4;5)xexp(1;2 3)
3  4
25 125

The most common use case for Fill uses scalar extension to replace every null value with some other value, such as zero.

q)0^1 2 3 0N 5 6 0N 8 9  / zero for null
1 2 3 0 5 6 0 8 9
q)"-"^"string with spaces"
"string-with-spaces"

But Fill iterates – atomically.

q)"one slick brown dog"^"the quick       fox"
"the quick brown fox"

q)N:(1 0N 3;(4 5;(6;0N 8));9;(10 0N;12))
q)1000^N
1 1000 3
(4 5;(6;1000 8))
9
(10 1000;12)

q)1000 2000 3000 4000^N
1 1000 3
(4 5;(6;2000 8))
9
(10 4000;12)

Cast:

q)"hij"$101b
1h
0i
1

q)"bhij"$L
111b
(4 5h;(6h;7 8h))
9i
(10 11;12)

q)s
("The";"quick")
(("Brown";"Fox");"JuMpS")
"over"
(("the";"LAZY");"dog")

q)lower s
("the";"quick")
(("brown";"fox");"jumps")
"over"
(("the";"lazy");"dog")

There are also some variants on atomic indexing.

Index At

Index At is right-atomic – atomic only in its right domain.

q)"abcdefghi"@L
"bcd"
("ef";("g";"hi"))
" "
("  ";" ")

Tok

The right domain of Tok is strings. (We could say it treats atoms in its right domains as 1-item strings.) So recursion in its right domain stops at strings.

We could call Tok right string-atomic.

q)("B";"H";("I";"J");"F")$("123";"45";("6";"78");"999")
0b
45h
(6i;78)
999f

Nothing like like

The like keyword has its own kind of implicit iteration. Its left domain is either a string or a list of strings, according to which it returns a boolean atom or vector.

q)"brown"like"br?wn"
1b
q)("brown";"brawn";"frown";"brain")like"br?wn"
1100b

Not left string-atomic

like could be called left string-atomic if only it recursed through deeper structures – but it doesn’t.

q)string[(`brown;`brawn`frown;`brain)]like"br?wn"
'type
  [0]  string[(`brown;`brawn`frown;`brain)]like"br?wn"
                                           ^

Nothing iterates like like!

Aggregators

Aggregators iterate through the primary dimension of a list.

q)sum 3 5 8 13                    /items of a vector
29
q)sum (3 5 8 13;2 4 6 8;1 3 5 7)  /rows of a matrix
6 12 19 28

The sum keyword covers the derived function +/ Add Over, which is the map-reduce pattern.

A matrix is a list of same-length vectors. In applying Add between list items (rows) the rules of conformity hold, so sum can be applied to a nested list of conforming items.

q)sum (3 5 8 13;3;1 3 5 7)
7 11 16 23

q)sum (3 4;(5;6 7);(8 9;10))
16 17
20 21

The last example proceeds by adding 3 4 to (5;6 7) to get (8;10 11)then adds (8 9;10) to get (16 17;20 21).

From a rectangular array of rank \(N\) an aggregator returns a rectangular array of rank \(N-1\). Put another way, it reduces (removes) the first dimension of its argument.

Exercises

No peeking.

Attempt each exercise before looking at its answer.

The exercises clarify your thinking. Reading answers does not.

  1. Define two nested lists A and B such that A+B is a matrix.

    Answer 
    q)A:(1;2 3;4)
q)B:(5 6;7;8 9)
q)A+B
6  7
9  10
12 13

  2. With a little care you can write utility functions that iterate implicitly. Write a binary function to that returns the inclusive range between its integer arguments, e.g.

    q)to[3;7]
3 4 5 6 7
    Answer 
    to:{x+til 1+y-x}

  3. Get to to work with conformable arguments; e.g.

    q)to[3;5 8]
3 4 5
3 4 5 6 7 8

q)to[3 4;5 8]
3 4 5
4 5 6 7 8
    Answer 
    to:{x+til each 1+y-x}

  4. Get to to iterate atomically.

    q)to[(3;4 5);(6 7;8)]
3 4 5 6   3 4 5 6 7
4 5 6 7 8 5 6 7 8
    Answer 
    q)to:{x+til each 1+y-x}'

q)to[3;7]
3 4 5 6 7

q)to[3 4;5 8]
3 4 5
4 5 6 7 8

q)to[(3;4 5);(6 7;8)]
3 4 5 6   3 4 5 6 7
4 5 6 7 8 5 6 7 8

  1. From Paul Reps, Zen Flesh, Zen Bones ↩