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

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?


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.