sicp-ex-2.18

[Top Page][Recent Changes][All Pages][Settings][Categories][Wiki Howto]
[Edit][Edit History]

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>