sicp-ex-2.38

  
 ;; Accumulates the result of the first and the already-accumulated 
 ;; rest. 
 (define (accumulate op initial sequence) 
   (if (null? sequence) 
       initial 
       (op (car sequence) 
           (accumulate op initial (cdr sequence))))) 
  
 (define (fold-right op initial sequence) 
   (accumulate op initial 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)) 
  

  (fold-right / 1 (list 1 2 3))
  = (/ 1 (/ 2 (/ 3 1)))
  = (/ 1 2/3)
  = 3/2

  (fold-left / 1 (list 1 2 3))
  = (/ (/ (/ 1 1) 2) 3)
  = (/ (/ 1 2) 3)
  = (/ 1/2 3)
  = 1/6

  (fold-right list nil (list 1 2 3))
  = (list 1 (list 2 (list 3 nil)))
  = (1 (2 (3 ())))

I wasn't expecting that final nil to be there, but I guess it *was* added to the newly-created list.

  (fold-left list nil (list 1 2 3))
  = (list (list (list nil 1) 2) 3)
  = (((() 1) 2) 3)

Same story with the innermost nil here.

Op has to be associative for fold-left and fold-right to be equivalent. For example, folding left and right with division would not be equivalent, but with matrix multiplication would (despite it's not a commutative operation).

  (fold-left + 0 (list 1 2 3 4))
  (fold-right + 0 (list 1 2 3 4))

The op must be commutative to ensure fold-left and fold-right get the same result. Consider sequence to be [x1, x2, ... xn], then (fold-left op init sequence) will be (op (op ... (op init x1) x2) ... xn) and (fold-right op init sequence) will be (op (op ... (op xn init) xn-1) ... x1). Now consider a special case sequence only contains one element, so sequence = [x1], then fold-left will get (op init x1) and fold-right will get (op x1 init), for these two to be equal, op must be commutative.