fold, fold-right 和 fold-left

我寻思没啥好写了,于是来水一篇文章。

写 SICP 习题的时候被 Guile 中 foldfold-left 的不一致坑了。我本以为它们是一个东西,实际上它们的方向完全相反。所以就画个图介绍一下它们的区别吧(然而我写这篇文章的大部分时间都花在画图上)。

当然我是不懂犯愁论的,所以关于 Catamorphism 和 F-Algebra 的内容就不深入了,等我有机会去学一遍再回头看看。

Guile 中 fold 出自模块 (srfi srfi-1)fold-left 出自模块 (rnrs lists)fold-right 就牛逼了,两个模块都提供。

fold-right

所以列表其实就是一个用 consfold-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 的结果甚至都不是一个列表哦)。

发表评论