我今天在 unix 中发现了“时间”命令，并认为我会用它来检查 Haskell 中尾递归和普通递归函数之间的运行时差异。
我写了以下函数：
--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
fac' 1 y = y
fac' x y = fac' (x-1) (x*y)
--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)
这些是有效的，请记住它们仅用于该项目，因此我没有费心检查零或负数。
但是，在为每个方法编写主方法、编译它们并使用“time”命令运行它们后，两者都具有相似的运行时，正常递归函数将尾递归函数边缘化。这与我听到的关于 lisp 中的尾递归优化的说法相反。这是什么原因？
Haskell 使用惰性求值来实现递归，因此将任何东西都视为在需要时提供值的承诺（这称为 thunk）。Thunks 只减少到继续进行所需的量，不再减少。这类似于您在数学上简化表达式的方式，因此以这种方式思考它是有帮助的。您的代码未指定评估顺序这一事实允许编译器进行许多更聪明的优化，而不仅仅是您习惯的尾调用消除。如果要优化，请编译！-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等待终止的函数调用堆栈 - 每次减少都被应用并消失，在其中留下一个堆栈帧唤醒（这是因为(*)它是严格的，因此会触发对其第二个参数的评估）。
Haskell 的递归函数不是以非常递归的方式计算的！唯一的一堆调用是乘法本身。如果 (*)被视为严格的数据构造函数，这就是所谓的保护递归（尽管它通常与非严格数据构造函数一起被称为，其中留下的是数据构造函数 - 当被进一步访问强制时）。
现在让我们看一下尾递归fac 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
因此，您可以看到尾递归本身并没有为您节省任何时间或空间。它不仅比 总体上需要更多的步骤facSlow 5，而且还构建了一个嵌套的 thunk（此处显示为{...}） - 需要一个额外的空间- 它描述了未来的计算，要执行的嵌套乘法。
然后通过遍历到底部来解开这个 thunk，在堆栈上重新创建计算。对于这两个版本，这里还有一个导致堆栈溢出的危险，计算时间很长。
如果我们想手动优化它，我们需要做的就是让它变得严格。您可以使用严格的应用程序运算符$!来定义
facSlim :: (Integral a) => a -> a
facSlim x = facS' x 1 where
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
我认为这就是您想要实现的目标。
-O2foldrfoldl试试这两个：
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是尾递归，而foldr1执行受保护的递归，以便立即呈现第一项以供进一步处理/访问。（第一个“括号”立即向左，(...((s+s)+s)+...)+s，强制其输入列表完全到其末尾，并比需要其完整结果更快地构建未来计算的大块；第二个逐渐向右括号，s+(s+(...+(s+s)...))，消耗输入逐点列出，因此整个事物能够在恒定空间中运行，并进行优化）。
您可能需要根据您使用的硬件调整零的数量。
应该提到的是，该fac函数不是保护递归的好候选者。尾递归是这里的方法。由于懒惰，您没有在fac'函数中获得 TCO 的效果，因为累加器参数不断构建大型 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（或仅）编译，GHC 可能会在严格性分析阶段-O自行执行此操作。
您应该查看有关Haskell 中尾递归的 wiki 文章。特别是，由于表达式评估，您想要的递归类型是受保护的递归。如果你弄清楚幕后发生的事情的细节（在 Haskell 的抽象机器中），你会得到与严格语言中的尾递归相同的东西。除此之外，您对惰性函数有统一的语法（尾递归将使您与严格的评估联系起来，而保护递归更自然地工作）。
（在学习 Haskell 时，其他 wiki 页面也很棒！）
如果我没记错的话，GHC 会自动将普通递归函数优化为尾递归优化函数。