comportamiento foldl versus foldr con listas infinitas

El código para la función myAny en esta pregunta usa foldr. Deja de procesar una lista infinita cuando se cumple el predicado.

Lo reescribí usando foldl:

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldl step False list
   where
      step acc item = p item || acc

(Tenga en cuenta que los argumentos de la función de paso se invierten correctamente).

Sin embargo, ya no deja de procesar listas infinitas.

Intenté rastrear la ejecución de la función como en la respuesta de Apocalisp :

myAny even [1..]
foldl step False [1..]
step (foldl step False [2..]) 1
even 1 || (foldl step False [2..])
False  || (foldl step False [2..])
foldl step False [2..]
step (foldl step False [3..]) 2
even 2 || (foldl step False [3..])
True   || (foldl step False [3..])
True

Sin embargo, esta no es la forma en que se comporta la función. ¿Cómo está mal esto?

Las folddiferencias parecen ser una fuente frecuente de confusión, así que aquí hay una descripción más general:

Considere doblar una lista de n valores [x1, x2, x3, x4 ... xn ]con alguna función fy semilla z.

foldl es:

• Izquierda asociativa :f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Cola recursiva : itera a través de la lista, produciendo el valor después
• Perezoso : nada se evalúa hasta que se necesita el resultado
• Al revés :foldl (flip (:)) [] invierte una lista.

foldr es:

• Derecho asociativo :f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
• Recursivo en una discusión : cada iteración se aplica fal siguiente valor y al resultado de plegar el resto de la lista.
• Perezoso : nada se evalúa hasta que se necesita el resultado
• Adelante :foldr (:) [] devuelve una lista sin cambios.

Aquí hay un punto ligeramente sutil que a veces hace tropezar a las personas: porque foldles al revés cada aplicación de fse agrega al exterior del resultado; y debido a que es vago , no se evalúa nada hasta que se requiere el resultado. Esto significa que para calcular cualquier parte del resultado, Haskell primero itera a través de la lista completa construyendo una expresión de aplicaciones de funciones anidadas, luego evalúa la función más externa , evaluando sus argumentos según sea necesario. Si fsiempre usa su primer argumento, esto significa que Haskell tiene que recurrir hasta el término más interno, luego trabajar hacia atrás calculando cada aplicación def .

Obviamente, esto está muy lejos de la eficiente recursión de cola que la mayoría de los programadores funcionales conocen y aman.

De hecho, a pesar de que foldles técnicamente recursivo, porque toda la expresión del resultado se construye antes de evaluar cualquier cosa,foldl puede causar un desbordamiento de la pila!

Por otro lado, considere foldr. También es vago, pero debido a que se ejecuta hacia adelante , cada aplicación de fse agrega al interior del resultado. Entonces, para calcular el resultado, Haskell construye una aplicación de función única , cuyo segundo argumento es el resto de la lista plegada. Si fes flojo en su segundo argumento, un constructor de datos, por ejemplo, el resultado será incrementalmente flojo , y cada paso del pliegue se computará solo cuando se evalúe una parte del resultado que lo necesita.

Entonces, podemos ver por qué a foldrveces funciona en listas infinitas cuando foldlno lo hace: la primera puede convertir perezosamente una lista infinita en otra estructura de datos infinita perezosa, mientras que la segunda debe inspeccionar toda la lista para generar cualquier parte del resultado. Por otro lado, foldrcon una función que necesita ambos argumentos de forma inmediata, como (+), funciona (o más bien, no funciona) de forma muy similar a foldlconstruir una gran expresión antes de evaluarla.

Entonces, los dos puntos importantes a tener en cuenta son estos:

• foldr puede transformar una estructura de datos recursiva perezosa en otra.
• De lo contrario, los pliegues perezosos se bloquearán con un desbordamiento de pila en listas grandes o infinitas.

Es posible que haya notado que parece que foldrpuede hacer todo lo foldlposible, y más. ¡Esto es verdad! De hecho, ¡ foldl es casi inútil!

Pero, ¿qué sucede si queremos producir un resultado no perezoso al plegar una lista grande (pero no infinita)? Para esto, queremos un pliegue estricto , que las bibliotecas estándar proporcionan cuidadosamente :

foldl' es:

• Izquierda asociativa :f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Cola recursiva : itera a través de la lista, produciendo el valor después
• Estricto : cada aplicación de función se evalúa a lo largo del camino
• Al revés :foldl' (flip (:)) [] invierte una lista.

Debido a que foldl'es estricto , para calcular el resultado, Haskell evaluará f en cada paso, en lugar de dejar que el argumento izquierdo acumule una expresión enorme y sin evaluar. ¡Esto nos da la recurrencia de cola usual y eficiente que queremos! En otras palabras:

• foldl' puede plegar listas grandes de manera eficiente.
• foldl' se colgará en un bucle infinito (no causará un desbordamiento de pila) en una lista infinita.

El wiki de Haskell también tiene una página que discute esto .

myAny even [1..]
foldl step False [1..]
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]

etc.

Intuitivamente, foldlsiempre está en el "exterior" o en la "izquierda", por lo que se expande primero. Indefinidamente.

Puede ver en la documentación de Haskell aquí que foldl es recursivo en la cola y nunca terminará si se pasa una lista infinita, ya que se llama a sí mismo en el siguiente parámetro antes de devolver un valor ...

No conozco a Haskell, pero en Scheme, fold-rightsiempre "actuaré" en el último elemento de una lista primero. Por lo tanto, no funcionará para la lista cíclica (que es lo mismo que una infinita).

No estoy seguro de si fold-rightse puede escribir recursivo de cola, pero para cualquier lista cíclica debería obtener un desbordamiento de pila. fold-leftOTOH normalmente se implementa con recursión de cola, y simplemente se atascará en un bucle infinito, si no lo termina antes de tiempo.