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)))
x
((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)
list2
(cons (car list1) (append (cdr list1) list2))))
(define (reverse items)
(if (null? items)
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)))))
(else
(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))
Related:
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.
6 comments:
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. :-)
Chris,
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.
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 []))
My solution
(define (deep-reverse items)
(define (iter a acc)
(if (null? a)
acc
(iter (cdr a)
(cons (if (pair? (car a))
(deep-reverse (car a))
(car a))
acc))))
(iter items nil))
(define (deep-reverse items)
(cond
((null? items) (list ))
((not (pair? items)) items)
(else (map deep-reverse (reverse items)))
)
)
```//In JavaScript
function deep_reverse(ls) {
return is_null(ls)
? ls
: ! is_pair(head(ls))
? append(deep_reverse(tail(ls)), list(head(ls)))
: append(deep_reverse(tail(ls)), list(deep_reverse(head(ls))));```
Post a Comment