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:

What are the values of

3/2

1/6

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

Leave a Reply