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 catsat+++
  on+++
   themat
   +++
  +++
++++
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+++
 themat
 +++
+++
] b =: > 1 { a
+++
themat
+++
] c =: > 1 { b
mat
but there is a builtin 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+++
 themat
 +++
+++
(2 ;1) {:: T
+++
themat
+++
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 fulllength path is a path which fetches
the data content from a leaf.
Along a fulllength 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 catsat+++
  on+++
   themat
   +++
  +++
++++ 
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 fulllength path, giving an overlength 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
++++
+++++++
01++++++
++++20++++++++
  +++210211
   ++++++++
   +++
  +++
++++
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 datacontent 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 indexingandunboxing steps needed.
It is evident that it takes at most 3 steps to fetch any datacontent from T
T 
L.T 
++++
the catsat+++
  on+++
   themat
   +++
  +++
++++ 
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')
+++
++++++
onetwothreefour
++++++
+++
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 level0 node, that is, each leaf:
. L: 0 D
+++
++++++
enoowteerhtruof
++++++
+++
Reversing at level 1:
. L: 1 D
+++
++++++
twoonefourthree
++++++
+++
and at level 2:
. L: 2 D
+++
++++++
threefouronetwo
++++++
+++
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
+++
++++++
enoowteerhtruof
++++++
+++
. L: _1 D
+++
++++++
twoonefourthree
++++++
+++
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
treestructure 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
+++
++++++
onetwothreefour
++++++
+++
. 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 
+++
fourthree
+++
The result above is a list of 2 items, each item being a list of 2 boxes.
. S: 2 D
+++
++++++
threefouronetwo
++++++
+++
The result above is a list of 2 items, each item being a box.
32.8 Trees with Varying Pathlengths
In the example tree D above all the pathlengths to a leaf
are the same length. However, in general pathlengths may vary.
For the example tree T,
T
++++
the catsat+++
  on+++
   themat
   +++
  +++
++++
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 level0 nodes gives no surprises:
. L: 0 T
++++
tac ehttas+++
  no+++
   ehttam
   +++
  +++
++++
but if we reverse contents of the level1 nodes we see that
some but not all of the level0 leaves reappear at level 1.
. L: 1 T
++++
tac ehttas+++
  no+++
   matthe
   +++
  +++
++++
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 level2 nodes we see:
. L: 2 T
++++
tac ehttas+++
  +++on
  themat 
  +++ 
  +++
++++
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 ehttasno+++
   matthe
   +++
+++++ 
The Level conjunction L: walks the tree in the same way,
that is, it hits the same nodes for reversing,
. L: 0 T
++++
tac ehttas+++
  no+++
   ehttam
   +++
  +++
++++
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 ehttas+++
  no+++
   matthe
   +++
  +++
++++ 
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
++++
+++++++
01++++++
++++20++++++++
  +++210211
   ++++++++
   +++
  +++
++++
# 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.
