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