¿Por qué este código Haskell funciona correctamente con listas infinitas?

Question

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 tal vez esa comprensión esté incompleta). Si es así, no debería importar cómo el '' paso '' la función está redactada ... el código no debería poder manejar bucles infinitos.

Sin embargo, lo siguiente funciona:

*Main Data.List> myAny even [1..]
True

Por favor, ayúdame a entender: ¿por qué?

Answer 1

Hagamos un pequeño rastro en nuestras cabezas de cómo Haskell evaluará su expresión. Sustituyendo iguales por iguales en cada línea, la expresión se evalúa rápidamente como Verdadero:

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

Answer 2

  

Mi comprensión de foldr es que   recorrerá cada elemento del   lista (y tal vez esa comprensión   está incompleto).

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 , fuerza la evaluación de una llamada a la función f . Pero observe cómo la llamada recursiva a foldr se incrusta en un argumento de la función f . Esa llamada recursiva no se evalúa si f no evalúa su segundo argumento.

Answer 3

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 completamente antes de que puedan usarse. Obviamente, esto permite una evaluación diferida, que es una técnica para retrasar un cálculo hasta que se requiera el resultado.

Comience desde este artículo de Wiki

Answer 4

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 según lo necesite.

Ver http://en.wikipedia.org/wiki/Lazy_evaluation