Help / Learning / Ch 32: Trees

From J Wiki
Jump to navigation Jump to search


>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help Learning J


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 :

  1. there are a small number of levels.
  2. the number of levels is fixed in advance.
  3. 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.


NEXT
Table of Contents
Index


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