蓄电池在Haskell

在Haskell，如果我写蓄电池在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来运行计算而不是首先编译它，那么答案是否会改变？

来源

2010-11-26 Inaimathi

你对“确实发生了什么不同”的定义是什么？微不足道的答案是“是”，因为它们是不同的 - 一个是尾递归，另一个不是。但我不认为这就是你要求的..？ – lijie 2010-11-26 05:29:25

您是不是指facRec n acc = facRec（n-1）（acc * n）？ – 2010-11-26 10:38:42

@lijie - 我主要感兴趣的是GHC是否会调用优化（有或没有累加器），但是我把它留给了一般，因为我老实说不确定尾递归如何与懒惰语言交互，并且可能会做其他不同基于我使用一种形式与另一种形式的东西。我不知道其他的东西是什么。 – Inaimathi 2010-11-26 12:23:20

尾递归确实在（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-26 14:54:37 nominolo

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

来源

2010-11-26 03:54:26

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

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

要了解事情发生的方式是不同的（或不是），最好的方法是检查生成的核心语言，a good blog post from Don Stewart explains things。顺便说一下，如果您对表演感兴趣，他的许多博文都很有趣。

来源

2010-11-26 10:55:08

蓄电池在Haskell

回答

相关问题