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]并避免整个事情,但我对如何尝试使用懒惰语言进行尾递归感兴趣.我知道我仍然可以获得堆栈溢出,因为thunks正在构建,但是当我使用累加器时,实际发生的事情实际上是不同的(就最终的编译程序而言)而不是我刚才说出的天真递归？除了提高可读性之外,遗漏尾递归是否有任何好处？如果我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找到编译的代码,它将使用它,否则它将使用执行少量优化的字节码解释器,因此不要指望任何奇特的优化发生.