蓄電池在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

回答

相關問題