**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:

1 2 3 4 5 6 7 |
(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

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

*3/2*

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

*1/6*

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

*(1 (2 (3 ())))*

1 |
(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 a_{1} a_{2} a_{3}))

(fold-left op i (list a_{1} a_{2} 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.