¿Cómo evitar el desbordamiento de pila en Haskell?

recursion stack-overflow

Question

Haskell no admite el ciclo para la computación, en su lugar, ofrece el uso de algoritmos de recursión. Pero este enfoque lleva al crecimiento de la pila, e incluso al desbordamiento de la pila. Creo que debería haber un enfoque para resolver este problema en general. Aquí está la muestra. Quería saber cuántas veces se puede llamar a getClockTime por 5 segundos:

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

El programa dura 5 segundos, pero eventualmente estoy recibiendo:

Desbordamiento de espacio de pila: tamaño actual 8388608 bytes.
Utilice `+ RTS -Ksize -RTS ''para aumentarlo.

La administración manual del tamaño de la pila puede ayudar en un caso particular, pero si quisiera ejecutar este algoritmo durante 10 segundos, podría desbordarse nuevamente. Así que esto no es una solución. ¿Cómo puedo hacer que este código funcione?

Answer 1

El problema aquí no es la recursión, sino la pereza de su argumento n . Los desbordamientos de pila en Haskell provienen de intentar evaluar thunks profundamente anidados; en su caso, cada llamada a doWork initTime (n+1) está haciendo un thunk un poco más profundo en el segundo argumento. Simplemente doWork initTime $! n+1 estricto, y las cosas deberían volver a ser felices: doWork initTime $! n+1 doWork initTime $! n+1 .