SICP Exercise 2.27

2022-01-09

Question

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

Answer

deep-reverse can be defined in a very similar manner to our previous reverse-procedure. The only real difference is that in this scenario, we are reversing car if it is itself a pair. Because this is recursive, it works on lists of any dimension.

(define (deep-reverse l)
  (if (null? l)
      l
      (if (pair? (car l))
          (append (deep-reverse (cdr l)) (list (deep-reverse (car l))))
          (append (deep-reverse (cdr l)) (list (car l))))))

; two-dimensional list
(define x (list (list 1 2) (list 3 4)))

; one-dimensional list
(define y (list 1 2 3 4))

; three-dimensional list
(define z (list (list 1 2) (list 3 (list 4 5))))

(deep-reverse x)
(deep-reverse y)
(deep-reverse z)

Results:

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