Haskell中的foldr是尾递归吗？能否改造为尾递归并优化？

你观察的没错，原生定义的foldr结构上确实不是尾递归——它的递归调用结果是作为f的第二个参数传入的，也就是说在拿到递归返回值之前，外层还需要保留当前栈帧等待这个结果。

疑问1：能否将foldr改造为尾递归形式？ #

分两种情况看：

• 如果不要求保持foldr的原有语义：当然可以写出递归调用处于最后位置的代码，但这种改造本质上是把它换成了我们熟悉的左折叠foldl，它的定义就是标准尾递归结构：

  foldl :: (b -> a -> b) -> b -> [a] -> b
  foldl f acc [] = acc
  foldl f acc (x:xs) = foldl f (f acc x) xs
  

  这个结构和foldr的计算逻辑完全不同：foldr是从列表右端开始折叠，计算展开为f a1 (f a2 (f a3 z))；foldl是从左端开始折叠，计算展开为f (f (f z a1) a2) a3，两者只有在f满足结合律的时候结果才一致。
• 如果要100%保留foldr的原有语义：靠普通的尾递归写法根本实现不了。因为foldr的核心逻辑是用当前列表元素x，搭配后续递归计算的结果去调用f，这层“把后续结果和当前元素一起传给f”的操作必然在递归调用的外层，从结构上就不可能让递归调用成为函数的最终返回值。
  网上偶尔能看到用CPS（延续传递风格）写的所谓“尾递归版foldr”：

  foldrCPS :: (a -> b -> b) -> b -> [a] -> b
  foldrCPS f z xs = go xs id
    where
      go [] k = k z
      go (x:xs') k = go xs' (\rest -> k (f x rest))
  

  它只是形式上把递归调用放到了最后位置，但本质上是靠不断嵌套的函数闭包存储计算上下文，根本没有做到严格语言里尾递归“复用栈帧、不新增栈空间”的效果。

疑问2：改造后的尾递归版本会得到优化吗？ #

先澄清一个很多初学者搞混的点：Haskell里的“尾递归”概念和严格求值语言（比如Scheme、Python）里的尾递归不是一回事，GHC的尾调用优化是有严格触发条件的。
分场景说优化效果：

• 如果你改造后得到的是普通的惰性foldl版本：在默认的ghci（无优化）场景下完全不会被优化。它会在堆上生成一大串嵌套的惰性thunk，等你需要最终结果的时候才一层层求值，处理长列表时很容易栈溢出。只有换成严格求值的左折叠foldl'，强制每次递归前把累加器的值算到弱头规范形（WHNF），GHC才会把这段代码优化成等价的循环结构，真正做到栈空间恒定，不会栈溢出。
• 如果你改造后是上面提到的CPS版本foldr：完全吃不到GHC的尾调用优化。因为它尾位置传递的是嵌套的lambda闭包，GHC没法像处理普通值那样直接复用栈帧，反而会因为每次递归都要在堆上分配新的闭包，比原生的foldr定义开销更大。

最后说个反常识的事实：Haskell从设计之初就没打算让foldr靠尾递归提性能。foldr和惰性求值的适配度远高于任何强制尾递归的版本——它可以直接处理无限长列表，也能在不需要遍历完整列表的场景下提前终止计算，这些能力都是死磕尾递归的左折叠根本做不到的。

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