cancel
Showing results for 
Search instead for 
Did you mean: 

Iterating lists and dictionaries

SJT
Contributor III
Contributor III

Iterating a list or dictionary gives you a finite-state machine

You have probably heard that one of the founding insights of q is that lists and dictionaries are functions; that is, the domain of a list or dictionary is its indices; its range is its value. Q syntax reflects this.

 

q)sqr1:{x*x}
q)sqr2:0 1 4 9 16 25 36 49 64 81
q)sqr1 6 3 4
36 9 16
q)sqr2 6 3 4
36 9 16

 

This gives rise in the documentation to the ugly term applicable value – something you can apply to an argument or an index. In many places in the Reference you will find definitions that refer to value where you might be expecting to see function. And rank is defined for both functions (number of arguments) and lists (number of indexes). An operator such as Add, and a matrix: both have rank 2. 

Iterators let you iterate a function over a list. But if you look them up in the Reference you find their definitions refer to values, not functions. The definition says value because you can iterate a list or a dictionary.

The key to this is a list or dictionary such that, when you index it, you get a valid index. (And round you go.)

Here is a table describing a European tour. From it we make a dictionary in which each value is a valid key. 

 

q)yrp                               / a European tour
from   to     wp
----------------
London Paris  0
Berlin London 0
Milan  Vienna 1
Paris  Genoa  1
Genoa  Milan  1
Vienna Berlin 1

q)show route:.[!]yrp`from`to
London| Paris
Berlin| London
Milan | Vienna
Paris | Genoa
Genoa | Milan
Vienna| Berlin

 

Now we can trace routes.

 

q)(route\)`Genoa                           / a circular tour
`Genoa`Milan`Vienna`Berlin`London`Paris
q)3 route\`London                          / 3 legs of the tour
`London`Paris`Genoa`Milan
q)(`Berlin<>)route\`Paris                  / Paris to Berlin
`Paris`Genoa`Milan`Vienna`Berlin
q)waypoints:.[!]yrp`from`wp
q)waypoints route\`Paris                   / Paris to the end
`Paris`Genoa`Milan`Vienna`Berlin

 

A matrix has rank 2. If all its cells are valid row numbers, it can be used to iterate through a list of column numbers.

 

q)u  / all cells are valid row numbers
0 2 2
0 1 1
2 2 0
1 3 3

q)show c:5?3  / all items are valid column numbers
1 2 0 1 1

q)u[0] 1
2
q)u[2] 2
0
q)u[0] 0
0
q)u[0] 1
2
q)u[2] 1
2

q)0 u\c
2 0 0 2 2

 

A list has rank 1. A unary function has rank 1. So a list of unary functions has rank 2.

Below, a list of unary functions is used to test for a specific Regular Expression. Each unary function tests a character and returns the index of the test to apply to the next character.

 

/ want to match "x*fz*0*0"
q)m:({0};{2*x="x"};{2+x="f"};{2+/1 2*x="fz"};{4+x="0"};{5+x="0"};{7-x="0"};{7-x="0"})
q)flip(til count m;m)
0 {0}
1 {2*x="x"}
2 {2+x="f"}
3 {2+/1 2*x="fz"}
4 {4+x="0"}
5 {5+x="0"}
6 {7-x="0"}
7 {7-x="0"}

q)f:{6=1 m/x}  / 1 is the initial left argument
q)f"xyzffz000"
1b

 

(Thanks to Ahmed Shahbaz for the above version of the list.)

We have seen here finite-state machines represented by:

  • an integer vector v such that all v in til count v
  • a dictionary d in which all key[d]in d
  • an integer matrix m in which (all raze m)in til count m
  • a list of unary functions m in which the range of each function is in til count m
1 REPLY 1

davidcrossey
Moderator Moderator
Moderator

Thanks for sharing another insightful post @SJT!