sicp-ex-2.39

  
  
  
 (define (fold-right op initial sequence) 
   (if (null? sequence) 
       initial 
       (op (car sequence) 
           (fold-right 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) 
  

  
  
  
 (define (reverse-using-left items) 
   (fold-left (lambda (result first) (cons first result)) 
              nil 
              items)) 
  
  
 ;;I think it is better to make no assumptions concerning use when defining the procedure  
 ;;that later will be passed as an argument to the formal parameter op of fold left.  
 ;;So i prefer the use of the neutral names x and y. 
  
 (define (reverse-using-left seq) 
   (fold-left (lambda (x y) (cons y x)) 
              '()  
              seq)) 
  
 ;Test  
  (reverse-using-left '(1 2 3 4 5)) 
 ;Value: (5 4 3 2 1) 
  

You could also define the reverse procedure using fold-right like that

  
 (define (reverse-using-right sequence) 
   (fold-right 
     (lambda (x y) 
       (fold-right cons (list x) y)) 
     nil 
     sequence)) 
  
 ;Test   
 (reverse-using-right '(1 2 3 4 5))  
 ;Value: (5 4 3 2 1) 
  

Maybe give a name to the inner lambda function could be a good idea:

  
 (define (push value sequence) 
   (fold-right cons (list value) sequence)) 
  
 ;starting from the last element, pushes all the elements on an empty list 
 (define (reverse-using-right sequence) 
   (fold-right push nil sequence)) 
  
 ;Test   
 (reverse-using-right '(1 2 3 4 5))  
 ;Value: (5 4 3 2 1) 
  

 (define (reverse sequence) 
   (fold-right (lambda (x y) (append y (list x))) () sequence)) 
  
 (define (reverse sequence) 
   (fold-left (lambda (x y) (append (list y) x)) () sequence))