SICP 2.24 - 2.26: Hierarchical Structure Basics

From SICP section 2.2.2 Hierarchical Structures

Section 2.2.2 introduces more complex data structures than the simple lists we've been working with so far. We now start to build lists whose elements are themselves lists. By doing so we create hierarchical data structures. The first few exercises in this section illustrate the basics.

Exercise 2.24 asks us to evaluate the expression (list 1 (list 2 (list 3 4))). We're to show the result printed by the interpreter, the corresponding box-and-pointer-structure, and an interpretation of the resulting structure as a tree.

The expression evaluates as follows:

> (list 1 (list 2 (list 3 4)))
(1 (2 (3 4)))

In somewhat plain English, this is a list whose first element is the number 1 and whose second element is another list. That list has the number 2 as its first element and another list as its second element. This final list has as its elements the numbers 3 and 4.

Here are the box-and-pointer and tree representations of the same structure.







Exercise 2.25 asks us to use combinations of car and cdr to pick the number 7 from each of the following structures:

(1 3 (5 7) 9)

((7))

(1 (2 (3 (4 (5 (6 7))))))

The first thing we should do is figure out how to write an expression that will produce each of these structures. After a little bit of experimentation, we come up with the following:

> (list 1 3 (list 5 7) 9)
(1 3 (5 7) 9)

> (list (list 7))
((7))

> (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7))))))
(1 (2 (3 (4 (5 (6 7))))))

Now that we know how each structure is created, we can experiment with car and cdr to see how we break these structures down.

(1 (2 (3 (4 (5 (6 7))))))
> (car (list 1 3 (list 5 7) 9))
1
> (cdr (list 1 3 (list 5 7) 9))
(3 (5 7) 9)

A bit more probing along these lines reveals the answer for the first structure.

> (cdr (cdr (list 1 3 (list 5 7) 9)))
((5 7) 9)
> (car (cdr (cdr (list 1 3 (list 5 7) 9))))
(5 7)
> (cdr (car (cdr (cdr (list 1 3 (list 5 7) 9)))))
(7)
> (car (cdr (car (cdr (cdr (list 1 3 (list 5 7) 9))))))
7

If that last step is confusing, just remember that list gives us a sequence of pairs formed by nested calls to cons, so (list 5 7) is equivalent to (cons 5 (cons 7 null)). We need to use car to get the first value from the pair returned in the next-to-last step.

The second structure is rather straightforward and so is its solution.

> (car (car (list (list 7))))
7

The last solution is similar to the first, but a little bit more complicated. Here's the solution:

> (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr
    (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7))))))))))))))))))
7

If you were expecting to be able to simply "cdr-down" this structure without all those calls to car, once again, remember that list returns a sequence of pairs. We have to use car to extract the inner list returned by cdr at each step.

> (cdr (list 5 (list 6 7)))
((6 7))
> (car (cdr (list 5 (list 6 7))))
(6 7)

Exercise 2.26 simply asks us to consider the following two lists:

(define x (list 1 2 3))
(define y (list 4 5 6))

We're then asked what is printed in the interpreter in response to evaluating each of the following expressions:

(append x y)

(cons x y)

(list x y)

These are the three procedures for combining expressions that we've learned. Analyzing the results of each function will allow us to review how they differ from each other.

> (define x (list 1 2 3))
> (define y (list 4 5 6))

> (append x y)
(1 2 3 4 5 6)
> (cons x y)
((1 2 3) 4 5 6)
> (list x y)
((1 2 3) (4 5 6))

The append procedure takes the elements from two lists and produces a new list. When given two lists as parameters, the cons procedure returns a list whose first element is the first parameter list and whose remaining elements are the elements of the second list (we saw this at the beginning of section 2.2.1 Representing Sequences). Finally the list procedure simply wraps its parameters in a new list without doing any merge or append operations on them. The returned list just has two lists as its elements.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.