foldl frente al comportamiento foldr con listas infinitas

Question

El código de la función myAny en usos a esta pregunta foldr. Se deja de procesar una lista infinita cuando se satisface el predicado.

Me volvió a escribir 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.

Me trató de trazar la ejecución de la función como en de Apocalisp respuesta :

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 las funciones se comporta. ¿Cómo es esto malo?

Answer 1

¿Cómo difieren folds parece ser una fuente frecuente de confusión, así que aquí tiene una visión más general:

Considere el plegado de una lista de valores de n [x1, x2, x3, x4 ... xn ] con algunos f función y semilla z.

foldl es:

• Izquierda asociativo : f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• cola recursiva : Se itera por la lista, produciendo el valor después
• Lazy : Nada se evalúa hasta que se necesite 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) ... )))
• recursiva en una discusión . Cada iteración se aplica f al siguiente valor y el resultado de doblar el resto de la lista
• Lazy : Nada se evalúa hasta que se necesite el resultado
• Delanteros :. Retornos foldr (:) [] una lista sin cambios

Hay un punto ligeramente sutil aquí que los viajes a la gente a veces: Debido foldl es hacia atrás de cada aplicación de f se añade a la fuera del resultado; y porque es perezosa , no se evalúa hasta que se requiera el resultado. Esto significa que para calcular cualquier parte del resultado, primeros itera Haskell a través de la lista entera construir una expresión de aplicaciones de funciones anidadas, a continuación, se evalúa la más externa función, la evaluación de sus argumentos como necesario. Si f siempre utiliza su primer argumento, esto significa Haskell tiene que Recurse todo el camino hasta el término más interna, a continuación, trabajar hacia atrás calcular cada aplicación de f.

Esto es obviamente algo muy distinto de la eficiencia de la cola-recursividad programadores más funcionales conocen y aman!

De hecho, a pesar de que es técnicamente foldl recursiva de cola, ya que toda la expresión resultado se construyó antes de evaluar cualquier cosa, foldl puede causar un desbordamiento de pila!

Por otro lado, considere foldr. También es perezoso, pero ya que se ejecuta hacia delante , que se añade cada aplicación de f a la dentro de del resultado. Por lo tanto, para calcular el resultado, Haskell construye un solo aplicación de función, el segundo argumento de que es el resto de la lista plegada. Si f es perezoso en su segundo argumento - un constructor de datos, por ejemplo - el resultado será incrementalmente perezoso , con cada paso del pliegue calcula sólo cuando alguna parte del resultado que las necesidades es evaluados.

Por lo que podemos ver por qué foldr trabaja a veces en las listas infinitas cuando foldl no: El primero puede convertir perezosamente una lista infinita en otra estructura de datos infinita pereza, mientras que este último debe inspeccionar toda la lista para generar cualquier parte del resultado . Por otro lado, foldr con una función que necesita dos argumentos de inmediato, como (+), obras (o más bien, no funciona) al igual que foldl, la construcción de una enorme expresión antes de su evaluación.

Así que los dos puntos importante tener en cuenta son los siguientes:

• foldr puede transformar una estructura de datos recursiva vago en otro.
• De lo contrario, pliegues perezosos chocarán con un desbordamiento de pila en las listas de grandes o infinitos.

Usted puede haber notado que suena como foldr puede hacer todo foldl puede, además de más. ¡Esto es verdad! De hecho, foldl es casi inútil!

Pero lo que si queremos producir un resultado no perezoso plegando una lista grande (pero no infinito)? Por esto, queremos un pliegue estricta , WHICH las bibliotecas estándar thoughfully proporcionar :

foldl' es:

• Izquierda asociativo : f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• cola recursiva : Se itera por la lista, produciendo el valor después
• Estricto : Cada aplicación de función se evalúa a lo largo de la manera
• Al revés . foldl' (flip (:)) [] invierte una lista

Debido foldl' es estricta , para calcular el resultado Haskell evaluar f en cada paso, en lugar de dejar que el argumento de la izquierda acumular una gran expresión, sin evaluar. Esto nos da la recursividad de costumbre, cola eficiente que queremos! En otras palabras:

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

El wiki de Haskell tiene una página de discusión de este , también.

Answer 2

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 es siempre en el "exterior" o en la "izquierda" por lo que se amplió por primera vez. Ad infinitum.

Answer 3

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

Answer 4

No sé Haskell, pero en el esquema, fold-right será siempre 'actuar' en el último elemento de una lista en primer lugar. Por lo tanto es no funcionará para lista cíclico (que es el mismo que un uno infinito).

No estoy seguro de si se puede escribir fold-right recursiva de cola, pero para cualquier lista cíclica que debe recibir un desbordamiento de pila. fold-left otoh normalmente se implementa con la recursión de cola, y se acaba de quedar atrapado en un bucle infinito, si no terminar a tiempo.