Saturday, January 29, 2011

SICP 2.27: Reversing Nested Lists

From SICP section 2.2.2 Hierarchical Structures

Exercise 2.27 asks us to modify our reverse procedure from exercise 2.18 to create a deep-reverse procedure that takes a list as its argument and returns the list with its elements reversed and with all sub-lists reversed as well. For example,
(define x (list (list 1 2) (list 3 4)))

((1 2) (3 4))

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

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

Recall that the solution to exercise 2.18 was to reverse a list by appending the car of the list to the reverse of the cdr of the list.
(define (append list1 list2)
(if (null? list1)
(cons (car list1) (append (cdr list1) list2))))

(define (reverse items)
(if (null? items)
(append (reverse (cdr items)) (list (car items)))))

We need to do something similar here, but we also need to check to see if each element in the list is a list itself, and reverse it if it is. Since lists can be nested as many levels deep as we want, we'll need to make recursive calls to deep-reverse to handle any depth.
(define (deep-reverse items)
(cond ((null? items) null)
((pair? (car items))
(append (deep-reverse (cdr items))
(list (deep-reverse (car items)))))
(append (deep-reverse (cdr items))
(list (car items))))))

This solution still follows the same basic idea of reverse. We're still appending the car of the list to the reverse of its cdr, but now we first check to see if the car of the list is a pair. If the car is a pair we need to reverse it as well by passing it through deep-reverse. If not, we only need to deep-reverse the cdr.
> (define x (list (list 1 2) (list 3 4)))
> (reverse x)
((3 4) (1 2))
> (deep-reverse x)
((4 3) (2 1))

That test is fine if the nesting is only one level deep, but we should also test our code for lists nested at least one level deeper.
> (define y (list (list 1 2) (list (list 3 4) (list 5 6 7))))
> y
((1 2) ((3 4) (5 6 7)))
> (deep-reverse y)
(((7 6 5) (4 3)) (2 1))


For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.


Chris K. Jester-Young said...

I always aim to write iterative (tail-recursive) solutions, when possible. In this case, my iterative solution is even simpler than the recursive solution.

After you've done all the exercises, you might decide you'd like to rewrite everything in iterative form, too. It's a totally different way of looking at programming. :-)

Bill the Lizard said...


I usually do try both iterative and recursive solutions unless one or the other jumps out at me as fitting the problem better. I had attempted an iterative solution on this problem too. I got it to work, but your solution is much more concise than the one I came up with.

kapitan said...

My solution is similar, but avoids tree-recursion...I am not sure it is correct though, looking at yours.

(defn deep-reverse [a]
(defn helper [a new-a]
(let [car (u/car a)
cdr (u/cdr a)])
(cond (empty? a) new-a
(u/pair? car) (helper cdr (cons (helper car []) new-a))
:else (helper cdr (cons car new-a))))
(helper a []))