sicp-ex-2.38

Actually, there's a much simpler way to implement `fold-left` iteratively than the book provides. Here it is:

 (define (my-fold-left op init seq) 
   (if (null? seq) 
       init 
       (my-fold-left op (op init (car seq)) (cdr seq)))) 

  
 ;; 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.

\n

\n

examples of unfolding (brackets show priority):

1. seq = '(a), op = +, zero = 0

   foldr: a + 0
   foldl: 0 + a

2. seq = '(a b)

   foldr: a + (b + 0)
   foldl: (0 + a) + b

[foldl, foldr as given in the book]

so i'd say you need both commutativity and associativity. either alone is not enough.

\n

\n

Suppose (foldl f a s) = (foldr f a s) for all a, s

Then (f a b) = (foldl f a (b)) = (foldr f a (b)) = (f b a)
So f is commutative.

also
(f a (f b c)) = (f a (f c b)) (commutativity)
= (foldr f b (a c))
= (foldl f b (a c))
= (f (f b a) c)
= (f (f a b) c) (commutativity)
so f is associative

Multiplication and addition properties for op works as well if we want to ensure commutative criteria.

Strict commutativity is not required. Consider OP as matrix multiplication where INITIAL value is identity marix I. I * A = A * I and also OP is associative so foldleft and foldright on matrix mulitiplication gives the same result. However matrix multiplication (the OP) is not commutative.

Update: However there is no universal Identity Matrix of all shapes! The above arguments are not valid.

Adding to woofy: associativity is required. Next to this either: a) the operator is commutative, as explained before. b) an identity element for the operator is given (see Monoid)

Eg:

 (fold-left append nil (list '(1) '(2 3) '() '(4)))    ;; (1 2 3 4) 
 (fold-right append nil (list '(1) '(2 3) '() '(4)))   ;; (1 2 3 4) 
  
 ;; if we use something other than nil, results will be different: 
 (fold-left append '(5)  (list '(1) '(2 3) '() '(4)))  ;; (5 1 2 3 4) 
 (fold-right append '(5) (list '(1) '(2 3) '() '(4)))  ;; (1 2 3 4 5)