¿El mapa de Haskell no es perezoso?

monads lazy-evaluation

Question

ACTUALIZACIÓN: Bueno, esta pregunta se vuelve potencialmente muy sencilla.

q <- mapM return [1..]

¿Por qué esto nunca vuelve?

¿MapM no trata perezosamente con listas infinitas?

El siguiente código cuelga. Sin embargo, si reemplazo la línea A por la línea B, ya no se bloquea. Alternativamente, si precedo la línea A por un "splitRandom $", tampoco se bloquea.

Q1 es: ¿MapM no es perezoso? De lo contrario, ¿por qué reemplazar la línea A con la línea B "arregla esto" código?

P2 es: ¿Por qué la línea A precedente con splitRandom "resuelve" el problema?

import Control.Monad.Random
import Control.Applicative

f :: (RandomGen g) => Rand g (Double, [Double])
f = do
    b <- splitRandom $ sequence $ repeat $ getRandom
    c <- mapM return b -- A
    -- let c = map id b -- B
    a <- getRandom
    return (a, c)

splitRandom :: (RandomGen g) => Rand g a -> Rand g a
splitRandom code = evalRand code <$> getSplit

t0 = do
    (a, b) <- evalRand f <$> newStdGen
    print  a
    print (take 3 b)

El código genera una lista infinita de números aleatorios perezosamente. Entonces genera un solo número aleatorio. Al usar splitRandom, puedo evaluar este último número aleatorio antes de la lista infinita. Esto se puede demostrar si devuelvo b en lugar de c en la función.

Sin embargo, si aplico el mapM a la lista, el programa ahora se bloquea. Para evitar que se cuelgue, tengo que aplicar splitRandom nuevamente antes del mapM. Tenía la impresión de que mapM puede perezosamente

Answer 1

Bueno, esta pregunta se vuelve potencialmente muy sencilla.

q <- mapM return [1 ..]

¿Por qué esto nunca vuelve?

No es necesariamente cierto. Depende de la mónada en la que estés.

Por ejemplo, con la mónada de identidad, puede usar el resultado perezosamente y termina bien:

newtype Identity a = Identity a

instance Monad Identity where
  Identity x >>= k = k x
  return = Identity

-- "foo" is the infinite list of all the positive integers
foo :: [Integer]
Identity foo = do
  q <- mapM return [1..]
  return q

main :: IO ()
main = print $ take 20 foo -- [1 .. 20]

Answer 2

Aquí hay un intento de probar que mapM return [1..] no termina. Supongamos por el momento que estamos en la mónada de Identity (el argumento se aplicará a cualquier otra mónada también):

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 ahora tan bueno...

-- 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)

Recuerde que return a = Identity a en la mónada de Identidad, y (Identity a) >>= f = fa en la Mónada de identidad. Continuo:

-- 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 punto nos encantaría aplicar a /xs , ¡pero aún no podemos! Tenemos que continuar desplegando hasta que tengamos un valor para 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 podemos aplicar a /xs , pero podemos aplicar a /x2 . Continuo:

-- 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 en el que ni /xs ni /xs2 se pueden 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í que puedes ver que, debido a foldr , estamos creando una serie de funciones para aplicar, comenzando desde el final de la lista y trabajando de regreso. 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 , no puedo encontrar cuál en este momento). En la siguiente lista de mónadas:

mebs = [Just 3, Just 4, Nothing]

esperaríamos que la sequence detecte la Nothing y devuelva un error para todo esto:

sequence mebs = Nothing

Sin embargo, para esta lista:

mebs2 = [Just 3, Just 4]

esperaríamos secuencia para darnos:

sequence mebs = Just [3, 4]

En otras palabras, la sequence tiene que ver la lista completa de cálculos monádicos, unirlos y ejecutarlos todos para obtener la respuesta correcta. No hay forma de que la sequence pueda dar una respuesta sin ver la lista completa.

Nota: la versión anterior de esta respuesta afirmó que foldr calcula a partir de la parte posterior de la lista y que no funcionaría en infinitas listas, ¡pero eso es incorrecto! Si el operador que pasa a foldr es perezoso en su segundo argumento y produce una salida con un constructor de datos perezoso como una lista, foldr funcionará felizmente con una lista infinita. Vea foldr (/x xs -> (replicate xx) ++ xs) [] [1...] para ver un ejemplo. Pero ese no es el caso con nuestro operador k .

Answer 3

Bueno, hay perezoso, y luego hay perezoso . mapM es de hecho perezoso, ya que no hace más trabajo del que tiene que hacer. Sin embargo, mira la firma de tipo:

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

Piense qué significa esto: le asigna una función a -> mb y un montón de a s. Un map regular puede convertirlos en un montón de mb s, pero no un m [b] . La única forma de combinar las b s en una sola [b] sin que la mónada se interponga en el camino es usar >>= para secuenciar las mb s para construir la lista .

De hecho, mapM es precisamente equivalente a sequence . map sequence . map

En general, para cualquier expresión monádica, si se usa el valor, se debe forzar toda la cadena de >>= s que conduce a la expresión, por lo que la aplicación de una sequence a una lista infinita nunca podrá terminar.

Si desea trabajar con una secuencia monádica ilimitada, o bien necesitará un control de flujo explícito, por ejemplo, una condición de terminación de bucle integrada en la cadena de enlaces de alguna manera, que las funciones recursivas simples como mapM y la sequence no proporcionan, o una secuencia paso a paso, algo como esto:

data Stream m a = Nil | Stream a (m (Stream m a))

... para que solo fuerce tantas capas de mónada como sea necesario.

Edit :: Respecto a splitRandom , lo que está sucediendo allí es que le está pasando un cálculo de Rand , evaluando que con la splitRandom obtiene, y luego return el resultado. Sin el splitRandom , la semilla utilizada por el único getRandom tiene que venir del resultado final de secuenciar la lista infinita, por lo tanto, se cuelga. Con el splitRandom adicional, la semilla utilizada solo necesita splitRandom través de las dos llamadas splitRandom , por lo que funciona. La lista final de números aleatorios funciona porque has dejado la mónada Rand en ese momento y nada depende de su estado final.

Answer 4

Esta pregunta muestra muy bien la diferencia entre la Mónada IO y otras Mónadas. En el fondo, el mapM construye una expresión con una operación de enlace (>> =) entre todos los elementos de la lista para convertir la lista de expresiones monádicas en una expresión monádica de una lista. Ahora, lo que es diferente en la mónada IO es que el modelo de ejecución de Haskell está ejecutando expresiones durante el enlace en la Mónada IO. Esto es exactamente lo que finalmente obliga (en un mundo puramente perezoso) a ser ejecutado.

Entonces, IO Monad es especial en cierto modo, está utilizando el paradigma de secuencia de enlace para hacer cumplir la ejecución de cada paso y esto es lo que nuestro programa hace para ejecutar cualquier cosa al final. Otras mónadas son diferentes. Tienen otros significados del operador de enlace, dependiendo de la mónada. IO es en realidad la única Mónada que ejecuta las cosas en el enlace y esta es la razón por la que los tipos de IO son "acciones".

El siguiente ejemplo muestra que otras mónadas no imponen la ejecución, por ejemplo, la mónada Maybe. Finalmente, esto indica que un mapM en la IO Monad devuelve una expresión que, cuando se ejecuta, ejecuta cada elemento individual antes de devolver el valor final.

Hay buenos documentos sobre esto, comience aquí o busque semántica denotacional y Mónadas: Abordando al escuadrón torpe: http://research.microsoft.com/en-us/um/people/simonpj/papers/marktoberdorf/mark.pdf

Ejemplo con Maybe Monad:

módulo principal donde

fstMaybe :: [Int] -> Tal vez [Int] fstMaybe = mapM (/ x -> if x == 3 entonces Nothing else Just x)

main = do r = fstMaybe [1 ..] return r

Answer 5

Vamos a hablar de esto en un contexto más genérico.

Como dijeron las otras respuestas, el mapM es solo una combinación de sequence y map . Entonces el problema es por qué la sequence es estricta en ciertas Monad . Sin embargo, esto no está restringido a las Monads sino también a los Applicative , ya que tenemos la sequenceA que comparte la misma implementación de sequence en la mayoría de los casos.

Ahora mire la firma de tipo (especializada para listas) de sequenceA :

sequenceA :: Applicative f => [f a] -> f [a]

¿Cómo harías esto? foldr una lista, por lo que le gustaría usar foldr en esta lista.

sequenceA = foldr f b where ...
  --f :: f a -> f [a] -> f [a]
  --b :: f [a]

Dado que f es un Applicative , usted sabe que b beule be - pure [] . Pero ¿qué es f ? Obviamente es una versión elevada de (:) :

(:) :: a -> [a] -> [a]

Así que ahora sabemos cómo funciona la sequenceA :

sequenceA = foldr f b where
  f a b = (:) <$> a <*> b
  b = pure []

o

sequenceA = foldr ((<*>) . fmap (:)) (pure [])

Supongamos que le dieron una lista perezosa (x:_|_) . La definición anterior de sequenceA da

sequenceA (x:_|_) === (:) <$> x <*> foldr ((<*>) . fmap (:)) (pure []) _|_
                  === (:) <$> x <*> _|_

Así que ahora vemos que el problema se redujo para considerar el clima f <*> _|_ es _|_ o no. Obviamente, si f es estricto, esto es _|_ , pero si f no es estricto, para permitir una detención de la evaluación requerimos que <*> no sea estricto.

Por lo tanto, el criterio para que un funtor aplicativo tenga una sequenceA que se detenga será el operador <*> no estricto. Una prueba simple seria

const a <$> _|_ === _|_      ====> strict sequenceA
-- remember f <$> a === pure f <*> a

Si estamos hablando de Moand s, el criterio es

_|_ >> const a === _|_ ===> strict sequence