foldl与foldr的本质区别:从惰性求值说起

Differences Between `Foldl` and `Foldr`

foldl与foldr的本质区别:从惰性求值说起

很多人误以为foldl和foldr的区别在于遍历方向,其实两者都是从左到右遍历列表,真正的差异在于结合的关联性。在严格语言中,foldl可以尾递归实现常数空间,而foldr需要栈帧线性增长。但在Haskell这样的惰性语言中,情况反转:默认的foldl会构建巨大的thunk导致空间泄漏,必须使用foldl'来强制求值;而foldr因为惰性特性,能在处理无限列表或流式处理时节省大量工作。理解这些机制,是掌握Haskell函数式编程的关键。

在惰性语言中,foldl之所以糟糕是因为它太懒惰,会构建巨大的thunk,而foldr之所以优秀恰恰是因为它的惰性特性。
  1. s-zeng

    关于列表上的 foldr,有一个 neat 的事实:与 foldl 不同,它在每一步折叠时实际上将控制流完全交给了累加函数。这意味着你可以用 foldr 来实现任意的列表遍历,包括 foldl' 或提前退出的列表遍历。参见 https://github.com/quchen/articles/blob/master/useful_techni...

  2. layer8

    > Both foldl and foldr traverse the structure in the same order, which in the case of lists means left to right.

    这种说法值得商榷,除非你默认是单向链表——按定义,单向链表只能从左到右遍历(在惰性语言中更是如此,因为列表长度可能是不确定的)。如果在严格语言中针对数组或双向链表实现,foldr 的遍历顺序将是右到左。

    更准确的说法应该是:在 Haskell 中,列表只能从左到右遍历,因此 Haskell 中 foldl 和 foldr 的实现必然基于这一点。

  3. mbauman

    对计算机科学家来说,"顺序"指的是列表的排列方式。但几乎所有人都会想到操作的*时间*顺序。在这种情况下,确实可以说是"从右"或"从左"开始。

    当你处理大量延迟/惰性操作时,这就容易让人混淆。

同日更多故事

2026-10-05