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