# Producing a deep-reverse procedure

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?

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(n²), 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))