foldl 与 foldr 的区别：结合性而非遍历方向

核心要点

• foldl 与 foldr 都以从左到右的顺序遍历列表，区别在于运算的结合方向：foldl 左结合，foldr 右结合。
• 在严格语言里，foldl 可以尾递归、以常数空间规约；foldr 则必须先建起 n 层栈帧才能开始计算。
• 在 Haskell 中，惰性的 foldl 会累积一条随输入线性增长的 thunk 链，把常数空间算法变成线性空间。
• 因此需要严格的 foldl’，它在处理下一个元素前先强制求值，让 thunk 始终不超过一次运算。
• 当累积函数在第二个参数上惰性时，foldr 反而能增量产出结果，支持无限列表与流式消费。
• 经验法则是：累积函数严格就用 foldl’，惰性就用 foldr，永远不要用 foldl 或 foldr’。
• 把这些结论推广到其它数据结构时会变模糊，因为树这类结构中元素既在左也在右，此时 foldMap 往往是更好的选择。

金句

← 返回 Lobsters 首页