Aquí hay un intento de prueba de que mapM return [1..] no finaliza. Supongamos por el momento que estamos en el Identity mónada (el argumento se aplicará a cualquier otra mónada igual de bien):
mapM return [1..] -- initial expression
sequence (map return [1 ..]) -- unfold mapM
let k m m' = m >>= \x ->
m' >>= \xs ->
return (x : xs)
in foldr k (return []) (map return [1..]) -- unfold sequence
Hasta aquí todo bien ...
-- unfold foldr
let k m m' = m >>= \x ->
m' >>= \xs ->
return (x : xs)
go [] = return []
go (y:ys) = k y (go ys)
in go (map return [1..])
-- unfold map so we have enough of a list to pattern-match go:
go (return 1 : map return [2..])
-- unfold go:
k (return 1) (go (map return [2..])
-- unfold k:
(return 1) >>= \x -> go (map return [2..]) >>= \xs -> return (x:xs)
Recordemos que return a = Identity a en la mónada Identity y (Identity a) >>= f = f a en la mónada Identity. Continuando:
-- unfold >>= :
(\x -> go (map return [2..]) >>= \xs -> return (x:xs)) 1
-- apply 1 to \x -> ... :
go (map return [2..]) >>= \xs -> return (1:xs)
-- unfold >>= :
(\xs -> return (1:xs)) (go (map return [2..]))
Tenga en cuenta que en este momento nos encantaría aplicará a \xs, pero todavía no puedo! Tenemos que seguir desarrollando su lugar hasta que tengamos un valor de aplicar:
-- unfold map for go:
(\xs -> return (1:xs)) (go (return 2 : map return [3..]))
-- unfold go:
(\xs -> return (1:xs)) (k (return 2) (go (map return [3..])))
-- unfold k:
(\xs -> return (1:xs)) ((return 2) >>= \x2 ->
(go (map return [3..])) >>= \xs2 ->
return (x2:xs2))
-- unfold >>= :
(\xs -> return (1:xs)) ((\x2 -> (go (map return [3...])) >>= \xs2 ->
return (x2:xs2)) 2)
En este punto, todavía no se puede aplicar a \xs, pero podemos aplicar a \x2. Continuando:
-- apply 2 to \x2 :
(\xs -> return (1:xs)) ((go (map return [3...])) >>= \xs2 ->
return (2:xs2))
-- unfold >>= :
(\xs -> return (1:xs)) (\xs2 -> return (2:xs2)) (go (map return [3..]))
Ahora hemos llegado a un punto donde ni \xs\xs2 ni se puede reducir todavía! Nuestra única opción es:
-- unfold map for go, and so on...
(\xs -> return (1:xs))
(\xs2 -> return (2:xs2))
(go ((return 3) : (map return [4..])))
Así se puede ver que, debido a foldr, estamos construyendo una serie de funciones para aplicar, a partir del final de la lista y trabajando nuestro camino de vuelta. Debido a que en cada paso la lista de entrada es infinita, este despliegue nunca terminará y nunca obtendremos una respuesta.
Esto tiene sentido si nos fijamos en este ejemplo (tomado de otro hilo de StackOverflow, no puedo encontrar cuál en este momento).En la siguiente lista de mónadas:
mebs = [Just 3, Just 4, Nothing]
que esperaría sequence para coger el Nothing y devolver un fracaso para todo el asunto:
sequence mebs = Nothing
Sin embargo, para esta lista:
mebs2 = [Just 3, Just 4]
esperaríamos que la secuencia nos diera:
sequence mebs = Just [3, 4]
En otras palabras, sequencetiene para ver toda la lista de cómputos monádicos, encadenarlos y ejecutarlos todos para obtener la respuesta correcta. No hay manera de que sequence pueda dar una respuesta sin ver toda la lista.
Nota: La versión anterior de esta respuesta afirmó que foldr calcula a partir de la parte posterior de la lista, y no funcionaría en absoluto en las listas infinitas, pero eso es incorrecto! Si el operador que pasa al foldr es flojo en su segundo argumento y produce salida con un constructor de datos perezoso como una lista, foldr trabajará felizmente con una lista infinita. Ver foldr (\x xs -> (replicate x x) ++ xs) [] [1...] para un ejemplo. Pero ese no es el caso con nuestro operador k.
Pero esto no explica por qué antes de la línea con splitRandom se resuelve el problema.Además, tenga en cuenta que splitRandom realmente divide la semilla aleatoria en dos y usa una de ellas para generar la lista infinita, por lo que no debería haber una dependencia allí. – qrest
@qrest: Se agregó una nota adicional - ¿eso ayuda? –
@camccann: No, no es así. Aquí está mi razonamiento. Necesito consumir una semilla para generar la lista infinita. Por lo tanto, dividí la semilla y la usé en "splitRandom $ sequence $ repeat $ getRandom". NOTA: ¡Esta es una expresión monádica y no se evaluó por completo! Tenga en cuenta también que intencionalmente obtuve un número aleatorio para "a" DESPUÉS de la lista infinita, lo que demuestra que las semillas no son dependientes. Y la mónada Rand no usa la semilla a menos que se genere un número aleatorio para que no exista una dependencia de semilla. Entonces, ¿el "retorno" es el que realmente fuerza la evaluación? – qrest