Haskell有尾recursion优化吗？
我在今天发现了unix中的“time”命令，并认为我会用它来检查Haskell中的尾recursion函数和正常recursion函数之间的运行时间差异。
我写了以下function：
--tail recursive fac :: (Integral a) => a -> a fac x = fac' x 1 where fac' 1 y = y fac' xy = fac' (x-1) (x*y) --normal recursive facSlow :: (Integral a) => a -> a facSlow 1 = 1 facSlow x = x * facSlow (x-1) 记住这些是完全用于这个项目的，所以我没有费心检查零或负数。
但是，在为每个方法编写一个主要方法时，编译它们并使用“time”命令运行它们，都具有与正常recursion函数相似的运行时间。 这与我在Lisp中关于尾recursion优化方面所听到的相反。 这是什么原因？
Haskell使用懒惰评估来实现recursion，所以把所有东西视为一个承诺，在需要的时候提供一个值（这叫做thunk）。 只有在必要的时候才能减lessThunk，不能再进行。 这类似于用math方式简化expression式的方式，因此以这种方式来思考是有帮助的。 评估顺序不是由你的代码指定的事实允许编译器做很多甚至更聪明的优化，而不仅仅是你曾经使用过的tail-call消除。 编译与-O2如果你想优化！
让我们看看我们如何评估facSlow 5作为案例研究：
facSlow 5 5 * facSlow 4 -- Note that the `5-1` only got evaluated to 4 5 * (4 * facSlow 3) -- because it has to be checked against 1 to see 5 * (4 * (3 * facSlow 2)) -- which definition of `facSlow` to apply. 5 * (4 * (3 * (2 * facSlow 1))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120
所以就像你担心的那样，在进行任何计算之前，我们都有一个积累的数字，但不像你担心的那样，没有一堆facSlow函数调用挂在等待终止 – 每个减less被应用并消失，留下一个堆栈帧它的醒来（这是因为(*)是严格的，所以触发了它的第二个参数的评估）。
Haskell的recursion函数不是以非常recursion的方式来计算的！ 悬挂的唯一一堆电话本身就是乘法。 如果(*)被视为一个严格的数据构造函数，这就是所谓的守护recursion（虽然它通常被称为非严格数据构造函数，其中剩下的是数据构造函数 – 当被进一步强制访问）。
现在我们来看看尾recursionfac 5 ：
fac 5 fac' 5 1 fac' 4 {5*1} -- Note that the `5-1` only got evaluated to 4 fac' 3 {4*{5*1}} -- because it has to be checked against 1 to see fac' 2 {3*{4*{5*1}}} -- which definition of `fac'` to apply. fac' 1 {2*{3*{4*{5*1}}}} {2*{3*{4*{5*1}}}} -- the thunk "{...}" (2*{3*{4*{5*1}}}) -- is retraced (2*(3*{4*{5*1}})) -- to create (2*(3*(4*{5*1}))) -- the computation (2*(3*(4*(5*1)))) -- on the stack (2*(3*(4*5))) (2*(3*20)) (2*60) 120
所以你可以看到尾部recursion本身如何没有为你节省任何时间和空间。 它不仅需要比facSlow 5更多的步骤，而且还构build了一个嵌套的thunk（这里显示为{...} ） – 需要额外的空间 – 描述未来的计算，嵌套的乘法运算。
然后通过遍历它到底部来解开这个thunk，重新创build栈上的计算。 对于这两个版本来说，在很长时间的计算中也会导致堆栈溢出。
如果我们想要手工优化这个，我们所要做的就是严格要求。 你可以使用严格的应用程序运算符$! 界定
facSlim :: (Integral a) => a -> a facSlim x = facS' x 1 where facS' 1 y = y facS' xy = facS' (x-1) $! (x*y)
这迫使facS'在第二个论点中严格要求。 （它的第一个论点已经很严格了，因为必须对它进行评估，以决定应用哪种定义）。
有时候严格会有很大的帮助，有时这是一个很大的错误，因为懒惰更有效率。 这是一个好主意：
facSlim 5 facS' 5 1 facS' 4 5 facS' 3 20 facS' 2 60 facS' 1 120 120
这是你想达到我想的。
概要
- 如果你想优化你的代码，第一步是用
-O2编译 - 只有在没有thunkbuild立的情况下，尾recursion才是有效的，并且在适当的情况下添加严格性通常有助于防止它。 这种情况发生在您一次性构build所需的结果时。
- 有时候，尾recursion是一个糟糕的计划，守护recursion更合适，也就是说，当你正在构build的结果将需要一点一点地分步。 例如，看到这个关于
foldr和foldl问题 ，并且相互testing它们。
试试这两个：
length $ foldl1 (++) $ replicate 1000 "The size of intermediate expressions is more important than tail recursion." length $ foldr1 (++) $ replicate 1000 "The number of reductions performed is more important than tail recursion!!!"
foldl1是尾recursion，而foldr1执行守护recursion，以便第一个项目被立即提交进一步处理/访问。 （第一个“括号”一下子， (...((s+s)+s)+...)+s ，迫使它的input列表完全结束，并且构build了大量的未来计算比它的全部结果要快;第二个逐渐向右加括号， s+(s+(...+(s+s)...)) ，消耗input列表一点一点，所以整个事情能够在恒定的空间中运行，并进行优化）。
您可能需要根据您使用的硬件调整零的数量。
应该提到的是， fac函数不是一个守护recursion的好select。 尾recursion是去这里的路。 由于懒惰，你的function没有得到TCO的影响，因为累加器的参数不断build立大的thunk，当评估时需要一个巨大的堆栈。 为了防止这种情况发生，并获得预期的TCO效果，您需要严格执行这些累加器参数。
{-# LANGUAGE BangPatterns #-} fac :: (Integral a) => a -> a fac x = fac' x 1 where fac' 1 y = y fac' x !y = fac' (x-1) (x*y)
如果使用-O2 （或者只是-O ）编译，GHC可能会在严格性分析阶段自行完成。
您应该查看关于Haskell中的尾recursion的wiki文章。 特别是，由于expression式的评价，你想要的recursiontypes是守护recursion。 如果你弄清楚了在Haskell的抽象机器下发生了什么的细节，你会得到和严格语言中的尾recursion类似的东西。 除此之外，对于懒函数你有一个统一的语法（尾recursion将使你严格评估，而守护recursion更自然地工作）。
（而在学习Haskell时，其余的维基页面也很棒！）
如果我没有记错，GHC会自动将简单recursion函数优化为尾recursion优化函数。
