¿Es el mapM en Haskell estricto? ¿Por qué este programa obtiene un desbordamiento de pila?

Question

El siguiente programa termina correctamente:

import System.Random 

randomList = mapM (\_->getStdRandom (randomR (0, 50000::Int))) [0..5000] 

main = do 
    randomInts <- randomList 
    print $ take 5 randomInts 

de reproducción:

$ runhaskell test.hs 
[26156,7258,29057,40002,26339] 

Sin embargo, alimentándolo con una lista infinita, el programa nunca termina, y cuando se compila, finalmente, da un error de desbordamiento de pila!

import System.Random 

randomList = mapM (\_->getStdRandom (randomR (0, 50000::Int))) [0..] 

main = do 
    randomInts <- randomList 
    print $ take 5 randomInts 

Correr,

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

que espera que el programa para evaluar perezosamente getStdRandom cada vez que cojo un elemento de la lista, terminando después de hacerlo 5 veces. ¿Por qué está tratando de evaluar toda la lista?

Gracias.

¿Existe alguna forma mejor de obtener una lista infinita de números aleatorios? Quiero pasar esta lista a una función pura.

EDIT: Un poco más de la lectura reveló que la función

randomList r = do g <- getStdGen 
        return $ randomRs r g 

es lo que estaba buscando.

EDIT2: después de leer la respuesta de camccann, me di cuenta de que getStdGen está recibiendo una nueva semilla en cada llamada. En su lugar, mejor usar esta función como un simple generador de lista aleatoria de una sola vez:

import System.Random 

randomList :: Random a => a -> a -> IO [a] 
randomList r g = do s <- newStdGen 
        return $ randomRs (r,g) s 

main = do r <- randomList 0 (50::Int) 
      print $ take 5 r 

Pero sigo sin entender por qué mi mapM llamada no terminó. Evidentemente, no está relacionado con números aleatorios, pero puede que tenga algo que ver con mapM.

Por ejemplo, he encontrado que el siguiente también no termina:

randomList = mapM (\_->return 0) [0..] 

main = do 
    randomInts <- randomList 
    print $ take 50000 randomInts 

lo que da? Por cierto, en mi humilde opinión, la función randomInts anterior debe estar en System.Random. Es extremadamente conveniente poder simplemente generar una lista aleatoria en la mónada IO y pasarla a una función pura cuando sea necesario, no veo por qué esto no debería estar en la biblioteca estándar.

Answer 1

me gustaría hacer algo de la misma familia, randomRs dejando que hacen el trabajo con un RandomGen inicial:

#! /usr/bin/env runhaskell 

import Control.Monad 
import System.Random 


randomList :: RandomGen g => g -> [Int] 
randomList = randomRs (0, 50000) 

main :: IO() 
main = do 
    randomInts <- liftM randomList newStdGen 
    print $ take 5 randomInts 

En cuanto a la pereza, lo que está sucediendo aquí es que mapM es (sequence . map)

Su tipo es: mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]

Está mapeando la función, dando un [m b] y luego necesita ejecutar todas esas acciones para hacer un m [b]. Es la secuencia que nunca pasará por la lista infinita.

Esto se explica mejor en las respuestas a una pregunta previa: Is Haskell's mapM not lazy?

Answer 2

Los números aleatorios en general no son estrictas, pero la unión monádico es - el problema aquí es que mapM tiene que secuenciar toda la lista. Considere su firma tipo, (a -> m b) -> [a] -> m [b]; como esto implica, lo que hace es primero map la lista de tipo [a] en una lista de tipo [m b], luego sequence esa lista para obtener un resultado del tipo m [b]. Por lo tanto, cuando se vincula el resultado de aplicar mapM, , p. poniéndolo en el lado derecho de <-, lo que esto significa es "asignar esta función a la lista, luego ejecutar cada acción monádica y combinar los resultados nuevamente en una sola lista". Si la lista es infinita, esto, por supuesto, no terminará.

Si simplemente desea una secuencia de números aleatorios, debe generar la lista sin utilizar una mónada para cada número. No estoy del todo seguro de por qué ha utilizado el diseño que tiene, pero la idea básica es la siguiente: dado un valor inicial, utilice un generador de números pseudoaleatorios para producir un par de 1) un número aleatorio 2) una nueva semilla , luego repite con la nueva semilla. Cualquier semilla dada, por supuesto, proporcionará la misma secuencia cada vez. Por lo tanto, puede usar la función getStdGen, que proporcionará una semilla nueva en la mónada IO; puedes usar esa semilla para crear una secuencia infinita en un código completamente puro.

De hecho, System.Random proporciona funciones para ese propósito, precisamente, randoms o randomRs en lugar de random y randomR.

Si por alguna razón desea hacerlo usted mismo, lo que quiere es esencialmente un despliegue. La función unfoldr de Data.List tiene el tipo de firma (b -> Maybe (a, b)) -> b -> [a], que es bastante explica por sí mismo: Dado un valor de tipo b, se aplica la función de conseguir ya sea algo del tipo a y un nuevo valor del generador de tipo b o Nothing para indicar la fin de la secuencia

Desea una lista infinita, por lo que nunca tendrá que devolver Nothing. Por lo tanto, aplicando parcialmente randomR al rango deseado y componer con Just da esto:

Just . randomR (0, 50000::Int) :: (RandomGen a) => a -> Maybe (Int, a) 

alimentación que en unfoldr da esto:

unfoldr (Just . randomR (0, 50000::Int)) :: (RandomGen a) => a -> [Int] 

... que hace exactamente lo que dice: Dada una instancia de RandomGen, producirá una lista infinita (y perezosa) de números aleatorios generados a partir de esa semilla.