如何避免Haskell堆栈溢出? [英] How to avoid stack overflow in Haskell?
问题描述
import System。时间
nSeconds = 5
main = do
initTime< - totalPicoSeconds`fmap` getClockTime
doWork initTime 1
其中
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 - >整数
totalPicoSeconds(TOD ab)= a * 10 ^ 12 + b
5秒,但最终我得到:
lockquote
堆栈空间溢出:当前大小8388608字节。 `+ RTS -Ksize -RTS'来增加它。
手动管理堆栈大小可能有助于特殊情况,但如果我愿意希望运行此算法10秒钟,它可能会再次溢出。所以这不是一个解决方案。我怎么能得到这个代码工作?
这里的问题不是递归,而是你的<$ c $懒惰c> n 参数。 Haskell中的堆栈溢出来自于试图评估深度嵌套的thunk;在你的情况下,每次调用 doWork initTime(n + 1)
都会在第二个参数中创建一个稍微更深的嵌套thunk。简单地说它很严格,而且事情应该会很快乐: doWork initTime $! n + 1
。
Haskell does not support cycling for computation, instead it offers to use recursion algorithms. But this approach leads to growing of stack, and even stack overflow. I believe there should be approach to solve this problem in general. Here is the sample. I wanted to know, how many times getClockTime may be called per 5 seconds:
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
The program goes 5 seconds, but eventually I'm getting:
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
Manual management of stack size may help in particular case, but if I would wish to run this algo for 10 seconds, it may overflow again. So this is not a solution. How can I get this code working?
The problem here is not the recursion, but the laziness of your n
argument. Stack overflows in Haskell come from trying to evaluate deeply-nested thunks; in your case, each call to doWork initTime (n+1)
is making a slightly-deeperly-nested thunk in the second argument. Simply make it strict, and things should be happy again: doWork initTime $! n+1
.
这篇关于如何避免Haskell堆栈溢出?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!