练习 2.38¶

先将题目计算所需的 fold-left 和 fold-right 写下来。

fold-left 直接对着题目敲下来就行了：

;;; 38-fold-left.scm

(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 也只是简单地对书本 78 页的 accumulate 函数进行改名：

;;; 38-fold-right.scm

(load "p78-accumulate.scm")

(define fold-right accumulate)

accumulate 函数的定义如下：

;;; p78-accumulate.scm

(define (accumulate op initial sequence)
    (if (null? sequence)
        initial
        (op (car sequence)
            (accumulate op initial (cdr sequence)))))

求值¶

表达式 (fold-right / 1 (list 1 2 3)) 的值是：

1 ]=> (fold-right / 1 (list 1 2 3))

;Value: 3/2

这个表达式生成的计算序列是：

(/ 1 (/ 2 (/ 3 1)))

(/ 1 (/ 2 3))

(/ 1 2/3)

3/2

表达式 (fold-left / (list 1 2 3)) 的值是：

1 ]=> (fold-left / 1 (list 1 2 3))

;Value: 1/6

这个表达式生成的计算序列是：

(/ (/ (/ 1 1) 2) 3)

(/ (/ (/ 1 1) 2) 3)

(/ (/ 1 2) 3)

(/ 1/2 3)

1/6

表达式 (fold-right list '() (list 1 2 3)) 的值是：

1 ]=> (fold-right list '() (list 1 2 3))

;Value 11: (1 (2 (3 ())))

这个表达式生成的计算序列是：

(list 1 (list 2 (list 3 '())))

(list 1 (list 2 (3 '())))

(list 1 (2 (3 '())))

(1 (2 (3 '())))

注意， () 是求值器对 '() 的打印格式，展开代码中使用了 '() 而不是 () ，注意不要把它们搞混了。

表达式 (fold-left list '() (list 1 2 3)) 的值是：

1 ]=> (fold-left list '() (list 1 2 3))

;Value 12: (((() 1) 2) 3)

这个表达式生成的计算序列是：

(list (list (list '() 1) 2) 3)

(list (list ('() 1) 2) 3)

(list (('() 1) 2) 3)

((('() 1) 2) 3)

fold-left 和 fold-right 产生同样的结果¶

因为 fold-left 和 fold-right 生成的计算序列不同，要让它们的计算产生同样的结果，一个办法就是要求 op 参数，也即是传入的操作函数必须符合结合律（monoid）。

比如说， \ 和 list 函数都不符合结合律，所以将它们应用到 fold-left 和 fold-right 会产生不同的计算结果。

另一方面，像 + 、 * 、 or 和 and 那样的函数，就是符合结合律的函数，使用这些函数可以让 fold-left 和 fold-right 计算出同样的结果：

1 ]=> (fold-left * 1 (list 1 2 3 4))

;Value: 24

1 ]=> (fold-right * 1 (list 1 2 3 4))

;Value: 24

1 ]=> (fold-left + 0 (list 1 2 3 4))

;Value: 10

1 ]=> (fold-right + 0 (list 1 2 3 4))

;Value: 10

让 fold-left 和 fold-right 得出同样结果的另一种办法是，在 fold-left 和 fold-right 之间进行转换，从而让两个函数产生同样的计算序列，练习练习 2.39 就是这样的一个例子。

Navigation

练习 2.38¶

求值¶

fold-left 和 fold-right 产生同样的结果¶

讨论 ¶

Navigation