5. Dictionaries

5.0 Overview

A dictionary is a mapping defined by an explicit association between a key list and value list. The two lists must have the same count and the key list should be a unique collection. While general lists can be used to create a dictionary, most dictionaries involve simple lists of keys and are often names.

5.1 Dictionary Basics

A dictionary is an association between a list of keys and a list of values. Logically it can also be considered as key-value pairs but it is always stored as a pair of lists.

5.1.1 Construction

A dictionary, sometimes called an association, is a mapping defined by positional correspondence between a domain list of keys and a codomain list of values, which have the same count. General dictionary creation uses the ! operator in contrast with the syntactic form for lists.

keys!values

All dictionaries have type 99h.

Observe that the q console displays a dictionary as an I/O table.

q)`a`b`c!100 200 300
a| 100
b| 200
c| 300

q)10 20 30!1.1 2.2 3.3
10| 1.1
20| 2.2
30| 3.3

Neither the keys nor values need be simple lists but the keys should conform else odd things will happen during operations.

q)(`Arthur`Dent; `Zaphod`Beeblebrox; `Ford`Prefect)!100 42 150
Arthur Dent | 100
Zaphod Beeblebrox| 42
Ford Prefect | 150

q)1001 1002 1003!(`Arthur`Dent;`Zaphod`Beeblebrox;`Ford`Prefect)
1001| Arthur Dent
1002| Zaphod Beeblebrox
1003| Ford Prefect

A dictionary can be decomposed into its key and value lists using the primitives key and value. The common number of keys or values is returned by count.

q)d:`a`b`c!100 200 300
q)key d
`a`b`c
q)value d
100 200 300
q)count d
3

Although q does not enforce uniqueness for keys during dictionary creation (considered a design flaw by some), a dictionary does provide a unique output value for each input value. Indeed, only the first key occurrence is seen during lookup.

The order of the items in the key and value lists is significant, just as positional order is significant for lists. Although the I/O assignments and the associated mappings are equivalent regardless of order, differently ordered dictionaries are not identical.

q)(`a`b`c!10 20 30)~`a`c`b!10 30 20
0b

5.1.2 Empty and Singleton Dictionaries

You can create a general empty dictionary using empty key and value lists. Just as with lists the console does not display an empty dictionary but it can be seen using .Q.s1.

q)()!()
q).Q.s1 ()!()
"()!()"

You can create a typed empty dictionary using typed empty key and value lists.

q)(`symbol$())!`float$()

Because both the keys and values are required to be lists, you must enlist atoms for a singleton dictionary.

q)enlist[`x]!enlist 42
x| 42

Tip

The following is not a singleton dictionary. This is a common mistake of newbies.

q)`x!42
`x!42

For those who want to know, it is actually an enumerated value for a link column. Are you sorry you asked?

5.1.3 Dictionary Definition Syntax

In practice, dictionary keys are often symbolic names as in our first example above.

q)`a`b`c!100 200 300
a| 100
b| 200
c| 300

In this case you can use literal dictionary definition syntax to specify it as key-value pairs. Whitespace in dictionary definition syntax is optional.

q)([a:100; b:200; c:300])
a| 100
b| 200
c| 300
q)([a:100; b:200; c:300])~`a`b`c!100 200 300
1b

Note

A moment of Zen meditation will reveal that this dictionary is the moral equivalent of a record or struct in traditional languages. For that reason we shall sometimes refer to a dictionary of this form as a record dictionary or record, especially in the context of tables.

Tip

If you know table definition syntax you might be tempted to say that literal dictionary definition is just a keyed table with only key columns. As my father used to say, let's don't and say we did.

Dictionary definition form makes empty and singleton record dictionaries easy since the cast and enlist are not necessary.

q)([])~(`symbol$())!()
1b
q)([a:100])~enlist[`a]!enlist 100
1b

Dictionary definition also makes it convenient to create a dictionary from variables.

q)a:10
q)b:20
q)c:30
q)([a;b;c])
a| 10
b| 20
c| 30

Use of dictionary definition syntax requires the keys to be valid symbolic q names, whereas this is not the case for dictionary creation in general.

q)([10:`a; 20:`b])
'type
    [0] ([10:`a; 20:`b])
            ^
q)10 20!`a`b
10| a
20| b

Important

Dictionary definition syntax does not allow duplicate keys. If it detects any, it will rename them. This can cause unexpected outcomes, so beware.

q)([a:10; b:20; c:30; a:40])
a | 10
b | 20
c | 30
a1| 40

Tip

Advanced: The remainder of this section can be skipped for first-timers as it is not necessary for basic understanding.

Similar to column specification in table definition syntax, omitted key names will be autogenerated by q.

q)([0; 1; 2])
x | 0
x1| 1
x2| 2

Note

As a general principle we strongly recommend against leaving things implicit in q, except for implicit function parameters.

As with literal list definition, omission of values results in projection.

q)d:([a:10; b:])
q)d 20
a| 10
b| 20

q)([k1:; k2:])[1;"a"]
k1| 1
k2| "a"

5.1.4 Dictionary Pattern

The dictionary pattern can be used with either the functional form ! or the bracketed dictionary definition form of dictionary creation. Akin to items in the list pattern, each item of the value portion of a dictionary pattern is itself a pattern. Matching is done by key and the matched value from the source is passed to the corresponding value sub-pattern within the dictionary pattern. See section 10.4 for the full treatment of pattern matching.

Both methods of dictionary definition can be used with pattern matching. Here we show the basic dictionary pattern. First are patterns to extract values using the ! form of definition and the equivalent dictionary definition form.

q)(10 20!(v1;v2)):10 20!"ab"
q)v1
"a"
q)v2
"b"

q)([low:l;high:h]):`low`high!42 98
q)l
42
q)h
98

Unlike the case for list patterns, dictionary match does not require a full match of key-value pairs. Keys in the source that are not present in the pattern do not signal an exception and are still present in the overall pattern assignment.

q)([goog:px]):`aapl`goog`ibm!198.42 177.84 281.83
q)px
177.84

5.1.5 Lookup

To find the output value corresponding to an input key, we look up the key. Lookup uses the same notation as indexing into a list: brackets or juxtaposition.

q)d:([a:10; b:20; c:30])
q)d[`a]
10
q)d `b
20

q)d1:10 20 30!`a`b`c
q)d1[10]
`a
q)d1 10
`a

Similar to list indexing, lookup of a value not in the key list of a dictionary results in a null whose type is that of the initial item in the value list.

q)d[`x]
0N

As with lists, key lookup in a dictionary is extended item-wise to a simple list of keys.

q)d[`a`c]
10 30
q)ks:`a`c
q)d ks
10 30

We note that the latter is composition of the list index position mapping with the dictionary mapping.

5.1.6 Reverse Lookup with Find `?`

Recall that the Find operator ? on a list returns the index of the first occurrence of the right operand.

q)10 20 30 10 40?10
0

Essentially Find inverts the positional retrieval mapping. Extending this concept to dictionaries means reversing the key-to-value mapping of lookup. That is, ? on a dictionary inverts lookup by mapping a value item to the first key associated to it. Duplicate keys are invisible to ?.

q)d:`a`b`c`a!10 20 30 10
q)d?10
`a

The result of Find on an argument not in the value list is a null whose type matches the initial item in the key list.

q)(`a`b`c!10 20 30)?40
`

5.1.7 Dictionary vs. List

It is possible to create a dictionary that seemingly behaves very much like an equivalent list by making the positional retrieval explicit.

q)L:10 20 30
q)d:0 1 2!10 20 30
q)L 0
10
q)d 0
10
q)L 1 2
20 30
q)d 1 2
20 30
d~L
0b

Despite the apparent application behavior, the two are not the same. One major difference is that dictionaries can be extended via assignment and a list cannot.

5.1.8 Non-unique Keys and Values

As mentioned previously, non-unique keys are tolerated when created with ! but lookup only sees the first occurrence.

q)dup:`a`b`a`c!10 20 30 20
q)dup[`a]
10

You can get all values for a non-unique key as follows.

q)value[dup] where `a=key[dup]
10 30

Reverse lookup will find only the first non-unique key and will only see the first non-unique value.

q)dup?30
`a
q)dup?20
`b

You can reverse lookup all keys mapping to a given value as follows.

q)where 20=dup
`b`c

5.1.9 Non-simple Keys and Values

Neither the key nor value lists of a dictionary are required to be atoms or uniform. Either can be nested lists.

q)d:(`a`b; `c`d`e; enlist `f)!10 20 30
q)d `f
30
q)d?20
`c`d`e

q)d:`a`b`c!(10 20; 30 40 50; enlist 60)
q)d `b
30 40 50
q)d?30 40 50
`b
q)d?enlist 60
`c
q)d?60
`c

Be forewarned that an irregular key or value list - i.e., items do not conform - will confound lookup or reverse lookup, respectively.

q)dwhackey:(1 2; 3 4 5; 6; 7 8)!10 20 30 40 / atom 6 is whack
q)dwhackey 1 2
10
q)dwhackey 6
0N
q)dwhackval:10 20 30 40!(1 2; 3 4 5; 6; 7 8) / atom 6 is whack
q)dwhackval?3 4 5
20
q)dwhackval?6
0N

The observed behavior is that lookup in either direction fails at the first item of different shape.

5.2 Operations on Dictionaries

Note

In general in q, operations that modify a data entity work on a copy of the original unless specified as in-place.

5.2.1 Amend and Upsert

As with lists, the items of a dictionary can be modified in-place via assignment to a key.

q)d:([a:10; b:20; c:30])
q)d[`b]:42
q)d
a| 10
b| 42
c| 30

In contrast to lists, dictionaries can be extended via assignment.

q)d:([a:10; b:20; c:30])
q)d[`x]:42
q)d
a| 10
b| 20
c| 30
x| 42

Let's examine more closely this capability to modify or extend a dictionary via key-value assignment. Given a dictionary d, a value k that matches the type of the keys of d and a value v that matches the type of the values of d, consider the assignment

d[k]:v

It updates the existing key-value association when k is in key d, or inserts (appends) a new key-value association when k is not in key d.

q)d:([a:10; b:20; c:30])
q)d[`b]:42      / update
q)d[`x]:100     / insert
q)d
a| 10
b| 42
c| 30
x| 100

This update/insert behavior is called upsert semantics. Because tables and keyed tables are dictionaries, upsert semantics permeate kdb.

5.2.2 Extracting a Sub-Dictionary

Dictionary lookup on a key or a list of keys returns the associated values. It is possible to extract both keys and values using an overload of the Take operator #. The left operand is a list of keys, the right operand is the source dictionary and the result is a sub-dictionary for the specified keys. Viewed as a mapping, the result is the original restricted to the specified keys.

q)d:([a:10; b:20; c:30])
q)d `a`c     / lookup values
10 30
q)`a`c#d    / extract sub dictionary
a| 10
c| 30
q)(enlist `c)#d
c| 30

In the event of duplicate keys, only the first is extracted.

q)dup:`a`b`a`c!10 20 30 20
q)`a`c#dup
a| 10
c| 20

This operation works with non-simple keys.

q)dns:(`a`dent; `f`prefect; `z`beebelbrox)!100 150 42
q)(`a`dent; `z`beebelbrox)#dns
a dent |     100
z beebelbrox| 42

5.2.3 Removing Entries

The adjoint operation to # is _, which removes key-value pairs. Its syntax is the same - i.e., a list of keys as the left operand and a dictionary on the right - but it returns the dictionary obtained by removing the key-value pairs for the specified keys.

Note

Whitespace is required to the left of _ if the left operand is a variable since _ is a valid name terminating character.

q)d:([a:10; b:20; c:30])
q)`a`c _ d
b| 20
q)b:enlist `b
q)b _ d
a| 10
c| 30
q)b_ d
'b_
    [0] b_ d
        ^

Observe that all occurrences of a key are removed and that attempting to remove a key that does not exist has no effect.

q)dup:`a`b`c`a!10 20 30 40
q)`a`c _ dup
b| 20
q)`x`a _ dup
b| 20
c| 30

Removing all the entries in a dictionary leaves a dictionary with empty key and value lists of the appropriate types. The console will not display the empty dictionary but you can force the display with .Q.s1. In this case we see the typed empty lists.

q)d:([a:10; b:20; c:30])
q)`a`b`c _ d
q).Q.s1!`a`b`c _ d
"(`symbol$())!`long$()"

The binary operator cut is the same as this overload of _ on a dictionary.

q)`a`c cut d
b| 20

There is another overload of _ with a dictionary on the left and a single key on the right that deletes just that key, which allows in-place deletion.

q)d _ `b
a| 10
c| 30

Finally we record here a special form of the delete template for removing entries from a dictionary by key. It will be useful when we discuss namespaces in Chapter 12.

q)d:([a:10; b:20; c:30])
q)delete a,b from d
c| 30

5.2.4 General Operations on Dictionaries

Because a dictionary is a map, it can be post composed with another map. The result is a dictionary whose key-value association is the composite of the original and the new map. Another way to say this is that applying a function to a dictionary effectively applies it to the value list.

Unary functions are straightforward.

`a`b`c!10 20 30 composed with neg:

`a      |->  10    |->     -10
`b      |->  20    |->     -20
`c      |->  30    |->     -30

q)neg ([a:10; b:20; c:30])
a| -10
b| -20
c| -30

And similarly for other unary maps.

q)2*d
a| 20
b| 40
c| 60
q)d=20
a| 0
b| 1
c| 0
q)f:{x*x}
q)f d
a| 100
b| 400
c| 900

When the domains of two dictionary maps are identical, performing a binary operation is also straightforward: do it value-with-value along the keys. For example, to add two dictionaries with a common list of keys, add their corresponding values,

q)d1:([a:1; b:2; c:3])
q)d2:([a:10; b:20; c:30])
q)d1+d2
a| 11
b| 22
c| 33

What happens when the domains lists are not identical? First, the domain of the resulting dictionary is the union of the domains - i.e., the union of the key lists. For items in the common domain - i.e., the intersection of the keys lists, we already know we should apply the operation value-with-value.

So the question becomes: what to do on non-common key items? The answer: Nothing! Since there really isn't anything to do where there is no matching key on the other side, simply carry the value to the result. In essence, this amounts to using the identity element for the operation in place of the missing value.

q)d1:([a:1; b:2; c:3])
q)d2:([b:20; c:30; d:40])
q)d1+d2
a| 1
b| 22
c| 33
d| 40

5.2.5 Join `,`

The join operator , merges two dictionaries. Clearly on disjoint keys the corresponding values should be carried over into the result.

q)d1:([a:10; b:20; c:30])
q)d2:([x:40; y:50])
q)d1,d2
a| 10
b| 20
c| 30
x| 40
y| 50

On common keys, the value of the right operand prevails over that of the left. This is consistent with the data of assignment flowing from right to left.

q)d1:([a:10; b:20; c:30])
q)d2:([a:100; b:200; c:300])
q)d1,d2
a| 100
b| 200
c| 300

In general, the entire right operand is upserted into the left operand.

q)d1:([a:10; b:20; c:30])
q)d2:([c:300; d:400])
q)d1,d2
a| 10
b| 20
c| 300
d| 400

This is equivalent to each key-value association being individually upserted into the left

q)d1:([a:10; b:20; c:30])
q)d1[`c]:300
q)d1[`d]:400
q)d1
a| 10
b| 20
c| 300
d| 400

Observe that join is not commutative: order matters.

q)d1,d2
a| 10
b| 20
c| 300
d| 400
q)d2,d1
c| 30
d| 400
a| 10
b| 20

5.2.6 Coalesce `^`

The coalesce operator ^ is related to , in that it employs upsert semantics to merge two dictionaries with right prevailing over left on common keys. The difference is that null values in the right operand do not prevail over the left.

q)d1:([a:10; b:0N; c:30])
q)d2:([a:100; b:200; c:0N])
q)d1^d2
a| 100
b| 200
c| 30

5.2.7 Arithmetic And Relational Operations

Following the general pattern, when an arithmetic operation is performed on dictionaries, the operation is performed on the common domain elements and the identity element is implied elsewhere. Of course the value lists must have proper types for the operation.

q)d1:([a:10; b:20; c:30])
q)d2:([b:200; c:300; d:400])
q)d1+d2
a| 10
b| 220
c| 330
d| 400

For equality and comparison operations on dictionaries, the indicated operation is performed over the common keys. On disjoint keys, the appropriate null is effectively substituted for missing values. Due to all nulls being equal, a null value on a disjoint key will report 1b under equality test.

q)([a:10; b:20; c:30])=([b:20; c:30; d:40])
a| 0
b| 1
c| 1
d| 0
q)([a:0N; b:20; c:30])=([b:20; c:300; d:0N])
a| 1
b| 1
c| 0
d| 1
q)([a:10; b:20; c:30])<([b:20; c:300; d:400])
a| 0
b| 0
c| 1
d| 1

5.3 Column Dictionaries

Column dictionaries are the foundation for tables.

5.3.1 Definition and Terminology

A very useful type of dictionary maps a simple list of symbols to a rectangular list of lists.

q)`c1`c2!(`a`b`c; 10 20 30)
c1| a b c
c2| 10 20 30

This is clearer in dictionary definition syntax.

q)([c1:`a`b`c; c2:10 20 30])
c1| a b c
c2| 10 20 30

Interpreting each symbol as a column name and the corresponding list as a vector of column values, we call such a list a column dictionary. A general column dictionary has the form,

c₁...c_n!(v₁;...;v_n)

or

([c₁:v₁; ...; c_n:v_n])

where each c_i is a symbol and the v_i are expressions that reduce to lists with common length count. Such a dictionary associates the name c_i with the value list v_i.

The type of the column named by c_i is the type of its associated value list v_i. Often the v_i are all simple lists - i.e., each column is a vector of atoms of uniform type.

5.3.2 Simple Example

Let's make a column dictionary that holds the names of famous galactic travelers and their IQ scores.

q)travelers:([name:`Dent`Beeblebrox`Prefect; iq:42 98 126])
q)travelers
name| Dent Beeblebrox Prefect
iq | 42 98 126

In this dictionary, the values for the name column are,

q)travelers[`name]
`Dent`Beeblebrox`Prefect

Since this column is a list, we can index into it.

q)travelers[`name][1]
`Beeblebrox
q)travelers[`iq][2]
126

As with lists, when we encounter repeated indexing in q we can alternatively write it as indexing at depth.

q)travelers[`name; 1]
`Beeblebrox
q)travelers[`iq; 2]
6

Thus travelers can be considered a two-dimensional entity indexed by name in the first slot and position in the second.

5.3.3 General Case

For a general column dictionary defined as,

dc:c₁...c_n!(v₁;...;v_n)

or

dc:([c₁:v₁; ...; c_n:v_n])

the i^th element of column c_j is retrieved by,

dc[c_j][i]

Or equivalently,

dc[c_j;i]

The indexing at depth notation suggests thinking of the column dictionary as a two-dimensional data structure, indexed by column name and column position. Alternately, it is a positional map of two variables with symbolic name in the first parameter and column index in the second.

Specifying just an index in the second column is interesting. It essentially retrieves a "slice" of the original dictionary across that index. This slice is itself a dictionary. In our simple example of the previous section,

q)travelers[; 2]
name| `Prefect
iq | 126

Let's summarize.

A column dictionary can be viewed a two dimensional entity with retrieval by name in the first dimension and by position within column in the second.
Specifying only a name retrieves the corresponding column, which can then be indexed by position.
Specifying only a column index retrieves a slice dictionary that maps the names to the associated values across that column index.

This data structure is useful but there is a hitch: the indexing is backwards. That is, columns are retrieved in the first slot. Normally in two dimensional data structures, columns are retrieved in the second slot. We shall see shortly how to fix this.

5.3.4 Column Dictionary with a Single Column

Recall that every dictionary is constructed from a list of keys and a list of values. A column dictionary is further required to have a rectangular list of values - i.e., a list of lists of the same length. Thus in order to create a column dictionary with a single column, we need to enlist the single key and enlist the single column list.

q)dc1:(enlist `c)!enlist 10 20 30
q)dc1
c| 10 20 30

In this case we are better off using dictionary definition syntax.

q)dc1~([c:10 20 30])
1b

And we can even do this.

q)([c:10])
c| 10

Tip

As noted previously, the following isn't even a valid dictionary, let alone a column dictionary.

q)`c!1 2 3
`c!1 2 3

5.5 Flipping a Dictionary

No, this isn't what you do to a dictionary that cuts you off in traffic. Recall that a rectangular nested list can be transposed with the flip operator.

q)L:(10 20 30; 100 200 300)
q)L
10 20 30
100 200 300
q)flip L
10 100
20 200
30 300

A side effect of transposing the nested list data is that it reverses the slots for indexing at depth.

q)M:flip L
q)L[0;0]
10
q)L[0;1]
20
q)L[0;2]
30
q)M[0;0]
10
q)
q)M[1;0]
20
q)M[2;0]
30

Also recall that applying flip to a nested list creates a copy of the original list in which the data has been reorganized.

When a column dictionary is considered as a two-dimensional entity it is rectangular, since its column lists all have the same count. The console display shows this.

q)([c1:`a`b`c; c2:10 20 30])
c1| a b c
c2| 10 20 30

Thus it makes sense to transpose this rectangular data structure. Observe that the console display is exactly transposed.

q)show dc:([c1:`a`b`c; c2:10 20 30])
c1| a b c
c2| 10 20 30

q)show t:flip dc
c1 c2
-----
a 10
b 20
c 30

We expect the transposed entity to have the slots reversed for indexing at depth and they do.

q)dc[`c1; 0]
`a
q)dc[`c1; 1]
`b
q)dc[`c1; 2]
`c
q)t[0; `c1]
`a
q)t[1; `c1]
`b
q)
q)t[2; `c1]
`c

Voila! We have fixed the indexing problem with our column dictionaries. Columns are now indexed in the second parameter. Let's transpose the other aspects of the column dictionary retrieval into the new setting.

q)dc[`c1;]
`a`b`c
q)t[;`c1]
`a`b`c

q)dc[; 0]
c1| `a
c2| 10
q)t[0;]
c1| `a
c2| 10

q)dc[`c2; 1]
20
q)
q)t[1; `c2]
20

For the moment, forget the origin of t as a transposed column dictionary and examine it in isolation.

q)t[;`c1]
`a`b`c
q)t[0;]
c1| `a
c2| 10
q)t[1; `c2]
20

Let's look more closely at the slice dictionaries that are now indexed in the first slot. Recall that we are permitted (although not encouraged) to omit trailing semicolons for elided indices.

q)q)t[0]
c1| `a
c2| 10
q)t[1]
c1| `b
c2| 20
q)q)t[2]
c1| `c
c2| 30

If you were to meet such a beast on the street, you might think that it is a list of these funky record dictionaries.

We summarize our findings about the transpose of a column dictionary,

It is a two-dimensional data structure that uses an integer index in the first slot and a column name symbol in the second slot.
Specifying only an integer in the first slot retrieves a slice dictionary across that index
Specifying only a column name in the second slot retrieves that column.
Specifying both an integer and a column name retrieves the "field" at the intersection of that index and that column.
It can be viewed as a list of sliced record dictionaries.

In general, if you transpose something twice, you get back the original.

q)dc~flip flip dc
1b
q)dc~flip t
1b

We restate this as:

The flip of a transposed column dictionary is a (the original) column dictionary

Important

Unlike the case of transposing rectangular lists, transposing a column dictionary does not physically re-arrange data. Instead, the result is a logical adjustment – meaning that the slots in indexing at depth are reversed. Thus our final observation.
A transposed column dictionary is stored in column order.

Spoiler Alert: A flipped column dictionary is a table.

5. Dictionaries

5.0 Overview

5.1 Dictionary Basics

5.1.1 Construction

5.1.2 Empty and Singleton Dictionaries

5.1.3 Dictionary Definition Syntax

5.1.4 Dictionary Pattern

5.1.5 Lookup

5.1.6 Reverse Lookup with Find ?

5.1.7 Dictionary vs. List

5.1.8 Non-unique Keys and Values

5.1.9 Non-simple Keys and Values

5.2 Operations on Dictionaries

5.2.1 Amend and Upsert

5.2.2 Extracting a Sub-Dictionary

5.2.3 Removing Entries

5.2.4 General Operations on Dictionaries

5.2.5 Join ,

5.2.6 Coalesce ^

5.2.7 Arithmetic And Relational Operations

5.3 Column Dictionaries

5.3.1 Definition and Terminology

5.3.2 Simple Example

5.3.3 General Case

5.3.4 Column Dictionary with a Single Column

5.5 Flipping a Dictionary

5.1.6 Reverse Lookup with Find `?`

5.2.5 Join `,`

5.2.6 Coalesce `^`