haskell - comportamiento foldl versus foldr con listas infinitas
lazy-evaluation combinators (4)
En la documentación de Haskell se puede ver que foldl es recursivo de cola y nunca terminará si pasa una lista infinita, ya que se llama al siguiente parámetro antes de devolver un valor ...
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 para la función de paso se invierten correctamente.)
Sin embargo, ya no detiene el procesamiento de 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á esto mal?
La forma en que fold s differ parece 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 f semilla z .
foldl es:
- Asociativo izquierdo :
f ( ... (f (f (f (fz x1) x2) x3) x4) ...) xn - Cola recursiva : itera a través de la lista, produciendo el valor después
- Lazy : nada se evalúa hasta que se necesita el resultado
- Al revés :
foldl (flip (:)) []invierte una lista.
foldr es:
- Asociativo derecho :
f x1 (f x2 (f x3 (f x4 ... (f xn z) ... ))) - Recursivo en un argumento : cada iteración aplica
fal siguiente valor y el resultado de doblar el resto de la lista. - Lazy : nada se evalúa hasta que se necesita el resultado
- Forwards :
foldr (:) []devuelve una lista sin cambios.
Aquí hay un punto ligeramente sutil que ocasionalmente hace que la foldl se foldl : foldl que foldl está hacia atrás, cada aplicación de f se agrega al exterior del resultado; y porque es flojo , nada se evalúa hasta que se requiera el resultado. Esto significa que para calcular cualquier parte del resultado, Haskell itera primero 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 f siempre 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 de f .
¡Esto obviamente está muy lejos de la eficiente recursión de cola que la mayoría de los programadores funcionales conocen y aman!
De hecho, aunque foldl es técnicamente recursivo de cola, debido a que toda la expresión de resultados se construye antes de evaluar cualquier cosa, foldl puede causar un desbordamiento de la pila.
Por otro lado, considere foldr . También es flojo, pero como se ejecuta hacia adelante , cada aplicación de f se 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 f es perezosa en su segundo argumento, un constructor de datos, por ejemplo, el resultado será gradualmente vago , con cada paso del pliegue calculado solo cuando se evalúa una parte del resultado que lo necesita.
Entonces podemos ver por qué foldr veces funciona en listas infinitas cuando foldl no: El primero puede convertir una lista infinita en otra estructura de datos infinita perezosa, mientras que el último debe inspeccionar toda la lista para generar cualquier parte del resultado. Por otro lado, foldr con una función que necesita ambos argumentos inmediatamente, como (+) , funciona (o más bien, no funciona) de manera muy similar a foldl , construyendo una enorme expresión antes de evaluarla.
Entonces, los dos puntos importantes a tener en cuenta son estos:
-
foldrpuede transformar una estructura de datos recursiva perezosa en otra. - De lo contrario, los pliegues perezosos se bloquean con un desbordamiento de pila en listas grandes o infinitas.
Puede haber notado que suena como foldr puede hacer todo lo que foldl puede, y más. ¡Esto es verdad! De hecho, ¡ foldl es casi inútil!
Pero, ¿y si queremos producir un resultado no perezoso doblando una lista grande (pero no infinita)? Para esto, queremos un doblez estricto , que las bibliotecas estándar ofrecen :
foldl'' es:
- Asociativo izquierdo :
f ( ... (f (f (f (fz 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 de la izquierda acumule una expresión enorme, no evaluada. ¡Esto nos da la recursión de cola usual y eficiente que queremos! En otras palabras:
-
foldl''puede doblar listas grandes de manera eficiente. -
foldl''se colgará en un bucle infinito (no causará un desbordamiento de la pila) en una lista infinita.
La wiki de Haskell también tiene una página discutiendo esto .
No conozco a Haskell, pero en Scheme, fold-right siempre ''actuará'' en el último elemento de una lista primero. Por lo tanto, no funcionará para la lista cíclica (que es igual a una lista infinita).
No estoy seguro de si fold-right puede escribirse recursivo de cola, pero para cualquier lista cíclica debería obtener un desbordamiento de pila. fold-left OTOH se implementa normalmente con recursividad de cola, y se quedará atascado en un bucle infinito, si no lo termina temprano.
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, foldl siempre está en "afuera" o en "izquierda", por lo que se expande primero. Indefinidamente.