6

在 Haskell 中，如果我写

 fac n = facRec n 1
   where facRec 0 acc = acc
         facRec n acc = facRec (n-1) (acc*n)

并用 GHC 编译它，结果会与我使用的不同吗

 fac 0 = 1
 fac n = n * fac (n-1)

我可以轻松地做到fac n = product [1..n]并避免整个事情，但我对尾递归的尝试如何在惰性语言中发挥作用很感兴趣。我知道我仍然可以得到堆栈溢出，因为 thunk 正在建立，但是当我使用累加器时，实际上发生的任何事情（就生成的编译程序而言）与我只是陈述天真的递归时不同吗？除了提高易读性之外，省略尾递归还有什么好处？如果我runhaskell用来运行计算而不是先编译它，答案是否会发生变化？

4

3 回答 3

10

如果您的累加器是严格的，尾递归在 (GHC) Haskell 中确实有意义。为了演示这个问题，这里是您的尾递归定义的“跟踪” fac：

   fac 4
~> facRec 4 1
~> facRec 3 (1*4)
~> facRec 2 ((1*4)*3)
~> facRec 1 (((1*4)*3)*2)
~> facRec 0 ((((1*4)*3)*2)*1)
~> (((1*4)*3)*2) * 1
  ~> ((1*4)*3) * 2
    ~> (1*4) * 3
      ~> 1*4
    ~> 4 * 3
  ~> 12 * 2
~> 24 * 1
~> 24

缩进级别（大致）对应于堆栈级别。请注意，累加器仅在最后进行评估，这可能会导致堆栈溢出。当然，诀窍是使累加器严格。如果在严格的上下文中调用 facRec ，理论上可以证明它是严格的，但我不知道有任何编译器这样做，ATM。不过， GHC确实会进行尾调用优化，因此facRec调用使用恒定的堆栈空间。

出于同样的原因foldl'，通常优先于foldl，因为前者在累加器中是严格的。

关于您的第二部分，runhaskell/runghc只是 GHCi 的包装。如果 GHCi 找到已编译的代码，它将使用它，否则它将使用执行少量优化的字节码解释器，因此不要期望会发生任何花哨的优化。

于 2010-11-26T14:54:37.583 回答
3

在 haskell 中，如果你的累加器是严格的并且你需要整个结果，它只会有助于以尾递归的方式编写你的程序。

使用 ghc 的 runHaskell 程序不会被优化，所以不会进行严格分析，所以可能会出现堆栈溢出；而如果您使用优化进行编译，编译器可能会检测到累加器需要严格并相应地进行优化。

要了解事情发生的不同（或不同），最好的方法是检查生成的核心语言，Don Stewart 的一篇很好的博客文章解释了事情。顺便说一句，如果您对性能感兴趣，他的许多博客文章都很有趣。

于 2010-11-26T10:55:08.200 回答
1

你的问题不完整。我假设您的意思是 GHC，并且至少在没有优化的情况下答案是“是”，因为工作函数（facRec在第一个或fac第二个中）与一个相比具有 2 的数量，并且程序集将反映这一点。通过优化或 JHC，答案可能是“否”。

于 2010-11-26T03:54:26.223 回答