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

Question

Tengo un código de Haskell que funciona 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 hará un bucle a través de cada elemento de la lista (y tal vez que la comprensión es 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, las siguientes obras:

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

Por favor, me ayudan a entender: ¿por qué ??

Answer 1

Vamos a hacer un poco rastro en la cabeza de la forma en Haskell evaluará su expresión. Sustituyendo es igual a los iguales en cada línea, la expresión se evalúa con bastante rapidez a 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 golpe seco sin evaluar (evaluación perezosa), sino también porque la función || es estricta en su primera argumento.

Así que esto termina:

True || and (repeat True) 

pero esto no significa:

and (repeat True) || True 

Mira la definición de || ver por qué este es el caso:

True || _ = True 
False || x = x 

Answer 2

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".

inicio de this Wiki article

Answer 3

no sé Haskell, pero sospecho que, en su caso, funciona debido a la 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.

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

Answer 4

Mi comprensión de foldr es que voluntad de bucle a través de cada elemento de la lista (y tal vez que la comprensión es 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, obliga a la evaluación de una llamada a la función f. Pero tenga en cuenta cómo la llamada recursiva a foldr está incrustada en un argumento a la función f. Esa llamada recursiva no se evalúa si f no evalúa su segundo argumento.