SICP Exercise 2.27: Deep Reverse

Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,

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

> x
((1 2) (3 4))

> (reverse x)
((3 4) (1 2))

> (deep-reverse x)
((4 3) (2 1))

Here's the reverse procedure we produced for exercise 2.18:

(define (reverse l)
  (define (iter remaining result)
    (if (null? remaining)
        result
        (iter (cdr remaining) (cons (car remaining) result))))
  (iter l nil))

...and we can indeed confirm its behavior matches that given above:

> (define x (list (list 1 2) (list 3 4)))
> (reverse x)
((3 4) (1 2))

reverse is designed to reverse the ordering of elements in the top-level list. It does not touch the contents of the elements themselves.

To implement deep-reverse we need to reverse the list as we do in reverse, but we also need to identify those elements of the list that are pairs themselves and apply the reversal process to those as well. This means at each iteration we now have three cases instead of two to consider:

• If the remaining list is empty then return the result.
• If the head of remaining is not a pair then put it onto the head of the result list and make the iterative call as before.
• If the head of remaining is a pair then put the result of deep reversing that onto the head of the result list and make the iterative call.

We can translate this into a procedure as follows:

(define (deep-reverse l)
  (define (iter remaining result)
    (cond ((null? remaining) result)
          ((pair? (car remaining))
            (iter (cdr remaining) (cons (deep-reverse (car remaining)) result)))
          (else (iter (cdr remaining) (cons (car remaining) result)))))
  (iter l nil))

...and check it works as expected:

> (deep-reverse x)
((4 3) (2 1))
> (deep-reverse (list (list (list 1 2) (list 3 4) 5) (list 6 (list 7 8) 9) (list 10)))
((10) (9 (8 7) 6) (5 (4 3) (2 1)))

SICP Exercise 2.26: Combining Lists

Suppose we define x and y to be two lists:

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

What result is printed by the interpreter in response to evaluating each of the following expressions:

(append x y)

(cons x y)

(list x y)

Let's fire up our interpreter and find out...

> (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))

In the first case we're using append which takes two lists and produces a new list containing all of the elements from both lists in order.

In the second case we're using cons, which creates a pair using its two arguments. As the second argument is a list the resulting structure will also be a list... and as the first argument is a list the first element of the list will be that list.

In the final case we're using list, which creates a list containing all of its arguments. We have two arguments, both of which are lists, so the resulting structure is a two-element list, each element of which is a list.

SICP Exercise 2.25: Nested cars and cdrs

Give combinations of cars and cdrs that will pick 7 from each of the following lists:

(1 3 (5 7) 9)

((7))

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

We can take this exercise quite literally and just use car and cdr. Let's do that to start with. Then we'll look at using abbreviations for the nested combinations as outlined in footnote 9 in this section.

Let's start at the top then. (list 1 3 (list 5 7) 9) defines a list with 4 elements, the third of which is a list of two elements, the last element of which is 7. First of all we need to get to the third element in the outer list. We know that, when processing lists, car gives us head of the current list and cdr gives us the tail of the current list. Taking the tail of the outer list will give us the three tail elements, of which the second is the one we want, so we need to take the tail of this again to give us the tail two elements, and then take the head to give us the inner list. The inner list has 7 as its second element, so we need to take the tail of this list, which is a single element list (i.e. a pair with a value, 7 in this case, as the first element and nil as the second). So we finally take the head of this list to get to 7.

In practice this is:

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

The second list, (list (list 7)), is a list with a single element which is itself a list with a single element, 7. So to get to 7 we can take the head of the outer list, giving us the inner list, and then take the head of the inner list, to give us 7. In other words:

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

In the case of the third list we have a repeated structure running through it. Starting at the outer list we have a list of two elements: the first is a numeric value and the second is itself a list of the same structure. This nesting of lists through the second element repeats all the way down to the sixth list, where the second element is the value 7 instead of another list. Now to get the second value of a list we need to take the head of the tail of the list (i.e. (car (cdr list))). As the value 7 is the second element of the sixth list in this repeated structure, we can simply repeat this action six times to pick it out:

> (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

All these nested cars and cdrs are pretty ugly though and, as noted in the footnote referenced above, Scheme provides abbreviations for such nesting. The footnote states that "The names of all such procedures start with c and end with r. Each a between them stands for a car operation and each d for a cdr operation, to be applied in the same order in which they appear in the name." However, we can't just change e.g. the last one to (cadadadadadadr <list>). The Scheme standard only requires that interpreters support combinations up to 4 deep. We can still nest those though, and so reduce the levels of nesting greatly:

> (car (cdaddr (list 1 3 (list 5 7) 9)))
7
> (caar (list (list 7)))
7
> (cadadr (cadadr (cadadr (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))))
7