Data structures

There are three data structures in q: atom, list and dictionary.

Atom

The simplest structure is no structure. An atom is indivisible, has no items and cannot be indexed.

List

An embraced sequence of zero or more items, separated by semicolons.

A list is ordered: its items are indexed by the natural numbers.

List item

A list item can be an atom, a list, or a dictionary.

General list

List notation: a general list is a series of items separated by semicolons and embraced by parens.

("a";`foggy;1942.04.02;in)

Parse tree

A list in which the first item is a function, and the rest its arguments.

(*;6;7)

Argument and expression lists

are embraced by square brackets.

["a";`foggy;1942.04.02;in]  / argument list
[a<b;c:2*a*b;foo::c%42]     / expression list

See Lambda Notation and Applying Functions for their use.

Vector

A list in which all items are data atoms of the same type.

The type of a vector is the negation of the type of one of its items.

Vector notation

Vector literals have their own notation according to datatype.

1 2 3 4             / long
1 2.0 3 4           / float
"abcdef"            / char
`abc`def`xyz        / symbol
2023.09 2023.10m    / month
..

Dictionary

A pair of same-length lists: the key and the value.

`alice`bob`carol`ted!25 37 32 35

The key list items are the indices of the dictionary.

Like dictionaries

Like dictionaries have identical key lists. (The order of keys matters.)

Simple table

A simple table is both

• a list of like dictionaries
• a list of named same-length lists

e.g.

q)name:`alice`bob`carol
q)age:25 37 32
q)hair:`fair`black`blonde
q)k:`name`age`hair

q)show t1:([]name;age;hair)
name  age hair
----------------
alice 25  fair
bob   37  black
carol 32  blonde

q)t2:k!/:((`alice;25;`fair);(`bob;37;`black);(`carol;32;`blonde))
q)t3:([]name:`alice`bob`carol;age:25 37 32;hair:`fair`black`blonde)

q)t1~/:(t2;t3)
11b

Keyed table

A dictionary in which both key and value are tables.

q)id:11 12 13
q)([name;id] hair;age)
name  id| hair   age
--------| ----------
alice 11| fair   25
bob   12| black  37
carol 13| blonde 32

Conformability

Two or more data structures conform if

• they are lists of the same length, in which corresponding items conform, or
• one or both is an atom.

Many primitives iterate implicitly through items of conformable lists.

1 2 3 + 4 5 6

Scalar extension

The matching of an atom with every item in a list.

1 2 3 + 4

Scalar extension applies to atoms but not to 1-item lists.

q)1 2 3 + 4
5 6 7
q)1 2 3 + 1#4
'length
  [0]  1 2 3 + 1#4
         ^

More on this later in Implicit Iteration.

Enlist

List notation is syntactic sugar for the enlist keyword.

q)(1;now;`abc;"abc") ~ enlist[1;now;`abc;"abc"]
1b

This means enlist is variadic: it can take any number of arguments. In particular, it can take more than 8.

A list with items omitted is a projection of enlist.

q)("Mary";"Khiloni";"Xin")(;"likes";)'("Ajay";"Carol";"Ingrid")
"Mary"    "likes" "Ajay"
"Khiloni" "likes" "Carol"
"Xin"     "likes" "Ingrid"

One-item lists

List notation provides no way to describe a list with one item.

q)type(3)  / atom 
-7h

The display form of a one-item list prefixes a comma.

q)1#3
,3

This is not a literal notation.

q),3
',
  [0]  ,3
       ^

The Join operator is binary, so cannot be used with prefix syntax.

You can make a one-item vector with the Take operator.

q)type 1#3 
7h

You can make a one-item vector by joining an atom to the general empty list.

q)type (),`ibm
11h

The enlist keyword makes any argument the sole item of a list.

q)count enlist 1 2 3
1

Type promotion

Assigning an atom to an item of a vector of another type signals a type error.

q)a:til 4
q)a[1]:0b
'type
  [0]  a[1]:0b
           ^
q)@[til 4;1;:;1.]
'type
  [0]  @[til 4;1;:;1.]
       ^

A general list is silently promoted to a vector at the first opportunity.

q)type a:(1;2;3.14159;4)  / general list
0h
q)@[a;2;:;3]              / vector
1 2 3 4
q)type @[a;2;:;3]
7h

Dictionaries

Key lists are often symbol vectors, but the structure is perfectly general: a dictionary can be made of any two lists of the same length, using the Dict ! operator.

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

q)type d  / a dictionary has type 99 
99h

The interpreter does not check for duplicate keys.

Ensure you have no duplicate key items. A dictionary with duplicate key items will behave in ways you would struggle to predict.

Are lists dictionaries? Arguably, a list is a dictionary in which the key is til count of the items.

Conversely, a dictionary is a more general form of list, in which you control the index.

This has implications for indexing.

• The indices of a list L are til count L.
• The indices of a dictionary k!v are k.

The syntax of indexing is the same for lists and dictionaries.

q)svect:`zero`one`two`three`four`five               / symbol vector
q)sdict:0 1 2 3 4 5!`zero`one`two`three`four`five   / symbol dictionary
q)svect 4 2
`four`two
q)sdict 4 2
`four`two

Tables

A table is a list of named same-length lists.

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

q)show a:([]species;genus;feet) 
species genus   feet 
--------------------
cow     mammal  4
duck    bird    2 
python  reptile 0 
snail   mollusc 1

A table is also a list of like dictionaries.

q)c:`species`genus`feet!(`cow;`mammal;4) 
q)d:`species`genus`feet!(`duck;`bird;2)
q)p:`species`genus`feet!(`python;`reptile;0) 
q)s:`species`genus`feet!(`snail;`mollusc;1)

q)show b:(c;d;p;s)
species genus   feet 
--------------------
cow     mammal  4
duck    bird    2 
python  reptile 0 
snail   mollusc 1

These two views of a table are equally valid.

q)a~b    / does a match b?
1b
q)type a
98h

Notation

Tables are first-class objects in q. They have their own notation.

A table is written as one or more conformable columns, separated by semicolons and prefixed by a list of zero or more key columns embraced by square brackets, all embraced by parentheses.

Columns

A column is either:

• the name of a variable, which provides both column name and value
• a value assigned to a name, which becomes the column name
• a value, in which case the column name is provided by q

Examples:

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

q)([]species;genus;feet)
species genus   feet
--------------------
cow     mammal  4
duck    bird    2
python  reptile 0
snail   mollusc 1

q)([`a`b`c`d]`mammal`bird`reptile`mollusc;feet:4 2 0 1;99)
x| x       feet x1
-| ---------------
a| mammal  4    99
b| bird    2    99
c| reptile 0    99
d| mollusc 1    99

---

Exercises

No peeking.

Attempt each exercise before looking at its answer.

The exercises clarify your thinking. Reading answers does not.

1. Write an example of a vector literal of each data type. Which data types do not have a notation for vector literals?

   Answer

   See the Datatypes. You should have examples for these types:

   1011b                                                        / boolean
   0x123456                                                     / byte
   0 1 2h                                                       / short
   0 1 2i                                                       / int
   0 1 2                                                        / long
   0 1 2e                                                       / real
   0 1 2f                                                       / float
   "012"                                                        / char
   `12`3                                                        / symbol
   2023.10.27D14:10:36.529000000 2023.10.27D14:10:42.613000000  / timestamp
   2023.01 2023.02 2023.03                                      / month
   2023.01.01 2023.01.02 2023.01.03                             / date
   2023.10.27T14:10:36.529 2023.10.27T14:10:36.529              / datetime
   0D00:00:00.000000001 0D00:00:00.000000002                    / timespan
   14:01 14:02 14:03                                            / minutes
   14:01:01 14:01:02 14:01:03                                   / seconds
   14:01:01.001 14:01:01.002 14:01:01.003                       / time
   

   There is no literal notation for GUID vectors.

2. If you use list notation rather than writing a vector literal, is the result a vector or a general list?

   Answer

   q)type (1;2;3;4)           / vector
   7h
   q)1 2 3 4 ~ (1;2;3;4)
   1b
   

3. Write a list of functions. What is its datatype?

   Answer

   q)type each(count;+;ssr;<>\;{x*x})
   101 102 100 108 100h
   q)type(count;+;ssr;<>\;{x*x})
   0h
   

   A general list. But what if the functions are all of the same type?

   q)type each(+;-;%)
   102 102 102h
   q)type(+;-;%)
   0h
   

   No: a list of functions is a general list.

4. Write a lambda that returns a list argument unchanged, but an atom as a 1-item list.

   Answer

   Some possible answers:

   {0<type x;(),x;x}
   {0<type x;1#x;x}
   {(1&neg type x)enlist/x}
   {(),x}
   

   The last lambda above could simply be replaced by the projection (),.

5. Can you demote a vector to a general list by joining it to an empty general list?

   Answer

   No, you cannot demote a vector by joining it to an empty general list.

   q)type 1 2 3,()
   7h
   q)type (),1 2 3
   7h
   q)1 2 3 ~ (),1 2 3
   1b
   

6. Your application keeps state (user queries) in a general list. The query parameters may be of different types, but if they happened to be the same, the list could get silently promoted to a vector and unable to record queries of any other type. How can you ensure the list is never promoted to a vector?

   Answer

   You can protect a general list from unintended promotion by including a function. A list with a function as an item will always be a general list.

   Any item will do, but using the first item means the list can easily vary in length.

   Any function will do, but using the Identity function :: prevents the list being taken for a parse tree.

   query:(::;`first;"second";reciprocal 3)
   

   Of course, as a list item, the Identity function is the general null.

7. A sparse array has many indices but few values. Write a sparse integer array sa with a million indices but non-zero values 100 200 300 (only) at indices 748428 5480 474634.

   What is the result of sa[748428 5490 474634 1000001]? What is the highest index of sa?

   Answer

   Nothing prevents us defining the sparse array as a simple list.

   q)sal: @[1000000#0N;748428 5480 474634;:;] 100 200 300  / simple list
   q)sal 748428 5490 474634 1000001
   100 0N 300 0N
   

   But what a waste of space. Index 5490 returns the null assigned there, and index 1000001 returns a null as the index is invalid.

   q)sa:748428 5480 474634!100 200 300
   q)sa 748428 5490 474634 1000001
   100 0N 300 0N
   

   Above, indices 5490 and 1000001 are both invalid and return nulls.

   The highest actual index of sa is 748428, but its highest possible index is long infinity.

   q)max key sa
   748428
   q)sa 0W
   0N
   

   Both sal and sa can be read at any integer index.

   q)sa[900000000]
   0N
   q)sal[900000000]
   0N
   

   But only sa can have values set at indices above 1000000.

   q)sa[900000000]:99
   q)sal[900000000]:99
   'length
     [0]  sal[100000000]:99
                        ^
   

8. Write a ternary lambda at that indexes x at y, but for invalid indices returns z instead of nulls.

   Answer

   The Fill operator ^ replaces null items.

   q)0^sa 748428 5490 474634 1000001
   100 0 300 0
   q){z^x y}[sa;748428 5490 474634 1000001;99]
   100 99 300 99
   

9. Does a dictionary have an order? If so, can it be sorted?

   Answer

   A dictionary is a pair of lists. Lists are ordered, so a dictionary is sortable.

   q)sa
   748428| 100
   5480  | 200
   474634| 300
   q)desc sa                  / sort by value
   474634| 300
   5480  | 200
   748428| 100
   q){k!x k:desc key x}sa     / sort by key
   748428| 100
   474634| 300
   5480  | 200
   

10. Make a list of dictionaries which have the same key items but not all in the same order. What type does it have? Write a lambda that takes a list of dictionaries whose keys have the same items and returns them as a table.

    Answer

    q)/similar - but not like - dictionaries.
    q)show sbnld:(`a`b`c!10 20 30;`c`b`a!40 50 60)
    `a`b`c!10 20 30
    `c`b`a!40 50 60
    
    q){x@\:key first x} sbnld
    10 20 30
    60 50 40
    

11. Define the table written above as ([]species;genus;feet). How many other ways can you find to construct this table? Show that each result matches the first.

    Answer

    species:`cow`duck`python`snail
    genus:`mammal`bird`reptile`mollusc
    feet:4 2 0 1
    ([]species;genus;feet)
    
    ([]species:`cow`duck`python`snail;
        genus:`mammal`bird`reptile`mollusc;feet:4 2 0 1)
    
    k:`species`genus`feet
    k!/:flip(`cow`duck`python`snail;`mammal`bird`reptile`mollusc;4 2 0 1)
    
    k!/:((`cow;`mammal;4);(`duck;`bird;2);(`python;`reptile;0);(`snail;`mollusc;1))
    

12. Make a table in which one column is specified as an atom. How is the column filled?

    Answer

    q)([]species;genus;feet;extinct:0b)
    species genus   feet extinct
    ----------------------------
    cow     mammal  4    0
    duck    bird    2    0
    python  reptile 0    0
    snail   mollusc 1    0
    

    Scalar extension applies: the atom fills every item in the column.

---