Producing a deep-reverse procedure

Question

Exercise 2.27

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

I wrote the following:

(define (deep-reverse lis)
 (define (snoc elem lis)
 (if (null? lis) 
 (cons elem lis)
 (cons (car lis) (snoc elem (cdr lis)))))
 (cond ((null? lis) lis)
 ((pair? (car lis)) (snoc (deep-reverse (car lis)) (deep-reverse (cdr lis))))
 (else (snoc (car lis) (deep-reverse (cdr lis))))))
(define a (list 1 2 3 4 5 (list 1 2 3 4) (list 5 6 7 8)))

What do you think?

Answer 1

The main problem with using snoc (or append, which your snoc effectively does) is that each call is O(n). This makes your function O(n2), which is (pun intended) deeply problematic.

Here's my O(n) implementation, which is tail-recursive along the cdrs:

(define (deep-reverse l)
 (let loop ((x l)
 (r '()))
 (cond ((null? x) r) 
 ((pair? x) (loop (cdr x) (cons (deep-reverse (car x)) r)))
 (else x))))

Here's an even shorter version, using fold (also tail-recursive along the cdrs):

(define (deep-reverse l)
 (define (iter x y)
 (cons (if (pair? x) (deep-reverse x) x) y))
 (fold iter '() l))

For even more fun, an unfold-right version (also tail-recursive along the cdrs); requires compose as well:

(define (deep-reverse l)
 (define (iter x)
 (if (pair? x) (deep-reverse x) x))
 (unfold-right null? (compose iter car) cdr l))