sicp-ex-2.39



<< Previous exercise (2.38) | Index | Next exercise (2.40) >>


jz

  
  
  
 (define (fold-right op initial sequence) 
   (if (null? sequence) 
       initial 
       (op (car sequence) 
           (accumulate op initial (cdr sequence))))) 
  
  
 (define (fold-left op initial sequence) 
   (define (iter result rest) 
     (if (null? rest) 
         result 
         (iter (op result (car rest)) 
               (cdr rest)))) 
   (iter initial sequence)) 
  

For fold-right: use append to ensure the list is built with correct nesting, and put the first item in a list so it can be appended.

For fold-left: The inner iter in fold-left keeps peeling off the first item and doing something with it and the current result, then passing that result and the remaining items to itself. So, items are getting handled in order, from left to right, and just need to be added to the result.

  
 (define (reverse-using-right items) 
   (fold-right (lambda (first already-reversed) 
                 (append already-reversed (list first))) 
               nil 
               items)) 
  
 (define (reverse-using-left items) 
   (fold-left (lambda (result first) (cons first result)) 
              nil 
              items)) 
  
 ;; Test 
 (define items (list 1 2 3 4 5)) 
 (reverse-using-right items) 
 (reverse-using-left items)