Haskell: repite una función una gran cantidad de veces sin stackoverflow

Question

Como novato en Haskell, estoy intentando iterar una función (por ejemplo, el mapa logístico) una gran cantidad de veces. En un lenguaje imperativo, este sería un bucle simple, sin embargo, en Haskell termino con desbordamiento de pila. Tomemos por ejemplo el código:

main = print $ iter 1000000 

f x = 4.0*x*(1.0-x) 

iter :: Int -> Double 
iter 0 = 0.3 
iter n = f $ iter (n-1) 

Para un pequeño número de iteraciones funciona el código, pero por un millón de iteraciones consigo un desbordamiento de espacio de pila:

Stack space overflow: current size 8388608 bytes. 
Use `+RTS -Ksize -RTS' to increase it. 

No puedo entender por qué sucede esto. La recursividad de la cola debería estar bien aquí. Tal vez el problema es la evaluación perezosa. Experimenté con varias formas de forzar una evaluación estricta, insertando $! o seq en varias posiciones, pero sin éxito.

¿Cuál sería la forma de Haskell de iterar una función una gran cantidad de veces?

He tratado sugerencias de los mensajes relacionados: here o here, pero siempre terminaba con stackoverflow para un gran número de iteraciones, por ejemplo, main = print $ iterate f 0.3 !! 1000000.

Answer 1

El problema es que su definición

iter :: Int -> Double 
iter 0 = 0.3 
iter n = f $ iter (n-1) 

trata de evaluar en la dirección equivocada. Desplegado por unos pasos, obtener

iter n = f (iter (n-1)) 
     = f (f (iter (n-2))) 
     = f (f (f (iter (n-3)))) 
     ... 

y toda la pila de llamada de iter 1000000 a iter 0 tiene que ser construido antes de que algo se puede evaluar. Sería lo mismo en un lenguaje estricto. Tienes que organizarlo para que parte de la evaluación pueda tener lugar antes de recurrir. La forma más habitual es tener un parámetro de acumulación, como

iter n = go n 0.3 
    where 
    go 0 x = x 
    go k x = go (k-1) (f x) 

A continuación, añadir anotaciones rigurosidad - en caso de que el compilador no tiene ya añadirlos - hará que funcione sin problemas sin consumir pila.

La variante iterate tiene el mismo problema que su iter, sólo la pila de llamadas está construida de adentro hacia afuera en lugar de afuera hacia adentro como para la suya. Pero desde iterate construye su pila de llamadas de dentro a fuera, una versión más estricta de iterate (o un patrón de consumo en iteraciones anteriores se ven obligados antes) resuelve el problema,

iterate' :: (a -> a) -> a -> [a] 
iterate' f x = x `seq` (x : iterate' f (f x)) 

calcula iterate' f 0.3 !! 1000000 sin problema.