我寻思没啥好写了,于是来水一篇文章。
写 SICP 习题的时候被 Guile 中 fold
和 fold-left
的不一致坑了。我本以为它们是一个东西,实际上它们的方向完全相反。所以就画个图介绍一下它们的区别吧(然而我写这篇文章的大部分时间都花在画图上)。
当然我是不懂犯愁论的,所以关于 Catamorphism 和 F-Algebra 的内容就不深入了,等我有机会去学一遍再回头看看。
Guile 中 fold
出自模块 (srfi srfi-1)
, fold-left
出自模块 (rnrs lists)
, fold-right
就牛逼了,两个模块都提供。
fold-right

所以列表其实就是一个用 cons
做fold-right
出来的数据结构。
fold

(define (fold fn init list)
(fold-right fn init (reverse list)))
fold
其实还是一个 fold-right
,只不过顺序变了一下。
fold-left

fold-left
其实是改变了结合方向的 fold-right
。
因此在满足结合律的二元运算符是不容易看出来和 fold-right
有什么区别的。
可以把上面的 +
换成 -
。或直接将 0
换成 '()
,然后用 cons
连接,这样对比就更直接了(这样子 fold-left
的结果甚至都不是一个列表哦)。