Iterating lists and dictionaries

Community Support
1

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:.[!]yrpfromto London| Paris Berlin| London Milan | Vienna Paris | Genoa Genoa | Milan Vienna| Berlin

 

Now we can trace routes.

 

q)(route)Genoa / a circular tour GenoaMilanViennaBerlinLondonParis q)3 route\London / 3 legs of the tour LondonParisGenoaMilan q)(Berlin<>)route\Paris / Paris to Berlin ParisGenoaMilanViennaBerlin q)waypoints:.[!]yrpfromwp q)waypoints route\Paris / Paris to the end ParisGenoaMilanVienna`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 “xfz00" q)m:({0};{2x=“x”};{2+x=“f”};{2+/1 2x=“fz”};{4+x=“0”};{5+x=“0”};{7-x=“0”};{7-x=“0”}) q)flip(til count m;m) 0 {0} 1 {2x=“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
2

Thanks for sharing another insightful post @SJT!