Trees and Indexes
Introduction
It's fairly easy to see how Mathematica expression are trees, and how each atom has an index. This is so until the heads of expressions are expression themselves. For example, the structure of the following expression is difficult to understand:
0[0,0][][0[0,0][],0[0,0][]]
It is however a legal expression, and such forms could be exploited in applications (one simple example is the Derivative function).
In this post, I hope to give a clear exposition of the isomorphism
between Mathematica expressions, trees, and index sets. Once we
understand the isomorphism of expressions and index set with atoms, we
can explain the behavior of any structural manipulating functions in
terms of how the function affects the indexes and atoms. The structural
manipulating functions I had in mind are those covered in The Mathematica Book 2.1 to 2.2
http://reference.wolfram.com/mathematica/book/section-2
We'll just call them tree functions for
abbreviaton.
We will write functions that convert expression to index set and vice versa. To simulate tree functions (For example, Level, Through, Flatten), we can first convert their main arguments to an index set, manipulate the index set, then convert it back into an expression. This approach exposes functions' behaviors, and it shows how they can be implemented in any language. (Our focus is not on implementation, but exploration on useful structural transformations of trees, as exemplified in Mathematica's Outer, Distribute, Transpose…etc.)
Trees and Index set
What is a tree? Trees can be defined formally as a network (graph) without circuits, but we won't need such definition here. Basically: A tree is an abstract idea of a structure. Starting with a node, called root. A node may have other nodes connected to it, called its children. Nodes that have no children are called leaves. If a node is not a leaf, then it is a non-leaf, or called a branching node. (terminology used here may differ from convention) In summary, a tree is a set of nodes, each has a parent/child relation with some other nodes, and by definition there is one node called root, which is the only node without parent.
We can lable the nodes systematically. The root node will be labeled {} (empty braces). If it has two children, then they are labeled {1} and {2}. The children of {1} will be labeled {1,1}, {1,2} and so on. Similarly, children of {2} are {2,1},{2,2}…etc. In general, we add a digit in every new generation, counting children starting at 1. In this way, each node has a name, called its index. The number of digits in an index indicates its “generation ordinal” or Level. The root node is the generation 0, or Level 0, because its index does not contain any digits.
Now notice that we can also use alphabets instead of numbers, or, we can start counting with 0 instead of 1. We will stick to the indexing system that starts counting with 0. This reason for this choice will be apparant later.
A set of indexes defines a tree. The set that contain all indexes of a given tree minus the root index {} will be called the _complete index set_ of that tree. _Leaves index set_ is the set of indexes of all leaves of the tree. Similarly for _Nonleaves index set_ (minus the root {}). The union of leaves and nonleaves is the Complete Index Set. Their intersection is empty.
Examples:
Here's the Complete Index Set of a tree:
{{0},{1},{2},{3},{0,0},{2,0},{2,1},{3,0},{3,1},{3,1,0}}
its LeavesIndexSet is
{{1},{0,0},{2,0},{2,1},{3,0},{3,1,0}}
its NonleavesIndexSet is
{{0},{2},{3},{3,1}}
The MinimumIndexSet is
{{0,0},{2,1},{3,1,0}}
(MinimumIndexSet is the a subset of Complete Index Set: its elements are indexes that can not be inferred from others. Discussed in a previous posting)
A given list of indexes may not be a Complete Index Set, but a complete index set can always be inferred. For example, given {{3},{1},{2,2}}, the {3} implies {2},{1},{0}, and {2,2} implies {2,1},{2,0},{2}. So the Complete Index Set is {{0},{1},{2},{3},{2,0},{2,1},{2,2}}. A list of index implies a Complete Index Set, which in turn defines a tree. Conversely, any tree corresponds to a unique Complete Index Set. Now we have the isomorphism between trees and (complete) index sets.
Lisp Expresions
Now let's look at how a tree shape can be defined as a string (we'll call such string _expression_). The simplest way is using nested parenthesis. We'll use 0 as the atomic object. Starting with root we have 0, which correpsonds to the index set {{}}.
First, notice that there are two types of tree growth: (1) birth of a new generation, for example, {{0},{1}}→{{0},{1},{1,0}}. (2) birth of a sibling, for example, {{0},{1}}→{{0},{1},{2}}.
To grow a new generation, we add a pair of parenthesis. So, we have 0 → (0), corresponding to {{}}→{{},{0}}. To grow a sibling, we append a 0. We have (0)→(0 0), corresponding to {{},{0}}→{{},{0},{1}}. By this growing process, all trees have a corresponding expression, and vice versa. If you are a purest, you can use a pair of empty parenthesis as your atom, so the whole string consists of only parenthesis.
Example: Here's a growth history of the tree {{0},{1},{2},{3},{0,0},{2,0},{2,1},{3,0},{3,1},{3,1,0}}, represented by both expressons and index sets.
{
0,
(0),
(0 0),
(0 0 0),
(0 0 0 0),
((0) 0 0 0),
((0) 0 (0) 0),
((0) 0 (0 0) 0),
((0) 0 (0 0) (0)),
((0) 0 (0 0) (0 0)),
((0) 0 (0 0) (0 (0)))
}
{
{},
{{0}},
{{0},{1}},
{{0},{1},{2}},
{{0},{1},{2},{3}},
{{0,0},{0},{1},{2},{3}},
{{0,0},{0},{1},{2,0},{2},{3}},
{{0,0},{0},{1},{2,0},{2,1},{2},{3}},
{{0,0},{0},{1},{2,0},{2,1},{2},{3,0},{3}},
{{0,0},{0},{1},{2,0},{2,1},{2},{3,0},{3,1},{3}},
{{0,0},{0},{1},{2,0},{2,1},{2},{3,0},{3,1,0},{3,1},{3}}
}
(the empty braces are omitted in index sets. This is so because otherwise an index set ALWAYS contains the {}.)
We'll call the above the Lisp expression system, and it is not the only way to represent a tree shape with strings. In the following system, we'll use brackets instead of parenthesis for visual distinction from the lisp system, and we'll call it the Mathematica expression system.
Mathematica Expresions
In the Mathematica expression system: (1) As before, we start with an atom 0. (2) To grow a new generation, we add a pair of brackets after its parent. So, we have 0 → 0[], corresponding to {{}}→{{},{0}}. (3) To grow a sibling, we append a 0 inside the []. We have 0[]→0[0], corresponding to {{},{0}}→{{},{0},{1}}.
Here is the growth history of the above tree in Mathematica expression:
{
0,
0[],
0[0],
0[0,0],
0[0,0,0],
0[][0,0,0],
0[][0,0[],0],
0[][0,0[0],0],
0[][0,0[0],0[]],
0[][0,0[0],0[0]],
0[][0,0[0],0[0[]]]
}
Commas are used instead of spaces for separaters.
Lisp vs Mathematica expression
Lisp expression system and Mathematica expression system are isomorphic, but expression systems are not isomorphic to trees. There is a one-to-one mapping between the set of all expressions and the set of all trees, but there is NOT a one-to-one mapping between strings in an expression and nodes of its corresponding tree. For example, a tree is a set but an expression is not a set. However, there is a one-to-one mapping between the atoms in an expression to leaves of its corresponding tree. For example, consider the Mathematica expression 1[][2,3[4],5[6[]]]. The atoms correpsonds to the leaves index set {{1},{0,0},{2,0},{2,1},{3,0},{3,1,0}}. This can be seen using the following construct
expr=1[][2,3[4],5[6[]]];
(#->Part[expr,Sequence@@#])&/@Position[expr,_,{-1}]//Sort
returns
{{1} -> 2, {0, 0} -> 1, {2, 0} -> 3, {2, 1} -> 4,
{3, 0} -> 5, {3, 1, 0} -> 6}
In summary, an expressions (lisp or Mathematica) corresponds to tree shapes, and the atoms of an expresion corresponds to the leaves of its corresponding tree.
In lisp form, atoms' indexes are visually apparant. For example, in
((1) 2 (3 4) (5 (6))), 1 must be {0,0}, 2 is {1}, 3 and 4 are {2,0} and
{2,1}, 5 is {3,0}, and 6 is {3,1,0}. In the Mathematica counterpart
1[][2,3[4],5[6[]]], it is less obvious what is the index of 1. In
general, if the first child of any node has children (i.e. if we have
non-atomic heads), then it's difficult to “see” its structure. Here is
a comparison table:
lisp Mathematica
-------------------------
0 0 atom
(0) 0[] appending (sibling birth)
(0 0) 0[0]
(0 0 0) 0[0 0]
((0)) 0[][] nesting (new generation birth)
(((0))) 0[][][]
In the lisp form, any pair of matching parenthesis (…) encloses a subexpression. (subexpression is a continuous partial string that is itself an expression). In the Mathematica counterpart, the form of subexpression is atom[…][…]…[…]. For example, f[][] is a subexpression corresponding to lisp's ((f)).
The structure of lisp expression is more visually apparent. However, Mathematica expression form has its advantages too. For example, sin(x) is more familiar then (sin x). Similarly of f(f(x)) vs. (f (f x)). But I believe there is a more important advantage which we'll discuss below.
Heads→True/False Intepretations
It is desirable to have an expression system such that atoms corresponds to all nodes of a tree, not just the leaves. This is inherently “impossible”, but we can “fake it” by intepreting our expression differently.
Notice that all nonleaves has at least one child: its first child. (e.g. {2,0} is the first child of {2}.) We can pretend that the first child (and all its offspring) of every nonleave is actually the nonleave, and the first child itself does not exist.
Example:
The Complete Index Set for the expression
List[List[f[1,1]],List[f[2,1]]] is
{{0},{1},{2},{1,0},{1,1},{2,0},{2,1},{1,1,0},{1,1,1},
{1,1,2},{2,1,0},{2,1,1},{2,1,2}}
In standard intepretation, the correspondences between leaves and atoms are:
{{0} -> List,
{1, 0} -> List,
{2, 0} -> List,
{1, 1, 0} -> f,
{1, 1, 1} -> 1,
{1, 1, 2} -> 1,
{2, 1, 0} -> f,
{2, 1, 1} -> 2,
{2, 1, 2} -> 1}
The nonleaves {{},{1},{2},{1,1},{2,1}} have no corresponding atoms.
In a "Mathematica intepretation", we have a mapping between all nodes and atoms:
{{} → List,
{1} → List,
{2} → List,
{1, 1} → f,
{1, 1, 1} → 1,
{1, 1, 2} → 1,
{2, 1} → f,
{2, 1, 1} → 2,
{2, 1, 2} → 1}
The following nodes are now considered “non-existant”: {{0},{1,0},{2,0},{1,1,0},{2,1,0}}, because their atoms now “belong” to their parents.
This new intepretation is actually more natural to Mathematica programers. When we see f[1,2…], we think of f[] as a container, and things are stored between its brackets. We don't think of f as the first element of a container even though it IS, as clearly shown in lisp form (f 1 2 …). With the “Mathematica intepretation”, things are dandy because now we have data at all nodes, not just the leaves. This is extremely useful. The price we pay is that when the heads are nested, things quickly become confusing. Compare:
Mathematica form:
1[2][3[4]][5[6][7[8]]]
Lisp form:
(((1 2)(3 4))((5 6)(7 8)))
Complete Index Set:
{{0},{1},{0,0},{0,1},{1,0},{1,1},
{0,0,0},{0,0,1},{0,1,0},{0,1,1},
{1,0,0},{1,0,1},{1,1,0},{1,1,1}}
MinimumIndexSet:
{{0,0,1},{0,1,1},{1,0,1},{1,1,1}}
In the above, the expression's structure is clearly shown by lisp form. However, the structure using the “Mathematica intepretation” is better shown by Mathematica form: the new structure is equivalent to f[ g[ 7[8] ] ], where f is 1[2][3[4]] and g is 5[6]. The dimensions of the expression in standard (lisp) intepretation is {2,2,2}, but in “Mathematica intepretation” it is {1,1,1}, with each 1 corresponding to g, 7, and 8 respectively. (Note: This is not what Dimensions returns. More on that later.)
The two different intepretation of expression is exactly what the Heads→True/False option means in functions that accepts a level spec. When Heads→True, it tell Mathematica to inteprete the expression normally, so that atoms corresponds to leaves only. Heads→False tells Mathematica to regards Heads as parts of the container, not part of the expression.
Here is an analogy: We are familiar with the concept of folders and files. Folders are containers of files. It is extremely convenient for Folders to have names. In the “lisp intepretation”, folders have no names. A folder is a pure basket. You MAY think of the name of a folder as the first thing in its basket. In the “Mathematica intepretation”, a folder has a name, and its name is the first item it contains. Consequently, each folder has one less item. Furthermore, the first item may happen to be a folder, thus the “name” of a folder may be another folder.
Remember that the lisp and Mathematica expression are isomorphic. You can use either one for whatever intepretation. It is in the Mathematica form that makes the Heads→True/False bi-intepretation apparant, and functions can have a Heads option for flexibility. This is what I believe to be an advantage. The disadvantage is that the expression form no longer clearly indicates its structure if heads are non-atomic, and the Heads→True/False is quite confusing. Consequently, I believe it is why we don't see much use of multiple nested heads.
With the above understanding, one may observe some idiosyncrasies of Mathematica. Here are some examples.
Depth of an expression is the max number of digits of indexes of the expression's Complete Index Set, plus 1.
“Plus 1” because the root {} counts as one
level. Now Depth@f[][][] returns 2, but the index of f is {0,0,0}. Of
course, if you read the Appendix, it explains that Depth[expr] is
effectively Depth[expr,Heads->False]. I wish there is a Heads option to
Depth.
Similarly, the Dimensions function is effectiely
Dimensions[expr,Heads->False]. For example, expr=0[0][0[0],0[0]], its
lisp form is ((0 0)(0 0)(0 0)), clearly of dimensions {3,2}. But
Dimensions[expr] does not return {3,2}. Since now Heads are ignored, in
order for Dimensions to be useful, it added one requirement: Dimensions
requires all heads to be the same. Observe:
Dimensions@f[f[0,0]] → {1,2}
Dimensions@f[g[0,0]] → {1}
This is unintuitive because we normally would not think of same structure as having different dimensions. More on Dimension in later posts.
Similarly, the Array function does not grow branches on Heads… and there are others… In general, I think that Mathematica discourages nested heads. I wish the Heads option will be added to more functions in future version to give user the flexibility.
This message is getting way long. We'll come back next week. For now, perhaps some would enjoy writing a LispToMathematica expression (string) converter and vice versa. Solutions will be given next week if more fundamental subjects didn't turn up.