Indexing

Indexing maps between data structures. It is deceptively powerful.

Indices of a list

The indices of a list are origin-zero ordinals.

q)`cow`duck`python`snail [3 1] 
`snail`duck

Above, the index expression is the vector 3 1.

Indices of a dictionary

The indices of a dictionary are its keys.

q)show d:`ATW`KEI`SJT!("Whitney";"Iverson";"Taylor") 
ATW| "Whitney"
KEI| "Iverson"
SJT| "Taylor"

q)d[2 3#`SJT`ATW]
"Taylor"  "Whitney" "Taylor"
"Whitney" "Taylor"  "Whitney"

Index notation

Select items from a list or dictionary by suffixing it with zero or more index expressions, separated by semicolons, and embraced in square brackets.

Index expression: An atom index or a list or dictionary in which the atoms are indices.

Indexing is right-atomic

The result of indexing a list mirrors the index expression.

q)1 type\" #"[1]        / atom index
"#"
-10h
q)1 type\" #"[1 0 1]    / vector index
"# #"
10h

q)" #"[5 3 0 4 2#'1]    / nested-list index
"#####"
"###"
""
"####"
"##"

A matrix is a list of same-length lists of uniform type.

q)show A:(11111b;10001b)[0 1 0 1 1]
11111b
10001b
11111b
10001b
10001b

q)" #"[A]               / matrix index
"#####"
"#   #"
"#####"
"#   #"
"#   #"

Indexing in depth

A matrix is a list of same-length lists of uniform type.

q)show m:3 5#15?100
12 10  1 90 73
90 43 90 84 63
93 54 38 97 88

Its items are its rows.

q)m[2 1]
93 54 38 97 88 
90 43 90 84 63

In a matrix the columns are its second axis or dimension. A second index expression indexes the columns.

q)m[2 1;2] 
38 90

Omitted index expressions

Omitting an index expression selects all indices in the corresponding dimension.

q)m[2;]
93 54 38 97 88 
q)m[;]
12 10 1  90 73 
90 43 90 84 63 
93 54 38 97 88

A general null is the same as an omitted index.

q)m[;2]
1 90 38
q)m[::;2]
1 90 38

Indices of a table

A table is a list of like dictionaries. Its first axis is indexed by non-negative integers. Its second axis is indexed by the column names as symbols.

q)a
species genus   feet
--------------------
cow     mammal  4
duck    bird    2
python  reptile 0
snail   mollusc 1

q)a[3 2]                / rows
species genus   feet
--------------------
snail   mollusc 1
python  reptile 0

q)a[1;`genus`species]   / rows and columns
`bird`duck

q)a[;`genus`species]    / columns
mammal  cow
bird    duck
reptile python
mollusc snail

Syntactic sugar allows you to index a table with just column names. It returns the columns as lists. (Table columns are most often, but not always, vectors.)

q)a[`genus`species]
mammal bird reptile mollusc
cow    duck python  snail

Invalid indices

An invalid (out of range) index to a vector returns a null of the same type as the vector.

q)(til 4)[4]        / long null
0N
q)(0.5*til 4)[4]    / float null
0n
q)now:.z.d+.z.t     / current timestamp
q)first 0#now
0Np
q)`a`b`c`d[4]       / symbol null
`

There is no boolean null. Instead you get 0b.

q)1001b[4]          / false
0b

For a list of strings you get an empty string.

q)("quick";"brown";"fox")[4]
""

For an empty general list you get – an empty general list.

q)() ~ ()[4]
1b

For any other general list you get … ah, that’s tricky. We’ll come back to that in the exercises.

q)(42;3.14159;"string";`symbol)[4]
0N
q)(42 43;3.14159;"string";`symbol)[4]
`long$()
q)(`symbol;42;3.14159;"string")[4]
`

A list of functions is not a vector, but a general list. An invalid index returns the Identity operator ::.

q)type (+;-;*;%)
0h
q)(::) ~ (+;-;*;%)[4]
1b

For a dictionary, the above rules are applied to the value list.

q)d
ATW| "Whitney"
KEI| "Iverson"
SJT| "Taylor"

q)d[`JHS]               / empty string
""

q)show e:`ATW`KEI`SJT!(`Arthur`Whitney;`Ken`Iverson;`Stephen`Taylor)
ATW| Arthur  Whitney
KEI| Ken     Iverson
SJT| Stephen Taylor

q)e[`JHS]               / empty symbol vector
`symbol$()

For a table, the above rules are applied to each of the column lists.

q)a[4 2]
species genus   feet
--------------------

python  reptile 0

q)a[4]
species| `
genus  | `
feet   | 0N

Invalid indices to general lists

When handing long vectors, mapping invalid indices to nulls is immensely valuable. Similarly for dictionaries and tables.

Q has corresponding rules for general lists, but the rules are by no means intuitive. The exercises below are not intended to help you to master and employ these rules for general lists, but to alert you to the difficulties.

Let your code use only valid indices to general lists.

Multiple dimensions

Rectangular list

A list in which the items are either all atoms or all rectangular lists of the same length.

Vectors and matrices are rectangular.

Rank

The rank of a list is the number of index expressions with which you can index it.

A vector can be indexed by only one expression; a matrix by two. Their respective ranks are 1 and 2.

In other contexts the rank of a rectangular list is known as the number of its axes or dimensions.

Do not confuse rank with the rank keyword, which concerns sorting.

Shape

The shape of a rectangular list is a vector of its counts on each axis.

The shape of a vector is a 1-item vector; the shape of a matrix is a 2-item vector.

You can form a rectangular list of shape shp with shp#.

Functional indexing

The Index and Index At operators make indexing a function.

.  / Index
@  / Index At

Index

You can select any item in a rank-$N$ list with the Index operator and a length-$N$ vector.

q)show m:3 4#til 12
0 1 2  3
4 5 6  7
8 9 10 11
q).[m;1 2]
6
q)m . 1 2
6

You can make a rectangular selection of a rank-$N$ list with a length-$N$ list.

q)m . (2 0;1)
9 1

Index At

The items of the right argument of Index are index expressions in successive dimensions of a list.

The items of the right argument of Index At @ are index expressions in its first dimension. That is, Index At indexes only items of the first axis; it does not ‘dive deep’.

Exercises

No peeking.

Attempt each exercise before looking at its answer.

The exercises clarify your thinking. Reading answers does not.

All data structures can be indexed. But what data structures cannot be used as index expressions? For example, can a dictionary be used as an index expression? A list of dictionaries? A table? In other words, in x@y what can y not be?

Answer

q)" #" ( 1 0 1; 1 1 0 1 1)   / nested integers
"# #"
"## ##"

q)" #" ( 1 0 1; 111011b)     / indices of mixed type
"# #"
"### ##"

q)" #" d:`tom`dick!01b       / dictionary with index values
tom |
dick| #

q)" #" ( 1 0 1; 111011b; d)  / list of mixed types including dict
"# #"
"### ##"
`tom`dick!" #"

q)" #" (d;d;d)               / list of like dictionaries (table)
'type
  [0]  " #" (d;d;d)
       ^

q)e:`tom`dick!(101b;11011b)  / list of unlike dictionaries 
q)" #" (d;e)
'type
  [0]  " #" (d;e)
       ^

q)" #" ( 1 0 1; 111011b; e;d)
"# #"
"### ##"
`tom`dick!("# #";"## ##")
`tom`dick!" #"

q)show f:`one`two`three!(11100b;d;e)
one  | 11100b
two  | `tom`dick!01b
three| `tom`dick!(101b;11011b)
q)" #" f
one  | "###  "
two  | `tom`dick!" #"
three| `tom`dick!("# #";"## ##")
q)" #" f`two`three
'type
  [0]  " #" f`two`three
       ^

A list of dictionaries – like or unlike – cannot be an index expression.

In your q session:
```
q)"abcdef" 1 0 3 6 1 4 4 5
"bad beef"
```
Explain the space in the result.

Answer

The space corresponds to index 6, which is invalid – out of range. An invalid index returns a null. The char null is a space.

In your q session:

b:6 cut 011100100010111100111110100000000000b  / boolean matrix
a:" a"!(5 5 5 5 5;0 1 3 1 1)                   / alphabet dictionary
b a "a"
" #" b a "a"

Explain what you see.

Answer

q)b a "a"
011100b
100010b
111110b
100010b
100010b

q)" #" b a "a"
" ###  "
"#   # "
"##### "
"#   # "
"#   # "

Above:

b is a matrix of rows in a 6-column digital display.
a is a dictionary mapping each letter to a list of rows from b.

In dictionary a make entries for keys "b", "c", "d", "e", and "f".

Evaluate " #" b a "c" and " #" b a "e".

Answer

q)a["bcdef"]:(3 1 2 1 3;0 1 4 1 0;3 1 1 1 3;3 4 2 4 3;3 4 2 4 4)
q)a
 | 5 5 5 5 5
a| 0 1 3 1 1
b| 3 1 2 1 3
c| 0 1 4 1 0
d| 3 1 1 1 3
e| 3 4 2 4 3
f| 3 4 2 4 4

q)" #" b a "c"
" ###  "
"#   # "
"#     "
"#   # "
" ###  "

q)" #" b a "e"
"##### "
"#     "
"####  "
"#     "
"##### "

Evaluate:
```
(,'/) " #" b a "bad beef"
```
If you see a length error signalled, check the previous exercise.

Describe in English what the above expression does. How would you say ,'/?
Answer
```
q)(,'/)" #" b a "bad beef"
"#####  ###  #####       ##### ##### ##### ##### "
"#   # #   # #   #       #   # #     #     #     "
"####  ##### #   #       ####  ####  ####  ####  "
"#   # #   # #   #       #   # #     #     #     "
"##### #   # #####       ##### ##### ##### #     "
```
Expression " #" b a "bad beef" maps
1. each letter to its list of rows
2. each list of rows to a bitmap
3. each bitmap to a char matrix of spaces and hashes
Finally, ,'/ (Join Each Over) joins corresponding rows from each char matrix into the result char matrix.
Show different ways you can set the type of an empty list.
Answer
```
"b"$()   / Cast
0#0b     / zero Take
```
Make an array (rectangular list) of rank 3 by using its shape as the left argument of Take.
Answer
```
q)show a3:2 3 4#.Q.a
"abcd" "efgh" "ijkl"
"mnop" "qrst" "uvwx"
```

Write a function shp that returns the shape of a rectangular list. Write a lambda or composition rnk that returns its rank. What is the shape and rank of an atom? Why is that?

Answer

q)shp:{-1_ count each first scan x}
q)shp a3
2 3 4
q)shp "string"
,6
q)rnk:count shp ::
q)rnk a3
3
q)rnk 3
0
q)shp 3
`long$()

q)shp a3                  / 3 axes
2 3 4
q)shp (101b;010b)         / 2 axes (matrix)
2 3
q)shp 42 43               / 1 axes (vector)
,2
q)shp 42                  / no axes (atom)
`long$()
q)rnk 42
0

With each step above, we remove an indexable dimension (axis) and the shape shortens. The atom 42 has no indexable dimensions; its shape is thus an empty vector and its rank is zero.

How could you determine the rank of a non-rectangular list?
Answer

The concepts of rank and shape are inherited from languages in which arrays are only rectangular. A q list is an array only while it happens to be rectangular. It’s not obvious that the concepts of shape and rank are helpful with a nested list.

However, you might usefully determine whether a list is an array:
```
q)same:{all x=first x}
q)rect:{$[0>type x;0b;same count each x]}
q)array:{$[rect x;all rect each x;0b]}

q)array a3
1b
q)show n3:(("abc";"def");("ghi";"jklm"))
"abc" "def"
"ghi" "jklm"
q)array n3
0b
```
And have shp signal a type error if its argument is not an array.
```
q)shp:{$[array x;-1_ count each first scan x;'`type]}
q)shp a3
2 3 4
q)count shp a3
3
q)count shp n3
'type
  [0]  rnk n3
       ^
```
1. Define a 4×5 matrix m and a variable ind so that m . ind returns the third column of m.
Answer
```
q)show m:4 5#.Q.a
"abcde"
"fghij"
"klmno"
"pqrst"

q)m[;2]
"chmr"

q)ind:(::;2)
q)m . ind
"chmr"
```
The right argument of Apply is a list of argument values; the right argument of Index is a list of index expressions. In either case, the general null :: corresponds to an omitted item.
The @ key on your keyboard has stopped working. Write a lambda at to use instead. (Assume the indices are all valid.)
Answer

The right argument of Index . is a list of expressions indexing the left argument on successive axes.

The right argument of Index At @ is a list of expressions indexing the left argument on its first axis. That is to say, it selects only the items of the left argument and makes no deeper selections.

Its right argument is the first and only right argument of Index:
```
x @ y   <==>   x . enlist y

at:{x . enlist y}
```