Haskell中的累加器 [英] Accumulators in haskell

问题描述

在Haskell中，如果我写的是

  fac n = facRec n 1 
其中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 来运行计算而不是先编译它，那么答案是否会改变？

解决方案

如果你的累加器是严格的，尾递归确实在（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 does 做尾部调用优化，因此 facRec 调用使用常量堆栈空间。

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

关于第二部分， runhaskell / runghc 是只是GHCi的封装。如果GHCi发现编译后的代码，它将使用它，否则它将使用执行少量优化的字节码解释器，所以不要期望发生任何花俏的优化。

In Haskell, if I write

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

and compile it with GHC, will the result be any different than if I used

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

I could easily do fac n = product [1..n] and avoid the whole thing, but I'm interested in how an attempt at tail recursion works out in a lazy language. I get that I can still get a stack overflow because thunks are building up, but does anything actually happen differently (in terms of the resulting compiled program) when I use an accumulator than when I just state the naive recursion? Is there any benefit to leaving out the tail recursion other than improved legibility? Does the answer change at all if I'm using runhaskell to run the computation instead of compiling it first?

解决方案

Tail recursion does make sense in (GHC) Haskell if your accumulator is strict. To demonstrate the problem, here is a "trace" of your tail-recursive definition of 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

The indentation level corresponds (roughly) to stack level. Note that the accumulator is only evaluated at the very end, and that may cause a stack overflow. The trick, of course, is to make the accumulator strict. It's theoretically possible to show that facRec is strict if it is called in a strict context, but I am not aware of any compiler that does that, ATM. GHC does do tail call optimisation, though, so the facRec calls use constant stack space.

For the same reason foldl' is usually preferred over foldl, since the former is strict in the accumulator.

Regarding your second part, runhaskell/runghc is just a wrapper over GHCi. If GHCi finds compiled code it will use that, otherwise it will use the bytecode interpreter which performs few optimisations, so don't expect any fancy optimisations to happen.

这篇关于Haskell中的累加器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！