optimization - foldl es cola recursiva, entonces, ¿cómo es que foldr se ejecuta más rápido que foldl?

haskell tail-recursion (7)

¡El problema es que la optimización de la recursividad de la cola es una optimización de la memoria, no una optimización del tiempo de ejecución!

La optimización de recursividad de cola evita la necesidad de recordar valores para cada llamada recursiva.

Entonces, foldl es de hecho "bueno" y foldr es "malo".

Por ejemplo, teniendo en cuenta las definiciones de foldr y foldl:

foldl f z [] = z foldl f z (x:xs) = foldl f (z `f` x) xs foldr f z [] = z foldr f z (x:xs) = x `f` (foldr f z xs)

Así es como se evalúa la expresión "foldl (+) 0 [1,2,3]":

foldl (+) 0 [1, 2, 3] foldl (+) (0+1) [2, 3] foldl (+) ((0+1)+2) [3] foldl (+) (((0+1)+2)+3) [ ] (((0+1)+2)+3) ((1+2)+3) (3+3) 6

Tenga en cuenta que foldl no recuerda los valores 0, 1, 2 ..., pero pasa la expresión completa (((0 + 1) +2) +3) como argumento perezosamente y no la evalúa hasta la última evaluación de foldl, donde alcanza el caso base y devuelve el valor pasado como el segundo parámetro (z) que aún no se evalúa.

Por otro lado, así es como funciona foldr:

foldr (+) 0 [1, 2, 3] 1 + (foldr (+) 0 [2, 3]) 1 + (2 + (foldr (+) 0 [3])) 1 + (2 + (3 + (foldr (+) 0 []))) 1 + (2 + (3 + 0))) 1 + (2 + 3) 1 + 5 6

La diferencia importante aquí es que donde foldl evalúa toda la expresión en la última llamada, evitando la necesidad de volver a alcanzar los valores recordados, foldr no. foldr recuerda un número entero para cada llamada y realiza una adición en cada llamada.

Es importante tener en cuenta que foldr y foldl no siempre son equivalentes. Por ejemplo, intente calcular estas expresiones en abrazos:

foldr (&&) True (False:(repeat True)) foldl (&&) True (False:(repeat True))

foldr y foldl son equivalentes solo bajo ciertas condiciones descritas here

(Perdón por mi mal ingles)

Quería probar foldl vs foldr. Por lo que he visto, debes usar foldl sobre foldr siempre que puedas debido a la optimización de la recursión de la cola.

Esto tiene sentido. Sin embargo, después de ejecutar esta prueba, estoy confundido:

foldr (toma 0.057s cuando se usa el comando de tiempo):

a::a -> [a] -> [a] a x = ([x] ++ ) main = putStrLn(show ( sum (foldr a [] [0.. 100000])))

foldl (toma 0.089s cuando se usa el comando de tiempo):

b::[b] -> b -> [b] b xs = ( ++ xs). (/y->[y]) main = putStrLn(show ( sum (foldl b [] [0.. 100000])))

Está claro que este ejemplo es trivial, pero no estoy seguro de por qué foldr está superando a foldl. ¿No debería ser este un caso claro en el que foldl gana?

Bienvenido al mundo de la evaluación perezosa.

Cuando lo piensas en términos de evaluación estricta, foldl se ve "bien" y foldr parece "malo" porque foldl es cola recursiva, pero foldr tendría que construir una torre en la pila para poder procesar primero el último elemento.

Sin embargo, la evaluación perezosa cambia las tornas. Tomemos, por ejemplo, la definición de la función de mapa:

map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs

Esto no sería demasiado bueno si Haskell usara una evaluación estricta, ya que tendría que calcular primero la cola y luego anteponer el ítem (para todos los ítems en la lista). La única forma de hacerlo eficientemente sería construir los elementos al revés, parece.

Sin embargo, gracias a la evaluación perezosa de Haskell, esta función de mapa es realmente eficiente. Las listas en Haskell se pueden considerar generadores, y esta función de mapa genera su primer elemento aplicando f al primer elemento de la lista de entrada. Cuando necesita un segundo elemento, simplemente hace lo mismo otra vez (sin usar espacio adicional).

Resulta que el map se puede describir en términos de foldr :

map f xs = foldr (/x ys -> f x : ys) [] xs

Es difícil saberlo al observarlo, pero la evaluación perezosa se inicia porque foldr puede dar su primer argumento de inmediato:

foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs)

Debido a que f definido por el map puede devolver el primer elemento de la lista de resultados utilizando únicamente el primer parámetro, el doblez puede operar perezosamente en un espacio constante.

Ahora, la evaluación perezosa muerde. Por ejemplo, intente ejecutar sum [1..1000000]. Produce un desbordamiento de pila. ¿Por qué debería? Debería simplemente evaluar de izquierda a derecha, ¿verdad?

Veamos cómo lo evalúa Haskell:

foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs sum = foldl (+) 0 sum [1..1000000] = foldl (+) 0 [1..1000000] = foldl (+) ((+) 0 1) [2..1000000] = foldl (+) ((+) ((+) 0 1) 2) [3..1000000] = foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000] ... = (+) ((+) ((+) (...) 999999) 1000000)

Haskell es demasiado perezoso para realizar las adiciones a medida que avanza. En cambio, termina con una torre de thunks no evaluados que deben ser forzados a obtener un número. El desbordamiento de pila ocurre durante esta evaluación, ya que tiene que recurrirse profundamente para evaluar todos los procesos.

Afortunadamente, hay una función especial en Data.List llamada foldl'' que opera estrictamente. foldl'' (+) 0 [1..1000000] no foldl'' (+) 0 [1..1000000] desbordamiento. (Nota: Intenté reemplazar foldl con foldl'' en tu prueba, pero en realidad lo hizo funcionar más lento).

Bueno, déjame reescribir tus funciones de una manera que la diferencia sea obvia:

a :: a -> [a] -> [a] a = (:) b :: [b] -> b -> [b] b = flip (:)

Ves que b es más complejo que a. Si quiere ser preciso, necesita un paso de reducción para calcular el valor, pero b necesita dos. Eso hace que la diferencia de tiempo que está midiendo, en el segundo ejemplo, dos veces se deben realizar reducciones.

// edit: Pero la complejidad del tiempo es la misma, así que no me molestaría demasiado.

EDITAR: Al volver a ver este problema, creo que todas las explicaciones actuales son algo insuficientes, así que escribí una explicación más larga.

La diferencia está en cómo foldl y foldr aplican su función de reducción. Mirando el caso foldr , podemos expandirlo como

foldr (/x -> [x] ++ ) [] [0..10000] [0] ++ foldr a [] [1..10000] [0] ++ ([1] ++ foldr a [] [2..10000]) ...

Esta lista se procesa por sum , que la consume de la siguiente manera:

sum = foldl'' (+) 0 foldl'' (+) 0 ([0] ++ ([1] ++ ... ++ [10000])) foldl'' (+) 0 (0 : [1] ++ ... ++ [10000]) -- get head of list from ''++'' definition foldl'' (+) 0 ([1] ++ [2] ++ ... ++ [10000]) -- add accumulator and head of list foldl'' (+) 0 (1 : [2] ++ ... ++ [10000]) foldl'' (+) 1 ([2] ++ ... ++ [10000]) ...

He omitido los detalles de la concatenación de la lista, pero así es como procede la reducción. La parte importante es que todo se procesa para minimizar los cruces de lista. El foldr solo atraviesa la lista una vez, las concatenaciones no requieren continuos recorridos de lista, y sum finalmente consume la lista en una sola pasada. Críticamente, el encabezado de la lista está disponible de foldr inmediato a la sum , por lo que la sum puede comenzar a funcionar inmediatamente y los valores se pueden convertir a medida que se generan. Con marcos de fusión como el vector , incluso las listas intermedias probablemente se fusionarán.

Compare esto con la función foldl :

b xs = ( ++xs) . (/y->[y]) foldl b [] [0..10000] foldl b ( [0] ++ [] ) [1..10000] foldl b ( [1] ++ ([0] ++ []) ) [2..10000] foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000] ...

Tenga en cuenta que ahora el encabezado de la lista no está disponible hasta que foldl haya terminado. Esto significa que toda la lista debe construirse en la memoria antes de que la sum pueda comenzar a funcionar. Esto es mucho menos eficiente en general. Ejecutar las dos versiones con +RTS -s muestra un miserable rendimiento de recolección de basura de la versión foldl.

Este también es un caso donde foldl'' no ayudará. El rigor adicional de foldl'' no cambia la forma en que se crea la lista intermedia. El encabezado de la lista no estará disponible hasta que foldl ''haya finalizado, por lo que el resultado será aún más lento que con foldr .

Uso la siguiente regla para determinar la mejor opción de fold

Para los pliegues que son una reducción , use foldl'' (por ejemplo, este será el único / recorrido final)
De lo contrario, use foldr .
No use foldl .

En la mayoría de los casos, foldr es la mejor función de plegado debido a que la dirección transversal es óptima para la evaluación perezosa de listas. También es el único capaz de procesar listas infinitas. El rigor extra de foldl'' puede hacerlo más rápido en algunos casos, pero esto depende de cómo usará esa estructura y qué tan vago es.

Ni foldl ni foldr tienen cola optimizada. Solo es foldl'' .

Pero en su caso, usar ++ con foldl'' no es una buena idea porque la evaluación sucesiva de ++ causará que el acumulador crezca transversalmente una y otra vez.

No creo que nadie haya dicho la verdadera respuesta en este caso, a menos que me esté perdiendo algo (lo cual puede ser cierto y bienvenido con los votos a la baja).

Creo que la diferencia más grande en este caso es que foldr construye la lista así:

[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))

Mientras que foldl construye la lista de esta manera:

((([0] ++ [1]) ++ [2]) ++ ...) ++ [999888]) ++ [999999]) ++ [1000000]

La diferencia es sutil, pero observe que en la versión de foldr ++ siempre tiene solo un elemento de lista como argumento de la izquierda. Con la versión foldl , hay hasta 999999 elementos en el argumento izquierdo de ++ (en promedio alrededor de 500000), pero solo un elemento en el argumento correcto.

Sin embargo, ++ toma tiempo proporcional al tamaño del argumento de la izquierda, ya que tiene que mirar toda la lista de argumentos de la izquierda hasta el final y luego volver a asignar ese último elemento al primer elemento del argumento de la derecha (en el mejor de los casos, tal vez sea necesita hacer una copia). La lista de argumentos correctos no se modifica, por lo que no importa qué tan grande sea.

Es por eso que la versión de foldl es mucho más lenta. No tiene nada que ver con la pereza en mi opinión.

Para a, la lista [0.. 100000] necesita expandirse de inmediato para que foldr pueda comenzar con el último elemento. Luego, cuando pliega las cosas, los resultados intermedios son

[100000] [99999, 100000] [99998, 99999, 100000] ... [0.. 100000] -- i.e., the original list

Como nadie tiene permitido cambiar el valor de esta lista (Haskell es un lenguaje funcional puro), el compilador puede reutilizar el valor de forma gratuita. Los valores intermedios, como [99999, 100000] pueden incluso ser simplemente punteros en la lista expandida [0.. 100000] lugar de listas separadas.

Para b, mira los valores intermedios:

[0] [0, 1] [0, 1, 2] ... [0, 1, ..., 99999] [0.. 100000]

Cada una de esas listas intermedias no puede reutilizarse, porque si cambia el final de la lista, habrá cambiado cualquier otro valor que la señale. Así que estás creando un montón de listas adicionales que llevan tiempo para construir en memoria. Entonces, en este caso, dedica mucho más tiempo a asignar y completar estas listas que son valores intermedios.

Como solo está haciendo una copia de la lista, a corre más rápido porque comienza expandiendo la lista completa y luego sigue moviendo un puntero desde la parte posterior de la lista al frente.