如何避免Haskell堆棧溢出？

Haskell不支持循環計算，而是提供使用遞歸算法。但是這種方法導致堆棧增長，甚至堆棧溢出。我認爲總體上應該有解決這個問題的方法。這是示例。我想知道，多少次getClockTime可每5秒被稱爲：如何避免Haskell堆棧溢出？

import System.Time 

nSeconds = 5 

main = do 
    initTime <- totalPicoSeconds `fmap` getClockTime 
    doWork initTime 1 
    where 
    doWork initTime n = do 
     currTime <- totalPicoSeconds `fmap` getClockTime 
     if (currTime - initTime) `div` 10^12 >= nSeconds 
      then print n 
      else doWork initTime (n+1) 

totalPicoSeconds :: ClockTime -> Integer 
totalPicoSeconds (TOD a b) = a * 10^12 + b

程序的進展5秒，但最終我得到：

堆棧溢出空間：目前的規模8388608字節。
使用`+ RTS -Ksize -RTS'來增加它。

手動管理堆棧大小可能有助於特殊情況，但如果我希望運行此算法10秒鐘，它可能會再次溢出。所以這不是一個解決方案。我怎樣才能使這個代碼工作？

來源

2011-09-23 Dmitry Bespalov

這不是尾巴遞歸嗎？爲什麼堆棧增長？ – Swiss

您是否使用或不使用優化進行編譯？ – fuz

@Swiss是的，它是尾遞歸的，但是增長的堆棧不是你認爲正在增長的堆棧。 –

這裏的問題不是遞歸，而是你的懶惰的論點。 Haskell中的堆棧溢出來自於試圖評估深度嵌套的thunk;在你的情況下，每次調用doWork initTime (n+1)都會在第二個參數中產生一個稍微更深的嵌套thunk。簡單地說，嚴格的，事情應該再次開心：doWork initTime $! n+1。

來源

2011-09-23 20:43:38

它的工作原理。大！ –

非常漂亮！ – acfoltzer

P.S.這裏的信用歸功於Brent Yorgey，他幾乎在三年前幫助我調試了一些代碼中幾乎相同的錯誤。 –

如何避免Haskell堆棧溢出？

回答

相關問題