haskell - haskell 中的累加器

Question

在 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，答案是否会改变？运行计算而不是先编译它？

Answer 1

如果您的累加器是严格的，尾递归在 (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 找到编译后的代码，它将使用它，否则它将使用执行少量优化的字节码解释器，所以不要指望会发生任何花哨的优化。