Haskell有尾递归优化吗？

Question

Haskell有尾递归优化吗？

我今天在unix中发现了“time”命令，并认为我会用它来检查Haskell中尾递归和正常递归函数之间运行时的差异。

我写了以下函数：

--tail recursivefac :: (Integral a) => a -> a
fac x = fac' x 1 where
    fac' 1 y = y
    fac' x y = fac' (x-1) (x*y) --normal recursivefacSlow :: (Integral a) => a -> a
facSlow 1 = 1facSlow x = x * facSlow (x-1)

这些都是有效的，记住它们只是用于这个项目，所以我没有费心去检查零或负数。

但是，在为每个编写main方法，编译它们并使用“time”命令运行它们时，两者都具有相似的运行时，正常的递归函数使尾递归函数边缘化。这与我在lisp中关于尾递归优化的内容相反。这是什么原因？

Answer 1

你应该查看关于Haskell中尾部递归的wiki文章。特别是，由于表达式评估，您想要的递归类型是保护递归。如果你弄清楚幕后发生了什么（在Haskell的抽象机器中）你会得到与严格语言中的尾递归相同的东西。除此之外，您还有一个统一的惰性函数语法（尾递归会将您绑定到严格的评估，而受保护的递归更自然地工作）。（在学习Haskell时，其余的wiki页面也很棒！）