Note: this wiki is now retired and will no longer be updated!
The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.
SICP exercise 2.27
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))
((3 4) (1 2))
((4 3) (2 1))
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.
((4 3) (2 1))
(define y (list 1 2 (list 3 4))) y
(1 2 (3 4))
((4 3) 2 1)
(define z (list (list 1) (list 2) 3 (list 4))) z
((1) (2) 3 (4))
((4) 3 (2) (1))
(define w (list (list (list 1 2) 3) (list (list (list 4))))) w
(((1 2) 3) (((4))))
((((4))) (3 (2 1)))