Chapter 32: Trees
32.1 Introduction
Data structures consisting of boxes within boxes may be called trees.
J provides several special functions in support of computations with trees.
Here is an example of a tree:
] T =: 'the cat' ; 'sat' ; < 'on' ; < ('the';'mat')
+-------+---+--------------+
|the cat|sat|+--+---------+|
| | ||on|+---+---+||
| | || ||the|mat|||
| | || |+---+---+||
| | |+--+---------+|
+-------+---+--------------+
Those boxes with no inner boxes will be called leaves. We see that T
has 7 boxes of which 5 are leaves.
32.2 Fetching
Evidently, the content of any box can be fetched from tree T
by a combination of indexing and unboxing.
] a =: > 2 { T
+--+---------+
|on|+---+---+|
| ||the|mat||
| |+---+---+|
+--+---------+
] b =: > 1 { a
+---+---+
|the|mat|
+---+---+
] c =: > 1 { b
mat
but there is a built-in verb, "Fetch" (dyadic {::) , for this purpose.
Its left argument is a sequence of indexes (called a path):
(2;1;1) {:: T
mat
Further examples:
2 {:: T
+--+---------+
|on|+---+---+|
| ||the|mat||
| |+---+---+|
+--+---------+
(2 ;1) {:: T
+---+---+
|the|mat|
+---+---+
32.3 The Domain of Fetch
The right argument of {:: must be a vector, or higher rank, and not a scalar,
or else an error results. (Recall that a single box is a scalar).
0 {:: , <'hello' |
0 {:: < 'hello' |
hello |
error |
Let us say that a full-length path is a path which fetches
the data content from a leaf.
Along a full-length path, every index must select a scalar, a box, or else
an error results. In other words, we must have a single path.
T |
(2; 1 ; 0 1) {:: T |
+-------+---+--------------+
|the cat|sat|+--+---------+|
| | ||on|+---+---+||
| | || ||the|mat|||
| | || |+---+---+||
| | |+--+---------+|
+-------+---+--------------+ |
error |
The data fetched from a leaf is the result of opening
the last box selected along the path. This data can, as we saw above,
be an array, a list say.
(2;1;1) {:: T
mat
If this data is an indexable array, then a further index can be
appended to a full-length path, giving an over-length path, to fetch a
further single scalar. The next example shows fetching 'm' from 'mat'.
(2;1;1;0) {:: T
m
32.4 The "Map" Verb
Monadic {:: is called "Map". It shows all the paths to the leaves.
{:: T
+---+---+-------------------------+
|+-+|+-+|+-----+-----------------+|
||0|||1|||+-+-+|+-------+-------+||
|+-+|+-+|||2|0|||+-+-+-+|+-+-+-+|||
| | ||+-+-+|||2|1|0|||2|1|1||||
| | || ||+-+-+-+|+-+-+-+|||
| | || |+-------+-------+||
| | |+-----+-----------------+|
+---+---+-------------------------+
32.5 What is the Height of This Tree?
The verb L. ("LevelOf") reports the length of the longest path
in a tree, that is, the maximum length
of a path to fetch the
unboxed data-content of a leaf. In the book "A Programming Language"
Kenneth Iverson uses the term "height" for the length of the longest path
of a tree.
The length of a path is the number of indexing-and-unboxing steps needed.
It is evident that it takes at most 3 steps to fetch any data-content from T
T |
L.T |
+-------+---+--------------+
|the cat|sat|+--+---------+|
| | ||on|+---+---+||
| | || ||the|mat|||
| | || |+---+---+||
| | |+--+---------+|
+-------+---+--------------+ |
3 |
One step is needed to fetch the content of the leaf of a tree consisting only of
a single leaf, for example ,<6 . The step is > @: (0&{)
A =: ,<6 |
L. A |
(> @: (0&{)) A |
0 {:: A |
+-+
|6|
+-+ |
1 |
6 |
6 |
and it evidently needs no steps to fetch the content of 'hello'
L. 'hello' |
(0$0) {:: 'hello' |
0 |
hello |
32.6 Levels and the L: Conjunction
A box with no inner box (a leaf) is said to be at level 0.
Here is another tree:
] D =: (<'one'; 'two'), (< 'three' ; 'four')
+---------+------------+
|+---+---+|+-----+----+|
||one|two|||three|four||
|+---+---+|+-----+----+|
+---------+------------+
We can apply a given function to the values inside the leaves, that is, at level 0,
with the aid of the L: conjunction (called "Level At").
Reversing the content of each level-0 node, that is, each leaf:
|. L: 0 D
+---------+------------+
|+---+---+|+-----+----+|
||eno|owt|||eerht|ruof||
|+---+---+|+-----+----+|
+---------+------------+
Reversing at level 1:
|. L: 1 D
+---------+------------+
|+---+---+|+----+-----+|
||two|one|||four|three||
|+---+---+|+----+-----+|
+---------+------------+
and at level 2:
|. L: 2 D
+------------+---------+
|+-----+----+|+---+---+|
||three|four|||one|two||
|+-----+----+|+---+---+|
+------------+---------+
We see that we can apply a function at each of the levels 0 1 2 .
The level at which the function is applied can also be specified
as a negative number:
|. L: _2 D
+---------+------------+
|+---+---+|+-----+----+|
||eno|owt|||eerht|ruof||
|+---+---+|+-----+----+|
+---------+------------+
|. L: _1 D
+---------+------------+
|+---+---+|+----+-----+|
||two|one|||four|three||
|+---+---+|+----+-----+|
+---------+------------+
Levels for trees are analogous to ranks for arrays.
L: is the analogue of the rank conjunction " .
32.7 The Spread Conjunction
We saw above that the result of the L: conjunction has the same
tree-structure as the argument. There is another conjunction, S: (called "Spread")
which is like L: in applying a function at a level, but unlike
L: in that the results are delivered, not as a tree but simply as a flat list.
D
+---------+------------+
|+---+---+|+-----+----+|
||one|two|||three|four||
|+---+---+|+-----+----+|
+---------+------------+
|. S: 0 D
eno
owt
eerht
ruof
The result above is a list (a "flat list") of 4 items,
each item being a string.
|. S: 1 D
+----+-----+
|two |one |
+----+-----+
|four|three|
+----+-----+
The result above is a list of 2 items, each item being a list of 2 boxes.
|. S: 2 D
+------------+---------+
|+-----+----+|+---+---+|
||three|four|||one|two||
|+-----+----+|+---+---+|
+------------+---------+
The result above is a list of 2 items, each item being a box.
32.8 Trees with Varying Path-lengths
In the example tree D above all the path-lengths to a leaf
are the same length. However, in general path-lengths may vary.
For the example tree T,
T
+-------+---+--------------+
|the cat|sat|+--+---------+|
| | ||on|+---+---+||
| | || ||the|mat|||
| | || |+---+---+||
| | |+--+---------+|
+-------+---+--------------+
the paths are shown by {:: T and the lengths of the paths
are given by
(# S: 1) {:: T
1 1 2 3 3
Reversing the contents of the level-0 nodes gives no surprises:
|. L: 0 T
+-------+---+--------------+
|tac eht|tas|+--+---------+|
| | ||no|+---+---+||
| | || ||eht|tam|||
| | || |+---+---+||
| | |+--+---------+|
+-------+---+--------------+
but if we reverse contents of the level-1 nodes we see that
some but not all of the level-0 leaves reappear at level 1.
|. L: 1 T
+-------+---+--------------+
|tac eht|tas|+--+---------+|
| | ||no|+---+---+||
| | || ||mat|the|||
| | || |+---+---+||
| | |+--+---------+|
+-------+---+--------------+
The explanation is that at level 1 the given verb is applied to
- those nodes strictly at level 1, that is, those for which 1=L. node AND
- those nodes strictly at level 0 not already accounted for
by being contained within a level 1 node.
Similarly, if we reverse the contents of the level-2 nodes we see:
|. L: 2 T
+-------+---+--------------+
|tac eht|tas|+---------+--+|
| | ||+---+---+|on||
| | |||the|mat|| ||
| | ||+---+---+| ||
| | |+---------+--+|
+-------+---+--------------+
In this example some of the results of reverse are
strings, and some are lists of boxes. They are of different types.
These results of different types cannot simply be assembled without
more ado into a flat list as would be attempted by S:
Hence u S: 1 may fail unless the verb u itself provides uniform results
at every node. Compare these two examples:
|. S: 1 T |
(< @: |.) S: 1 T |
error |
+-------+---+--+---------+
|tac eht|tas|no|+---+---+|
| | | ||mat|the||
| | | |+---+---+|
+-------+---+--+---------+ |
The Level conjunction L: walks the tree in the same way,
that is, it hits the same nodes for reversing,
|. L: 0 T
+-------+---+--------------+
|tac eht|tas|+--+---------+|
| | ||no|+---+---+||
| | || ||eht|tam|||
| | || |+---+---+||
| | |+--+---------+|
+-------+---+--------------+
However, Level does not try to build a flat list of results,
rather puts each individual result back into its position in the tree.
Hence where Spread will fail because it tries to build a flat list,
Level will succeed.
|. S: 1 T |
|. L: 1 T |
error |
+-------+---+--------------+
|tac eht|tas|+--+---------+|
| | ||no|+---+---+||
| | || ||mat|the|||
| | || |+---+---+||
| | |+--+---------+|
+-------+---+--------------+ |
32.9 L. Revisited
Here we show that the LevelOf a tree can be computed from its Map
that is, that L. T, say, can be found from {:: T
{:: T NB. Map giving the paths to leaves
+---+---+-------------------------+
|+-+|+-+|+-----+-----------------+|
||0|||1|||+-+-+|+-------+-------+||
|+-+|+-+|||2|0|||+-+-+-+|+-+-+-+|||
| | ||+-+-+|||2|1|0|||2|1|1||||
| | || ||+-+-+-+|+-+-+-+|||
| | || |+-------+-------+||
| | |+-----+-----------------+|
+---+---+-------------------------+
# S: 1 {:: T NB. the length of each path
1 1 2 3 3
>. / # S: 1 {:: T NB. the maximum of the lengths
3
L. T NB. the LevelOf T
3
This is the end of Chapter 32.
|