2 ms·
You might want indexing for linear list access. Here we have z in the dotted position of a nested list, which is tricky to connect to a simple index. Even if w
by kazinator 4y ago
You might want indexing for linear list access. Here we have z in the dotted position of a nested list, which is tricky to connect to a simple index.
Even if we set nesting aside, our z could be in these positions:
z ;; z is the object itself
(z)
(y . z)
(y)
(x y . z)
(x y z)
and so on.
Numeric navigation of the tree structure is possible in various forms. TXR Lisp has the functions cxr and cyr which use a bitmask "address" argument to navigate the car/cdr links. The address 0 is invalid, 1 is a noop. Other than that, bit 1 means car and 0 means cdr. cxr and cyr differ in the order of the bits.
1> (cxr #b10101 '((x (y . z))))
z
I.e.
1> (cxr 21 '((x (y . z))))
z
To interpret the bitmask, we ignore the upper framing bit and follow the 0101 right to left: 1=car, 0=cdr, 1=car, 0=cdr. Of course, this just being a function argument, it can be computed. Any positive integer is a potentially valid address in some cons structure.
Indexing is supported, but doens't reach dotted positions; it is geared toward sequences, not cons structure.
2> [[['(a b (c d e (f))) 2] 3] 0]
f
That could be compressed into some kind of path mechanism where you just have the indices as 2 3 0.
The numeric address idea is inspired by the tree addressing system in Urbit's Nock. This is explained as a layer-by-layer enumeration using successive natural numbers:
1
2 3
4 5 6 7
Address is 1 is "this object". Then 2 is car, and 3 is cdr. Note that these have a binary structure 10 and 11. Similarly 4, 5, 6, 7 are 100 101 110 and 111. You can see that the bits mean 0=car 1=cdr, left to right, after skipping the framing 1 bit.
I swapped their meaning in my implementation and provided a right-to-left function.
I don't remember the exact reason I swapped the roles, but likely it was because linear lists are more common than nested lists. You do more cdr than car, loosely speaking. For instance, the simple positions in a linear list are all cdr operations followed by car: car, cadr, caddr, cadddr, ... if cdr is 0, then these look like 11, 110, 1100, 11000:
40> (cxr #b11 '(1 2 3 4 5 6))
1
41> (cxr #b110 '(1 2 3 4 5 6))
2
42> (cxr #b1100 '(1 2 3 4 5 6))
3
43> (cxr #b11000 '(1 2 3 4 5 6))
4
44> (cxr #b110000 '(1 2 3 4 5 6))
5
In other words, 3 is car, and then we just arithmetically left shift the 3 to get the other positions. If cdr is 1, then we have to left shift and mask in a 1 to replace the 0 that was shifted in.