understanding the tree in SICP - exercise 2.24

Question

Exercise 2.24: Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in Figure 2.6).

The problem is my eyes are destroyed, therefore I can see neither the box and pointer diagram nor Figure 2.6. So now I only have a guess on what this list should look like as a tree based on:

Another way to think of sequences whose elements are sequences is as trees. The elements of the sequence are the branches of the tree, and elements that are themselves sequences are subtrees.

Please check my tree interpretation. This is just my imagination. I'm pretty confident this is correct, but have no way of confirming it because all of the answers to the exercise I found are pictures and my screen reader can't read them.

(list 1 (list 2 (list 3 4))) - I think this is the tree itself, or the rootnode. This tree has two branches or children.
The first branch (1) is a leaf node, so we are done at this side of the tree.
The second branch (list 2 (list 3 4) is another tree.
Now we focus on the subtree (list 2 (list 3 4). It has two children/branches.
The first branch is a leafnode (2), so we're done here.
The second branch is another tree (list 3 4).
Now we focus on the subtree (list 3 4). It has two children branches.
They are both leafnodes, so we're done.

Is this correct? Did I interpret the tree right?

Will Ness Will Ness · Accepted Answer · 2016-01-07T03:27:28

The real list-building primitive in Lisp is cons. A list which is the result of evaluating the form (list 1 2 3) is the same as the result of evaluating (cons 1 (cons 2 (cons 3 '()))), and can also be written '(1 2 3 . ()), or in its fully dotted form, '(1 . (2 . (3 . ()))).

All these will be printed as (1 2 3) by the interpreter:

(list 1 2 3)                       '(1 2 3)                ;  (1 2 3)
(cons 1 (list 2 3))                '(1 . (2 3))            ;  (1 2 3)
(cons 1 (cons 2 (list 3)))         '(1 . (2 . (3)))        ;  (1 2 3)
(cons 1 (cons 2 (cons 3 '())))     '(1 . (2 . (3 . ())))   ;  (1 2 3)

Viewed as a tree, (1 2 3) has three branches - all are leaf nodes: the 1, the 2 and the 3. On the other hand, (1 (2 3)) has two branches - a leaf and a tree of two leaf nodes. And ((1 2) 3) also has two branches - a tree of two leaf branches, and a leaf branch.

As boxes-and-pointers structure, the dots symbolize the cons cells (i.e. boxes), each with its two slots, or pointers - the car (to the left of the dot) and the cdr (to the right of the dot).

Thus, the result of evaluating (list 1 (list 2 3)) , which is printed as (1 (2 3)), is also constructed by the call (cons 1 (cons (cons 2 (cons 3 '())) '())); so as a box-and-pointer structure it is really '(1 . ( (2 . (3 . ())) . () )). Its car is 1, and its cdr is the box ( (2 . (3 . ())) . () ) whose cdr is () and its car - the box (2 . (3 . ())); etc.

Lists with () in their last box's cdr are known as "proper lists". Any others are called "improper lists", e.g.

'(1 2 . 3) 
= '(1 . (2 . 3))
= (cons 1 (cons 2 3))

understanding the tree in SICP - exercise 2.24

2 Answers