为何foldr应用于双严格参数函数时不会引发栈溢出？

嘿，这个问题问得太戳点了——我刚啃Haskell的时候也被foldr的“反常”行为搞懵过！你说的没错，(+)和(-)都是严格求值的，按道理foldr常规的递归展开应该会生成一堆嵌套的调用，最后求值时把栈压爆，但GHC的优化魔法在这里偷偷帮了大忙！

1. 核心原因：foldr/build融合优化 #

首先得搞懂：Haskell里的[1..5000000]并不是真的一个个构造链表节点连起来的，它是通过build函数生成的——这是GHC专门为列表性能优化设计的机制。当GHC看到foldr和这种build生成的列表搭配时，会直接把两者“融合”成一段高效的循环代码，完全绕开了中间链表的构造，也彻底避免了递归调用栈的生成。

拿foldr (+) 0 [1..5000000]来说，GHC不会傻乎乎地先造一个500万元素的链表，再用foldr递归遍历。它会直接把这段代码转换成类似普通循环的逻辑：用一个累加变量从0开始，逐个加上1到5000000，全程没有递归栈的开销——因为根本没构造链表，也没有嵌套的(+)调用等着求值。

2. 为什么foldr (-) 0也能跑起来？ #

你肯定会疑惑：(-)不满足结合律啊！foldr (-) 0 [1,2,3]是1 - (2 - (3 - 0))，和foldl的结果完全不同，GHC总不能乱改计算顺序吧？

别担心，foldr/build融合根本不依赖操作的结合律！它只是把foldr的递归展开逻辑和列表的生成过程合并，生成一个严格按照foldr顺序求值的循环，而不是用递归栈来实现。比如处理foldr (-) 0 [1..n]时，GHC会生成一段代码，从右往左计算（对应foldr的嵌套顺序），但全程用变量保存中间结果，不会在栈上堆积调用帧。简单说，它把递归逻辑改成了迭代式的计算，自然不会栈溢出。

3. 什么时候foldr才会真的栈溢出？ #

只有当你的列表没办法触发foldr/build融合时，才会回到常规的递归展开，这时候大列表才会压爆栈。比如你手动构造一个链表：

-- 手动拼出来的链表，GHC没法做融合优化
let xs = 1 : 2 : 3 : ... : 5000000 : []
in foldr (+) 0 xs

这时候GHC只能老老实实按foldr的递归逻辑来，每一步都生成一个挂起的调用，最后求值时栈就会溢出。

总结一下：不是foldr本身变“乖”了，是GHC的融合优化把它和列表生成的过程捏成了高效的循环，不管是(+)还是(-)，只要能触发这个优化，就能轻松跑大列表而不栈溢出。

内容的提问来源于stack exchange，提问作者user6445533