Exercise 2.38 · 习题

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))
(fold-left / 1 (list 1 2 3))
(fold-right list nil (list 1 2 3))
(fold-left list nil (list 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.

练习 2.38：过程 accumulate 也称为 fold-right，因为它将序列的第一个元素与右边所有元素的组合结果合并在一起。还有一个 fold-left，与 fold-right 类似，但它沿相反方向组合元素：

(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))
(fold-left / 1 (list 1 2 3))
(fold-right list nil (list 1 2 3))
(fold-left list nil (list 1 2 3))

给出 op 需要满足的一个性质，使得对任意序列，fold-right 和 fold-left 都能产生相同的值。