sicp-ex-2.18



<< Previous exercise (2.17) | Index | Next exercise (2.19) >>


jz

I couldn't figure out a way to do this problem without using an intermediary variable to store the reversed list as it is built. If there is such a way, post it.

  
 ;; ex 2.18, reverse. 
  
 ;; Note: nil isn't defined in my environment, using footnote from page 
 ;; 101. 
 (define nil '()) 
  
 (define (reverse items) 
   (define (iter items result) 
     (if (null? items) 
         result 
         (iter (cdr items) (cons (car items) result)))) 
  
   (iter items nil)) 
  
  
 ;; Usage 
 (reverse (list 1 2 3 4)) 
  

vlprans

This is a solution that doesn't use intermediary variable, former should be more efficient though.

  
 (define nil '()) 
  
 (define (reverse items) 
   (if (null? (cdr items)) 
       items 
       (append (reverse (cdr items)) 
               (cons (car items) nil)))) 
  
 (reverse (list 1 2 3 4)) 
  

You can get rid of the nil definition by replacing cons with list:

 guile>  
 (define (reverse items) 
   (if (null? (cdr items)) 
       items 
       (append (reverse (cdr items)) 
               (list (car items))))) 
 guile> (reverse (list 1 2 3 4)) 
 (4 3 2 1) 
 guile> 

You can also get rid of the boundary-condition failure by eliminating the first cdr:

 guile> (reverse '()) 
  
 Backtrace: 
 In standard input: 
    9: 0* [reverse {()}] 
    2: 1  (if (null? (cdr items)) items ...) 
    2: 2* [null? ... 
    2: 3*  [cdr {()}]] 
  
 standard input:2:14: In procedure cdr in expression (cdr items): 
 standard input:2:14: Wrong type (expecting pair): () 
 ABORT: (wrong-type-arg) 
 guile>  
 (define (reverse items) 
   (if (null? items) 
       items 
       (append (reverse (cdr items)) 
               (list (car items))))) 
 guile> (reverse '()) 
 () 
 guile> (reverse (list 1 2 3 4)) 
 (4 3 2 1) 
 guile> 
  

bmm

 ;; ex 2.18 
  
 ;; nil 
 (define nil '()) 
  
 ;; returns length of list 
 (define length (lambda (list) 
               (if (null? list) 0 
                   (+ 1 (length (cdr list)))))) 
  
 ;; returns the n-th element 
 (define list-ref (lambda (list n) 
               (if (= n 0) (car list) 
                   (list-ref (cdr list) (- n 1))))) 
  
 ;; reverse list procedure 
 (define (reverse list) 
   (define (do-reverse items size) 
     (if (< size 0) nil 
         (cons (list-ref items size) (do-reverse items (- size 1))))) 
   (let ((len (- (length list) 1))) 
     (do-reverse list len))) 
  
 ;; Test 
  
 (reverse (list 1 2 3 4 5)) ;; '(5 4 3 2 1) 

karthikk

Yes, the boundary condition (when the input parameter is the null list) should work. So here are two simple solutions: the first generates an iterative process and the second a recursive process (note since cons treats its first formal parameter as an atom, we have to use append in the recursive definition). The iterative solution is mostly the same as the fp's but the recursive definition eliminates testing the base step on the cdr of the list...

  
 ;iterative solution 
 (define (i-reverse l) 
   (define (it-rev lat ans) 
     (if (null? lat) 
         ans 
         (it-rev (cdr lat) (cons (car lat) ans)))) 
   (it-rev l '())) 
  
 ;recursive solution 
 (define (r-reverse lat) 
   (if (null? lat) 
       '() 
       (append (r-reverse (cdr lat)) (list (car lat))))) 


<< Previous exercise (2.17) | Index | Next exercise (2.19) >>