Exercise 2.38 of SICP

2009-08-23

sicp

Exercise 2.38: The accumulate procedure is also known as fold-right, because it combines the first element of the sequence with the result of combining all the elements to the right. There is also a fold-left, which is similar to fold-right, except that it combines elements working in the opposite direction:

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

What are the values of

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

3/2

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

1/6
    
(fold-right list nil (list 1 2 3))

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

(((() 1) 2) 3)

Give a property that op should satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

(fold-right op i (list a1 a2 a3))

$$ (a_1 \cdot (a_2 \cdot ( a_3 \cdot i))) $$

(fold-left op i (list a1 a2 a3))

$$ (((i \cdot a_1) \cdot a_2) \cdot a_3) $$

Any binary associative operation will be invariant under fold-right and fold-left. Since 2.37 involved matrix multiplication which is associative, I will use that as an example.

> (define i (list (list 1 0 0) (list 0 1 0) (list 0 0 1)))
> (define a1 (list (list 8 3 2) (list 1 0 9) (list 3 4 5)))
> (define a2 (list (list 5 6 7) (list 1 2 8) (list 6 7 7)))
> (define a3 (list (list 6 7 9) (list 4 3 1) (list 3 4 5)))
> (fold-left matrix-*-matrix i (list a1 a2 a3)) 

((884 965 1033) (840 900 950) (802 878 942))

> (fold-right matrix-*-matrix i (list a1 a2 a3)) 

((884 965 1033) (840 900 950) (802 878 942))

Notice that i is the identity matrix because if it wasn’t, I would also be testing commutativity of matrix product. Matrix product doesn’t commute. If i is changed to another matrix fold-left and fold-right will return differing results.

Contents