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 |
Here we see 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
32.6 Levels
Consider the way the text of a book is organized.
- a book is a sequence of chapters. Different books may have different numbers of chapters.
- a chapter is a sequence of paragraphs. Different chapters may have different number of paragraphs.
- a paragraph is a sequence of sentences. Different paragraphs may have different numbers of sentences
- a sentence is a sequence of words. Different sentences may have different numbers of words.
We say that chapters, paragraphs, sentences and words are different levels in the organization. The organizing principles are evident :
- there are a small number of levels.
- the number of levels is fixed in advance.
- the path to every leaf is of the same length.
J provides several built-in functions which are particularly useful in handling trees organized into fixed levels in this way..
Here is an example of such a tree:
] D =: (<'one'; 'two'), (< 'three' ; 'four')
+---------+------------+
|+---+---+|+-----+----+|
||one|two|||three|four||
|+---+---+|+-----+----+|
+---------+------------+
A box with no inner box (a leaf) is said to be at level 0.
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 leaves
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 Transforming Trees
Next we look at transformations between trees, relations and arrays.
The motivation for these transforms is that, by turning structure
into data, some operations become more straightforward. For example
adding or removing branches (grafting or pruning) becomes easier.
Throughout this section it will be assumed that
the trees in question
have the property of a fixed number of levels,
and the same path-length to every leaf.
Here is a tree for a starting point.
p1 =: (< 'aa' ;'bb' ; 'cc'), (< 'dd' ; 'ee' )
p2 =: (,< ( 'ff' ; 'gg'))
] T =: (< p1) , (< p2) NB. a tree
+--------------------+---------+
|+----------+-------+|+-------+|
||+--+--+--+|+--+--+|||+--+--+||
|||aa|bb|cc|||dd|ee|||||ff|gg|||
||+--+--+--+|+--+--+|||+--+--+||
|+----------+-------+|+-------+|
+--------------------+---------+
32.9.1 Relation from Tree
Here is a function to make a relation from a tree. It combines the index-matrix,
that is the set of all paths to leaves,
with the data values of corresponding leaves:
rfromt =: 3 : 0
P =. indmat y NB. index-matrix
V =. dava y NB. the value of each word
(<"1 P) (, "0 0) V NB. relation
)
indmat =: 3 : 0 NB. index-matrix of given tree
(; @: >) S: 1 ({:: y)
)
dava =: < S: 0 NB. data-values from leaves
We see that each row relates the path to a leaf
and the data content of that leaf.
T
+--------------------+---------+
|+----------+-------+|+-------+|
||+--+--+--+|+--+--+|||+--+--+||
|||aa|bb|cc|||dd|ee|||||ff|gg|||
||+--+--+--+|+--+--+|||+--+--+||
|+----------+-------+|+-------+|
+--------------------+---------+
] R =: rfromt T
+-----+--+
|0 0 0|aa|
+-----+--+
|0 0 1|bb|
+-----+--+
|0 0 2|cc|
+-----+--+
|0 1 0|dd|
+-----+--+
|0 1 1|ee|
+-----+--+
|1 0 0|ff|
+-----+--+
|1 0 1|gg|
+-----+--+
32.9.2 Tree from Relation
A function to make a tree from a relation:
tfromr =: 3 : 0
while. (1 < # >{. {. y) do. y =. step y end.
1 { "1 y
)
where
step =: 3 : 0 NB. one step of tree-from-relation
k =. rkeys y
v =. k < /. (1 { "1 y)
(~.k) ,. v
)
rkeys =: (}: &. >) @: ({. " 1) NB. reduced-length keys
Each step of the process reduces the path-lengths by 1:
| R |
step R |
+-----+--+
|0 0 0|aa|
+-----+--+
|0 0 1|bb|
+-----+--+
|0 0 2|cc|
+-----+--+
|0 1 0|dd|
+-----+--+
|0 1 1|ee|
+-----+--+
|1 0 0|ff|
+-----+--+
|1 0 1|gg|
+-----+--+ |
+---+----------+
|0 0|+--+--+--+|
| ||aa|bb|cc||
| |+--+--+--+|
+---+----------+
|0 1|+--+--+ |
| ||dd|ee| |
| |+--+--+ |
+---+----------+
|1 0|+--+--+ |
| ||ff|gg| |
| |+--+--+ |
+---+----------+ |
| step step R |
tfromr R |
+-+--------------------+
|0|+----------+-------+|
| ||+--+--+--+|+--+--+||
| |||aa|bb|cc|||dd|ee|||
| ||+--+--+--+|+--+--+||
| |+----------+-------+|
+-+--------------------+
|1|+-------+ |
| ||+--+--+| |
| |||ff|gg|| |
| ||+--+--+| |
| |+-------+ |
+-+--------------------+ |
+--------------------+---------+
|+----------+-------+|+-------+|
||+--+--+--+|+--+--+|||+--+--+||
|||aa|bb|cc|||dd|ee|||||ff|gg|||
||+--+--+--+|+--+--+|||+--+--+||
|+----------+-------+|+-------+|
+--------------------+---------+ |
T -: tfromr R
1
32.9.3 Array from Tree and Tree from Array
Here is a verb to construct an array from a tree.
It is assumed that the result is to be an array of boxes,
and so empty boxes may be needed for paddding.
afromt =: 3 : 0 NB. array from tree
a =. indmat y
b =. 1+ >./ a NB. dimensions of array
c =. b $ a: NB. recipient array
d =. dava T
e =. < @: ( ;/) "1 a NB. indices
d e } c
)
| T |
A =: afromt T |
+--------------------+---------+
|+----------+-------+|+-------+|
||+--+--+--+|+--+--+|||+--+--+||
|||aa|bb|cc|||dd|ee|||||ff|gg|||
||+--+--+--+|+--+--+|||+--+--+||
|+----------+-------+|+-------+|
+--------------------+---------+ |
+--+--+--+
|aa|bb|cc|
+--+--+--+
|dd|ee| |
+--+--+--+
+--+--+--+
|ff|gg| |
+--+--+--+
| | | |
+--+--+--+ |
The converse function is to build a tree from an array,
assuming that all empty boxes are padding to be discarded.
First we convert the given array to its
indexmatrix-value relation
and then convert the relation to a tree with tfromr.
tfroma =: 3 : 0 NB. tree from array
b =. , y NB. units of data content
c =. (#: i. @ (*/)) $ y NB. index-matrix
d =. -. b -:"0 a:
e =. (<"1 c) ,. b NB. a relation
f =. d # e NB. discarding empty boxes
tfromr f
)
| A |
Z =: tfroma A |
+--+--+--+
|aa|bb|cc|
+--+--+--+
|dd|ee| |
+--+--+--+
+--+--+--+
|ff|gg| |
+--+--+--+
| | | |
+--+--+--+ |
+--------------------+---------+
|+----------+-------+|+-------+|
||+--+--+--+|+--+--+|||+--+--+||
|||aa|bb|cc|||dd|ee|||||ff|gg|||
||+--+--+--+|+--+--+|||+--+--+||
|+----------+-------+|+-------+|
+--------------------+---------+ |
Checking for correctness:
Z -: T
1
This is the end of Chapter 32.
|