sicp-ex-2.27

  
 ;; A value for testing. 
 (define x (list (list 1 2) (list 3 (list 4 5)))) 
  
 ;; My environment doesn't have nil. 
 (define nil '()) 
  
  
 ;; Here's reverse for reference: 
 (define (reverse items) 
   (define (rev-imp items result) 
     (if (null? items) 
         result 
         (rev-imp (cdr items) (cons (car items) result)))) 
   (rev-imp items nil)) 
  
 ;; Usage: 
 (reverse x) 
  
  
 ;; Deep reverse.  Same as reverse, but when adding the car to the 
 ;; result, need to check if the car is a list.  If so, deep reverse 
 ;; it. 
  
 ;; First try: 
 (define (deep-reverse items) 
   (define (deep-rev-imp items result) 
     (if (null? items) 
         result 
         (let ((first (car items))) 
           (deep-rev-imp (cdr items) 
                    (cons (if (not (pair? first)) 
                              first 
                              (deep-reverse first)) 
                          result))))) 
   (deep-rev-imp items nil)) 
  
 ;; Usage: 
 (deep-reverse x) 
  
  
 ;; Works, but it's a bit hard to read?  Refactoring: 
  
 (define (deep-reverse-2 items) 
   (define (deep-rev-if-required item) 
     (if (not (pair? item)) 
         item 
         (deep-reverse-2 item))) 
   (define (deep-rev-imp items result) 
     (if (null? items) 
         result 
         (deep-rev-imp (cdr items) 
                       (cons (deep-rev-if-required (car items)) 
                             result)))) 
   (deep-rev-imp items nil)) 
  
 ;; Usage: 
 (deep-reverse-2 x) 
  

Here's Eli Bendersky's code, translated into Scheme. It's pretty sharp, and better than my own since it's more concise:

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

This works for me:

 (define (reverse x) 
   (if (pair? x) 
       (append (reverse (cdr x))  
               (list (reverse (car x)))) 
       x)) 

Another solution without append

  
 (define (deep-reverse items) 
   (define (iter items result) 
     (if (null? items) 
         result 
         (if (pair? (car items)) 
             (let ((x (iter (car items) ()))) 
               (iter (cdr items) (cons x result))) 
             (iter (cdr items) (cons (car items) result))))) 
   (iter items ())) 
  

Solution that is a simple modification of reverse

  
 (define (deep-reverse tree) 
   (define (iter t result) 
     (cond ((null? t) result) 
           ((not (pair? (car t))) 
            (iter (cdr t) (cons (car t) result))) 
           (else  
            (iter (cdr t) (cons (deep-reverse (car t)) result))))) 
   (iter tree '())) 
  
 #| 
 > (deep-reverse '((1 2) (3 4))) 
 '((4 3) (2 1)) 
 > (deep-reverse '(1 2 (3 4) 5 (6 (7 8) 9) 10)) 
 '(10 (9 (8 7) 6) 5 (4 3) 2 1) 
 >  
 |# 
 >>> 

there is another solution. it may be simpler.

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

Took me a while to implement it without append and reverse.

 (define (deep-reverse L) 
   (define (rev L R) 
     (cond ((null? L) R) 
           ((not (pair? (car L))) (rev (cdr L) 
                                       (cons (car L) R))) 
           (else (rev (cdr L)  
                      (cons (rev (car L) '()) 
                                    R))))) 
   (rev L '())) 
  
 (define x '((1 2) (3 4))) 
 (deep-reverse x) ;; ((4 3) (2 1))