resueltos - multiplicar haskell
¿Por qué este código Haskell funciona con éxito con listas infinitas? (4)
Mi comprensión de foldr es que recorrerá cada elemento de la lista (y quizás esa comprensión sea incompleta).
foldr (a diferencia de foldl ) no tiene que recorrer todos los elementos de la lista. Es instructivo observar cómo se define foldr .
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Cuando se evalúa una llamada a foldr , se fuerza la evaluación de una llamada a la función f . Pero observe cómo la llamada recursiva a foldr está integrada en un argumento de la función f . Esa llamada recursiva no se evalúa si f no evalúa su segundo argumento.
Tengo un código Haskell que funciona correctamente en una lista infinita, pero no entiendo por qué puede hacerlo con éxito. (Modifiqué mi código original, que no manejaba listas infinitas, para incorporar algo de otro código en línea, y de repente veo que funciona pero no sé por qué).
myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldr step False list
where
step item acc = p item || acc
Mi comprensión de foldr es que recorrerá cada elemento de la lista (y quizás esa comprensión sea incompleta). Si es así, no debería importar cómo se redacte la función "paso" ... el código no debería ser capaz de manejar bucles infinitos.
Sin embargo, los siguientes trabajos:
*Main Data.List> myAny even [1..]
True
Por favor, ayúdame a entender: ¿por qué?
El punto clave aquí es que Haskell es un lenguaje no estricto. "No estricto" significa que permite funciones no estrictas, lo que a su vez significa que los parámetros de la función pueden no evaluarse por completo antes de que puedan ser utilizados. Obviamente, esto permite una evaluación perezosa, que es "una técnica para retrasar un cálculo hasta que se requiera el resultado".
Comience desde este artículo de Wiki
Hagamos un pequeño rastro en nuestras cabezas de cómo Haskell evaluará su expresión. Sustituyendo equals por iguales en cada línea, la expresión se evalúa rápidamente como True:
myAny even [1..]
foldr step False [1..]
step 1 (foldr step False [2..])
even 1 || (foldr step False [2..])
False || (foldr step False [2..])
foldr step False [2..]
step 2 (foldr step False [3..])
even 2 || (foldr step False [3..])
True || (foldr step false [3..])
True
Esto funciona porque acc se pasa como un thunk no evaluado (evaluación diferida), pero también porque || la función es estricta en su primer argumento.
Entonces esto termina:
True || and (repeat True)
Pero esto no:
and (repeat True) || True
Mira la definición de || para ver por qué este es el caso:
True || _ = True
False || x = x
No conozco a Haskell, pero sospecho que en su caso, funciona debido a una evaluación perezosa. Debido a que le permite trabajar con una lista infinitamente larga, cuando acceda a ella, calculará el resultado a medida que lo necesite.