Exercise 2.27 of SICP

2009-08-12

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

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

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

(define (deep-reverse x)
  (cond ((null? x) '())
        ((not (pair? x))
         (list x))
        ((not (pair? (car x)))
         (append (deep-reverse (cdr x)) (list (car x))))
        (else
          (append (deep-reverse (cdr x)) 
                  (list (deep-reverse (car x)))))))

> (define x (list (list 1 2) (list 3 4))) 
> (deep-reverse x)
((4 3) (2 1))
> (define y (list (list (list 1 2)) (list 3 4))) 
> y
(((1 2)) (3 4)) 
> (deep-reverse y)
((4 3) ((2 1)))

Contents