Haskell中的foldR尾递归吗？

Question

我是 Haskell 的新手，从第一性原理开始阅读 Haskell，在第 384 页的折叠章节中，我遇到了FoldR，似乎它不是尾递归的

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

1-我们可以让它尾递归吗？

2-它会被优化吗？

Answer 1

在像 Haskell 这样的惰性语言中，尾递归通常是一个坏主意。这是其中一种情况。

我们可能会尝试foldr通过例如从 a 开始reverse（这也可以以尾递归方式进行）来使尾递归成为尾递归，然后foldr以尾递归方式逐步累积结果。但是，这会破坏foldr语义。

使用标准foldr，我们有例如

foldr (\_ _ -> k1) k2 (x:xs) = k1

无论是什么xs，包括undefined像[0..]. 此外，当xs是一个有限但很长的列表时，上面的代码也是有效的，因为它会立即停止计算而无需扫描整个列表。

作为一个更实际的例子，

and :: [Bool] -> Bool
and = foldr (&&) True

使 的某些元素评估为 后立即and xs返回，而不扫描列表的其余部分。FalsexsFalse

最后，foldr变成尾递归函数将：

• 在处理部分定义的列表 ( 1:2:undefined) 或无限列表 ( )时更改语义[0..]；
• 在有限长度列表上效率较低，即使不需要，也总是必须完全扫描。

Answer 2

foldr不是尾递归......但它可用于编写处理常量空间中的列表的函数。chi已经指出，它可以and有效地实施。以下是它如何实现对列表求和的有效函数：

mySum :: Num a => [a] -> a
mySum xs = foldr go id xs 0
  where
    go x r acc = r $! x + acc

这个工作怎么样？考虑mySum [1,2,3]。这扩展到

foldr go id [1,2,3] 0
==> -- definition of foldr
go 1 (foldr go id [2,3]) 0
==> -- definition of go
foldr go id [2,3] $! 1 + 0
==> -- strict application
foldr go id [2,3] 1

我们将列表大小减少了 1，并且没有在“堆栈”上累积任何内容。重复相同的过程，直到我们得到

foldr go id [] 6
==> definition of foldr
id 6
==> definition of id
6

注意：如果此代码由 GHC 编译并启用了优化（-O或-O2），那么它实际上会将其转换为极快的尾递归代码，而无需您的任何进一步帮助。但即使未优化，它也能正常工作，不会消耗大量内存/堆栈。