先将题目计算所需的 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
生成的计算序列不同,要让它们的计算产生同样的结果,一个办法就是要求 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 就是这样的一个例子。
See also
维基百科的 Fold 词条 给出了关于 fold
的主要特性。
See also
论文 A tutorial on the universality and expressiveness of fold 给出了很多 fold
操作的例子,非常实用。
See also
书本 《Introduction to Functional Programming》(第一版) 在 3.5 节讲到了结合律在函数中的应用。