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 (deep-reverse x) 
   (if (pair? x) 
       (append (deep-reverse (cdr x))  
               (list (deep-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)) 
  

Solution with no use of append. Would be nice to have a full iterative process, but this problem is naturally recursive.

  
 (define (deep-reverse l)   
   (define (update-result result picked) 
     (cons (if (pair? picked) (deep-reverse picked) picked) ;; recursive process 
           result))   
    
   (define (iter source result) 
     (if (null? source) 
         result 
         (iter (cdr source) (update-result result (car source))))) 
    
   (iter l '())) 
  
  
 ;; testing 
 (deep-reverse '(1 2 (a b c (d1 d2 d3)) 4)) ;; returns '(4 ((d3 d2 d1) c b a) 2 1) 
  

My solution which is very similar to the original.

  
 (define (deep-reverse items) 
   (define (try-deep item) 
     (if (not (list? item)) 
         item 
         (iter item '()))) 
  
   (define (iter old new) 
     (if (null? old) 
         new 
         (iter (cdr old) 
               (cons (try-deep (car old)) new)))) 
  
   (iter items '())) 
  
 ;; Testing 
 (define x (list (list 1 2) (list 3 (list 4 5)) (list (list 2 3) 3))) 
 ;; ((1 2) (3 (4 5)) ((2 3) 3)) 
 (deep-reverse x) 
 ;; ((3 (3 2)) ((5 4) 3) (2 1)) 
  

I though I'll found my version. Very close to some version here tough, but using map for clarity. It looks like it is working. May I be wrong somewhere?

 (define (deep-reverse tree) 
   (cond ((null? tree) nil) 
         ((not (pair? tree)) tree) 
         (else (map deep-reverse (reverse tree))))) 
  
 (display (deep-reverse (list (list 1 2) (list 3 4))))  
 (newline) 
 (display (deep-reverse (list (list 1 (list 5 6)) (list 3 4)))) 
 (newline) 

The most briefly solution

This solution only works with list of lists

 (define (deep-reverse l) 
 (reverse (map reverse l))) 

This solution doesn't require to check for the end of list.

 (define (deep-reverse lst) 
         (if (not (pair? lst)) 
             lst 
             (append (deep-reverse (cdr lst)) 
                     (list (deep-reverse (car lst)))))) 
  
 ;;Testing 
 (define x (list (list 1 2) (list 3 (list 4 (list 5 6 7) (list 8 9 10) 11)))) 
 (deep-reverse (deep-reverse x)) 
 ;; ((1 2) (3 (4 (5 6 7) (8 9 10) 11))) 

  
 (define (reverse item) 
   (define (reverse-iter item result) 
     (if (null? item) 
         result 
         (reverse-iter (cdr item) (cons (car item) result)))) 
   (reverse-iter item nil)) 
  
 (define (deep-reverse item) 
   (define (deep-reverse-iter item result) 
     (cond ((null? item) result) 
           ((pair? (car item)) (deep-reverse-iter (cdr item) (cons (deep-reverse (car item)) result))) 
           (else (deep-reverse-iter (cdr item) (cons (car item) result))))) 
   (deep-reverse-iter item nil)) 
  
 ;;Testing 
 > (define x (list (list 1 2) (list 3 4))) 
 > x 
 (mcons (mcons 1 (mcons 2 '())) (mcons (mcons 3 (mcons 4 '())) '())) 
 > (reverse x) 
 (mcons (mcons 3 (mcons 4 '())) (mcons (mcons 1 (mcons 2 '())) '())) 
 > (deep-reverse x) 
 (mcons (mcons 4 (mcons 3 '())) (mcons (mcons 2 (mcons 1 '())) '())) 
 > (deep-reverse (list 1 2 3)) 
 (mcons 3 (mcons 2 (mcons 1 '()))) 
 > (deep-reverse (list (list 1 2 3))) 
 (mcons (mcons 3 (mcons 2 (mcons 1 '()))) '()) 

My first try: this is the same solution as joshwarrior's, except that the last two of cond's operands are reversed.

  
 (define (deep-reverse l) 
   (define (rev l res) 
     (cond ((null? l) res) 
           ((not (pair? (car l))) (rev (cdr l) 
                                       (cons (car l) 
                                             res))) 
           (else (rev (cdr l) 
                      (cons (rev (car l) 
                                 '()) 
                            res))))) 
   (rev l '())) 

Then I realized that car'ing before pair? was unnecessary, and here's my final answer.

  
 (define (deep-reverse l) 
   (define (rev l res) 
     (cond ((null? l) res) 
           ((not (pair? l)) l) 
           (else (rev (cdr l) 
                      (cons (rev (car l) 
                                 '()) 
                            res))))) 
   (rev l '())) 

I think this is better in terms of simplicity. This solution is also efficient because it does not use append or any operation that travels down the intermediate list from its head every time the function is called.

I think the solution can be much shorter by using map and list?.

  
 (define (deep-reverse x) 
   (if (list? x) 
       (reverse (map deep-reverse x)) 
       x)) 

This method is a very slight and (in my opinion) intuitive alteration of the reverse procedure. Instead of cons'ing the car of z to result (as in the original reverse procedure), the reverse of car of z is cons'ed to the result.

  
 (define (deep-reverse items) 
   (define (iter-reverse z result) 
     (cond ((null? z) result) 
           ((not (pair? z)) z) 
           (else (iter-reverse (cdr z) (cons (iter-reverse (car z) '()) result))) 
     ) 
   ) 
   (iter-reverse items '()) 
 ) 
  

I felt that this solution was very 'conforming' to the spirit of doing things the Scheme way, and added minimum complexity over the vanilla version of reverse, and therefore might be a useful addition here

My first contribution to this wiki

  
 (define (deep-reverse l) 
   (define atom? 
     (lambda (x) 
       (and (not (pair? x)) (not (null? x))))) 
   (define (reverse l) 
     (if (null? (cdr l)) 
         l  
         (append (reverse (cdr l)) (list (car l))))) 
   (cond 
     ((null? l) nil) 
     ((pair? (car l)) (append (deep-reverse (cdr l)) 
                              (list (deep-reverse (car l))))) 
     ((atom? (car l)) (append (deep-reverse (cdr l)) 
                              (list (car l)))) 
     (else (reverse l)))) 
  
 (deep-reverse '(13 14 (1 2 3) ((3 4) (1 2)) (6 (7 8 9) (7)))) 

results in

 (((7) (9 8 7) 6) ((2 1) (4 3)) (3 2 1) 14 13) 

which can be simplified

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

(first-timer here)

I think zerol's solution wins the cake for simplicity, readability, clarity AND application of newly learned material.

But here is mine, as it is somewhat different from the others:

 (define (deep-reverse items) 
   (if (pair? items) 
       (reverse (cons (deep-reverse (car items)) 
                      (reverse (deep-reverse (cdr items))))) 
       items)) 

I think using list? as condition is better than pair? since list? is strict thant pair? and the element of list could be just pair but not list. Consider a case like (list (cons 1 2) (cons 3 4)). Of course, pair? is enough for this execise.