Haskell有尾递归优化吗？

Question

我今天在unix中发现了"time"命令,并认为我会用它来检查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)

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

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

Answer 1

Haskell使用惰性求值来实现递归,因此将任何东西视为在需要时提供值的promise(这称为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

我认为这是你想要实现的目标.

摘要

• 如果要优化代码,第一步是编译 -O2
• 尾部递归只有在没有thunk积累的情况下才有用,并且添加严格性通常有助于在适当的时候阻止它.当您构建稍后需要的结果时,会发生这种情况.
• 有时尾递归是一个糟糕的计划,保护递归是一个更好的拟合,即当你正在构建的结果将需要一点一滴地分开.见这个问题有关foldr,并foldl举例来说,并测试他们反目成仇.

试试这两个:

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)...)),消耗输入逐位列出,所以整个事物能够在恒定的空间中运行,并进行优化).}

您可能需要根据所使用的硬件调整零的数量.

Answer 2

应该提到的是,该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(或仅仅-O)编译,GHC可能会在严格性分析阶段自行完成.

Answer 3

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

(在学习Haskell时,其余的wiki页面也很棒!)