Haskell是否有尾递归优化？

问题描述

限时删除！！

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

$ $ p $ code $ - 尾递归
fac ::（Integral a）=> a - > a
fac x = fac'x 1其中
fac'1 y = y
fac'xy = fac'（x-1）（x * y）

- 正常递归
facSlow ::（Integral a）=> a - > a
facSlow 1 = 1
facSlow x = x * facSlow（x-1）

这些都是有效的，因为他们只是用于这个项目，所以我没有打扰检查零或负数。

然而，为每个方法编写一个主要方法，编译它们，并使用time命令运行它们，两者的运行时间与普通的递归函数类似，只是逐渐递减尾递归函数。这与我在lisp中关于尾递归优化方面所听到的相反。这是什么原因？

解决方案

Haskell使用lazy-evaluation来实现递归，所以将任何事情视为承诺提供一个值在需要时（这称为thunk）。只有必要的时候，Thunk才会减少，不会再继续。这类似于用数学方式简化表达式的方式，所以以这种方式来思考就很有帮助。评估顺序不是由你的代码指定的事实允许编译器做很多更聪明的优化，而不仅仅是你曾经习惯的tail-call消除。 如果您想进行优化，请使用 -O2 进行编译 让我们看看我们如何评估 facSlow 5 作为案例研究：

  facSlow 5 
 5 * facSlow 4  - 注意`5-1`只被评估为4 
 5 *（4 * facSlow 3） - 因为必须对照1来检查
 5 *（4 *（3 * facSlow 2）） - 要应用`facSlow`的哪个定义。 
 5 *（4 *（3 *（2 * facSlow 1）））
 5 *（4 *（3 *（2 * 1）））
 5 *（4 *（3 * 2））
 5 *（4 * 6）
 5 * 24 
 120 
  

因此，就像你担心的那样，在进行任何计算之前，我们都会积累数字，但不像你担心的那样，没有 facSlow code>函数调用挂在等待终止 - 每个减少应用并消失，留下一个（这是因为（*）是严格的，因此会触发对其第二个参数的评估）。



Haskell的递归函数不是以非常递归的方式来计算的！唯一挂在身边的电话本身就是乘法。如果（*）被视为严格的数据构造函数，这就是所谓的防护递归（尽管它通常被称为 non - 严格数据构造函数，其中剩下的就是数据构造函数 - 当被进一步访问所强制时）。



现在让我们来看看尾递归 fac 5 ：

  fac 5 
 fac '5 1 
 fac'4 {5 * 1}  - 请注意，'5-1`只被评估为4 
 fac'3 {4 * {5 * 1}}  - 因为它必须检查1以查看
 fac'2 {3 * {4 * {5 * 1}}}  - 要应用哪种fac的定义。 
 fac'1 {2 * {3 * {4 * {5 * 1}}}} 
 {2 * {3 * {4 * {5 * 1}}}}  -  thunk {...}
（2 * {3 * {4 * {5 * 1}}}） - 被回溯
（2 *（3 * {4 * {5 * 1}} ）） - 创建
（2 *（3 *（4 * {5 * 1}））） - 计算
（2 *（3 *（4 *（5 * 1）） ）） - 堆栈
（2 *（3 *（4 * 5）））
（2 *（3 * 20））
（2 * 60）
 120 
  

所以你可以看到尾部递归本身是如何为你节省时间和空间的。它不仅需要比 facSlow 5 更多的步骤，它还构建了一个嵌套的thunk（这里显示为 {...} ） - 需要一个额外的空间 - 它描述了未来的计算，嵌套乘法的执行。



然后通过遍历 it 到底部来解开这个thunk，重新创建堆栈上的计算。如果我们想手工优化这个，我们所需要做的就是make它严格。您可以使用严格的应用程序操作符 $！来定义


  facSlim： ：（积分a）=> a  - > a 
 facSlim x = facS'x 1其中
 facS'1 y = y 
 facS'x y = facS'（x-1）$！ （x * y）
  

这会强制 facS'在第二个论点中要严格。 （它的第一个参数已经很严格了，因为必须对它进行评估，以决定应用哪个 facS'>的定义。）

有时候严格会有很大的帮助，有时这是一个很大的错误，因为懒惰更有效率。这是一个好主意：

  facSlim 5 
 facS'5 1 
 facS'4 5 
 facS'3 20 
 facS'2 60 
 facS'1 120 
 120 
  

这就是我想要达到的目标。

总结

• 如果你想优化你的代码，第一步是使用 -O2
进行编译

• 尾递归只有当没有thunk积累，并且加入严格性通常有助于防止它，如果适当的话。这种情况发生在您构建一次后需要的结果时。


• 有时候，尾递归是一个糟糕的计划，守护递归更适合，也就是说，重新建设将需要一点一点的，部分。查看例如， foldr 和 foldl ，并相互测试。

试试这两个：

  length $ foldl1（++）$ replicate 1000 
中间表达式的大小比尾递归更重要。 
长度$ foldr1（++）$ replicate 1000 
执行的缩减次数比尾递归更重要!!! 
  

foldl1 是尾递归，而 foldr1 执行守护递归，以便第一个项目立即呈现以供进一步处理/访问。

You might need to adjust the number of zeros depending on what hardware you're using.

这篇关于Haskell是否有尾递归优化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

1403页，肝出来的..