# Exercise 2.38 of 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.