Defining a tree structure in Lisp

Question

From the general Lisp HyperSpec dictionary:

tree n. 1. A binary recursive data structure consisting of conses and atoms: consus themselves are trees (sometimes called "subtrees" or "branches"), and atoms are the final nodes (sometimes called leaves). Typically, leaves represent data, and branches establish some relationship between this data. 2. in general, any recursive data structure that has some concept of "branches" and leaves.

tree structure . (from wood) the many conses that make up the tree. Note that although the component [1b] of the car of each such minus is part of the tree structure, objects that are the cars of each minus in the tree themselves are not part of their tree structure, unless they are also conses.

The last sentence in the definition of the tree structure raises the question, which, perhaps, can be said about cdrs?

Using the word binary in the definition of "tree" seems to indicate that there is no difference between car vs cdr for tree purposes, but then the definition of "tree structure" seems to refer to special cars, so I'm confused .

Answer 1

Short answer

The last sentence in the definition of the tree structure raises the question, which can also be said of cdrs?

I think the answer is yes. There is a similar definition of the list structure with almost the same wording. There is more room for confusion in the structure of the list about whether the value of the minus car is part of the structure of the list, as questions may arise, for example: "what does it mean to replace X in the list (X (X) Y)?" Cdr is not much in doubt, since cdr is the rest of the list; this is obviously part of the list structure.

For the tree structure, I find there is less ambiguity; cons in a car or cdr - subtree. The definitions of the tree structure and the structure of the list are almost identical in their places, and I would not be surprised if someone wrote a definition of the structure of the list and then copied it for the tree structure, making the minimum number of changes necessary for an accurate one. This would leave a little about the cars there, although the question he answers is likely not to arise in practice.

Longer answer

Look at the definition of the list structure and compare:

. (list) the set of requirements that make up the list. Note that although the automotive component of each of these minuses is part of the list structure, objects that are elements of the list (i.e. objects that are cars of every minus in the list) are not themselves part of their list structure, even if they are conses, except in the (circular) case where the list actually contains one of its tails as an element. (A list structure list is sometimes redundantly referred to as a "top-level list structure" for sequencing to emphasize that any conses that are list items are not involved.)

Pay attention to the places where they differ:

(list structure). Note that although the car component of each such minus is part of the list structure, objects that are elements of the list (i.e. objects that are cars of every minus in the list) are not themselves part of their list structure, even if they are conses .

(tree structure). Note that although the automotive component of each such minus is part of a tree structure, objects that are cars of each minus in a tree themselves are not part of their tree structure, unless they are also conses.

This means that in

(1 (2) 3) == (cons 1 (cons (cons 2 nil) (cons 3 nil))) 

there are three cons cells and four cons cells in the tree structure in the list structure.

Where does it really matter? It is important to define these terms so that the specification can easily determine which parts of the list or tree are traversed or changed by specific functions.

nsubst can change tree structure

For example, nsubst functions and friends whose documentation reads:

nsubst, nsubst-if and nsubst-if-not can change the tree structure of the tree.

A specific definition of the tree structure allows us to understand what can and cannot be changed with nsubst .

tree structure . (from wood) the many conses that make up the tree. Please note that although the automotive component of each of these minuses is part of a tree structure, objects that are cars of each minus in a tree themselves are not part of their tree structure, unless they are also conses.

So what this tells us is that for any cons cell x in the tree nsubst can do (setf (car x) ...) so that (car x) might be something else later, but it will not change the actual the object to be returned (car x) (unless that means the course). This can be important in cases where the value (car x) is an object in which trees can be. So, for example, nsubst will not go into vectors, but it will replace vectors:

 (let* ((l (list 1 2 3)) ; a list (v (vector 0 l 4)) ; a vector that contains the list (and other elements) (tree (cons lv))) ; a tree containing the list and the vector (nsubst 'xl tree)) ; replace the list in the tree with X ;=> (X . #(0 (1 2 3) 4)) ; nsubst doesn't descend into the vector, because it's ; not tree structure 

delete-duplicates can change the list structure

On the other hand, delete-duplicates only modifies the list structure:

delete-duplicates, when a sequence is a list, it is allowed to set any part, car or cdr, of the top-level list structure in that sequence. When the sequence is a vector, duplicates are allowed to resize the vector and slide its elements to new positions without rearranging them to create the resulting vector.

Answer 2

Note that although the component [1b] of the car of each such minus is part of the tree structure, objects that are the cars of each minus in the tree themselves are not part of their tree structure, unless they are also conses.

As far as I can see, the author of this definition is trying to draw a line between the structure of the tree itself and its objects. Thus, he argues that only conses can make up a tree structure.

Consider the following example:

 (1 2 (3 "string") 4) 

As long as the "string" object is part of the tree (and this is car of ("string") ), it is not part of the tree structure, because the strings are not composed of cons cells.

I believe that the author of the definition had in mind the correct lists, because for them every element of car :

 (cons "foo" (cons "bar" (cons "baz" nil))) ; ^car^ ^car^ ^car^ 

cdr rather defines the structure of the tree if the list is correct.

But you can also consider the following as a tree:

 ("foo" . "bar") 

In this case, cdr will not be part of the tree structure.