如何避免Haskell堆栈溢出？ [英] How to avoid stack overflow in Haskell?

问题描述

Haskell不支持循环计算，而是提供使用递归算法。但是这种方法导致堆栈增长，甚至堆栈溢出。我认为总体上应该有解决这个问题的方法。这是示例。我想知道，每5秒可以调用多少次 getClockTime ：

  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屋！