Understanding Deep Reverse

Question

Say I have the list '(1 2 3 (4 5 6) 7 8 9). It should return (9 8 7 (6 5 4) 3 2 1) using the following code below. I'm trying to understand how this iterative process works. Showing how this is done step by step would be very helpful.

The part I get confused the most is when deep-reverse is called twice at this point
(append (deep-reverse (cdr lst)) (list (deep-reverse (car lst)))))

I don't know what happens then.

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

Theo Belaire Theo Belaire · Accepted Answer · 2010-11-05T02:10:36

Well, I just answered something like this here, but I didn't really go into detail on the deep-reverse.

What happens is it reverses each item that happens to be a list before appending it to the end of the list. Imagine what would happen if it didn't call deep-reverse on the car of the list: (reverse '(a (b c d) e) is

(list
   'e
   '(b c d)
   'a
)

With deep-reverse it would look something like

(list
    'e
    (deep-reverse '(b c d))
    'a
)

Which is

(list
    'e
    '(d c b)
    'a
)

Here is another version of deep-reverse, written differently, if that makes it clearer.

(define (deep-reverse ls)
  (define (deep-reverse-2 ls acc)
    (if (null? ls)
        acc
        (if (list? (car ls))
            (deep-reverse-2 (cdr ls) (cons (deep-reverse (car ls)) acc));  If adding  a list, reverse it first
            (deep-reverse-2 (cdr ls) (cons (car ls) acc)))))
  (deep-reverse-2 ls '()))

This version of deep-copy uses an accumulator and is tail recursive.

This checks to see if the element is a list before adding it to the list, and if it is, reverses it first. Since it calls itself to revers the inner list, it can handle arbitrary nesting.

(deep-reverse '(a (b c d) e)) -> '(e (d c b) a)

which is in reverse alphabetical order, despite the fact that there is a nested list. It evaluates as so:

(deep-reverse-2 '(a (b c d) e) '()); Which calls
(deep-reverse-2 '((b c d) e)  '(a)); which is the same as
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(b c d) '()) '(a))); it calls deep-reverse on the list '(b c d) before consing it on.
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(c d)  '(b)) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(d)  '(c b)) '(a)))
(deep-reverse-2 '(e) (cons '(d c b) '(a)))
(deep-reverse-2 '(e)  '((d c b) a))
(deep-reverse-2 '() '(e (d c b) a))
'(e (d c b) a)

Understanding Deep Reverse

2 Answers