2 weeks ago - last edited 2 weeks ago
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:
v
such that all v in til count v
d
in which all key[d]in d
m
in which (all raze m)in til count m
m
in which the range of each function is in til count m
2 weeks ago
Thanks for sharing another insightful post @SJT!
EMEA
Tel: +44 (0)28 3025 2242
AMERICAS
Tel: +1 (212) 447 6700
APAC
Tel: +61 (0)2 9236 5700
KX. All Rights Reserved.
KX and kdb+ are registered trademarks of KX Systems, Inc., a subsidiary of FD Technologies plc.