haskell - 尾递归，我应该在 Haskell 中使用它吗

Question

这个问题已经有答案了:

Does Haskell have tail-recursive optimization? (4 个回答)

已关闭 9 年前。

我知道 Haskell 中的尾递归由于其惰性而遇到一些困难。也就是说，在 Haskell 中使用尾递归是否明智？

Answer 1

与这些重大问题一样，答案是“视情况而定”。

例如，当您以懒惰的方式进行编程时，通常可以使用简单的递归来逃脱

 map f (x:xs) = f x : map f xs
 map _ []     = []

实际上是标准库中定义map的方式。这很好，因为尾递归函数产生的结果通常不能很好地延迟，如果您执行类似 head 的操作，尾递归映射将不会终止。 map (+1) $ [1..].

但是，有时我们不想偷懒。典型的例子是当我们太懒并开始构建我们真正只想评估的 thunk 时，就像对列表求和时。

sum xs = someFold (+) 0 xs

现在，由于 + 的参数和关联非常严格，因此没有理由使用 foldr 但 foldl' 是完美的，它是尾递归并严格评估，从而带来显着的空间改善。 ' 很重要，在许多尾递归函数中，每个递归步骤都会修改一个累加器，foldl' 将强制对其求值，从而防止我们的尾递归函数太懒惰和积累重击。

所以这个故事的寓意是，当您惰性编程并生成惰性数据结构时，尾递归并不是什么大问题。但是，当您严格编程并在两个参数中严格使用函数时，尾递归对于保持良好的性能非常重要。