Help / Learning / Ch 32: Trees
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help Learning J
|
|
Chapter 32: Trees
32.1 IntroductionData 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 FetchingEvidently, 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 FetchThe 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).
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.
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" VerbMonadic {:: 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
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&{)
and it evidently needs no steps to fetch the content of '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 LevelsConsider the way the text of a book is organized.
We say that chapters, paragraphs, sentences and words are different levels in the organization. The organizing principles are evident :
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 ConjunctionWe 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-lengthsIn 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
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:
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.
32.9 Transforming TreesNext 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 TreeHere 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 RelationA 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:
T -: tfromr R
1
32.9.3 Array from Tree and Tree from ArrayHere 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
)
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
)
Checking for correctness: Z -: T 1 This is the end of Chapter 32. |
The examples in this chapter
were executed using J version 802 beta.
This chapter last updated 25 Aug 2014
Copyright © Roger Stokes 2014.
This material may be freely reproduced,
provided that acknowledgement is made.
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help Learning J