SICP exercise 2.27

From Drewiki

Problem

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

Output:

((1 2) (3 4))

(reverse x)

Output:

((3 4) (1 2))

(deep-reverse x)

Output:

((4 3) (2 1))

Solution

Here's the definition of reverse from our answer to exercise 2.18:

(define nil (quote ()))
 
(define (reverse items)
  (if (null? items)
      nil
      (append (reverse (cdr items)) (cons (car items) nil))))

Here's an implementation of deep-reverse:

(define (deep-reverse x)
  (cond ((null? x) nil)
        ((pair? x)
         (append (deep-reverse (cdr x)) (cons (deep-reverse (car x)) nil)))
        (else x)))

Note that when x is a pair, the procedure makes a list of the results of applying deep-reverse to (car x), before applying append. This behavior mirrors that of procedure reverse. append expects its 2nd argument to be a list, but removes the list structure of that argument when forming its result. When (car x) is itself a list, we need to encapsulate it in another list to retain its list structure during the append operation; otherwise, all sublists in the list will be "flattened" into a single list by append, which isn't the behavior we want. Of course, this code also does the right thing when x is not a pair, since in that case deep-reverse simply returns x.

Test:

(deep-reverse x)

Output:

((4 3) (2 1))

(define y (list 1 2 (list 3 4)))
 
y

Output:

(1 2 (3 4))

(deep-reverse y)

Output:

((4 3) 2 1)

 
(define z (list (list 1) (list 2) 3 (list 4)))
 
z

Output:

((1) (2) 3 (4))

(deep-reverse z)

Output:

((4) 3 (2) (1))

(define w (list (list (list 1 2) 3) (list (list (list 4)))))
 
w

Output:

(((1 2) 3) (((4))))

(deep-reverse w)

Output:

((((4))) (3 (2 1)))