foldl es recursiva cola, así que ¿cómo es que foldr corre más rápido que foldl?

Question

quería probar foldl vs foldr. Por lo que he visto que puedes usar foldl sobre foldr cuando cada vez que puede debido a la optimización de la cola reccursion.

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

foldr (0.057s lleva al utilizar comando time):

a::a -> [a] -> [a]
a x = ([x] ++ )

main = putStrLn(show ( sum (foldr a [] [0.. 100000])))

foldl (0.089s lleva al utilizar comando time):

b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])

main = putStrLn(show ( sum (foldl b [] [0.. 100000])))

Es evidente que este ejemplo es trivial, pero estoy confundido en cuanto a por qué foldr está latiendo foldl. No debería ser un caso claro donde las ganancias foldl?

Answer 1

Bienvenido al mundo de la evaluación perezosa.

Cuando se piensa en ello en términos de evaluación estricta, miradas foldl "buena" y las miradas foldr "malas" porque foldl es recursiva cola, pero foldr tendría que construir una torre en la pila para que pueda procesar primero el último elemento .

Sin embargo, la evaluación perezosa da la vuelta. 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 muy bueno si Haskell utiliza evaluación estricta, ya que tendría que calcular la cola en primer lugar, a continuación, anteponer el artículo (para todos los elementos de la lista). La única manera de hacerlo de manera eficiente sería construir los elementos en orden inverso, lo que parece.

Sin embargo, gracias a la evaluación perezosa de Haskell, esta función mapa es realmente eficiente. Listas en Haskell pueden ser considerados como generadores, y esta función genera un mapa su primer elemento mediante la aplicación f para el primer elemento de la lista de entrada. Cuando se necesita un segundo elemento, que sólo hace lo mismo otra vez (sin utilizar espacio adicional).

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

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

Es difícil saber con sólo mirarlo, pero patadas en la evaluación perezosa porque foldr puede dar f su primer argumento de inmediato:

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

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

Ahora, la evaluación perezosa hace tragarse. Por ejemplo, intente ejecutar suma [1..1000000]. Se produce un desbordamiento de pila. ¿Por qué habría de hacerlo? Sólo debe evaluar de izquierda a derecha, de derecha?

Echemos un vistazo a cómo se 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 que va. En lugar de ello, termina con una torre de procesadores sin evaluar que tienen que ser obligado a obtener un número. El desbordamiento de pila se produce durante esta evaluación, ya que tiene que recursivo profundamente para evaluar todos los procesadores.

Afortunadamente, hay una función especial en Data.List llamada foldl' que opera en sentido estricto. foldl' (+) 0 [1..1000000] no desbordamiento de pila. (Nota: He intentado reemplazar foldl con foldl' en su prueba, pero en realidad se hizo correr más lento.)

Answer 2

EDIT:. Al mirar este problema de nuevo, creo que todas las explicaciones actuales son algo insuficiente por lo que he escrito 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 ampliar como

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

Esta lista es procesada por sum, que consume como sigue:

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 dejado de lado los detalles de la lista de concatenación, pero así es como procede la reducción. La parte importante es que todo se procesa con el fin de minimizar los recorridos de la lista. La única foldr atraviesa la lista una vez, las concatenaciones no requieren recorridos continuos lista, y finalmente se consume sum la lista en una sola pasada. Fundamentalmente, la cabeza de la lista está disponible de inmediato para foldr sum, por lo sum puede comenzar a trabajar de inmediato y los valores se puede gc'd medida que se generan. Con marcos de fusión tales como vector, incluso las listas intermedias es probable que se fusionan de distancia.

Esto contrasta 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 la cabeza de la lista no está disponible hasta foldl ha terminado. Esto significa que toda la lista debe ser construido en la memoria antes sum pueden comenzar a trabajar. Esto es mucho menos eficiente en general. Ejecución de las dos versiones con espectáculos +RTS -s lamentable actuación de recolección de basura de la versión foldl.

Este es también un caso en el que foldl' no ayudará. La rigidez añadida de foldl' no cambia la forma en que se crea la lista intermedia. La cabeza de la lista sigue sin estar disponible hasta foldl' ha terminado, por lo que el resultado será incluso más lenta que con foldr.

Yo uso la siguiente regla para determinar la mejor opción de fold

• Para pliegues que son un reducción , el uso foldl' (por ejemplo, esta será la única / recorrido final)
• En caso contrario el uso foldr.
• No utilice foldl.

En la mayoría de los casos foldr es la mejor función de plegado debido a la dirección de recorrido es óptimo para la evaluación perezosa de listas. Es también el único capaz de procesar listas infinitas. La rigidez extra de foldl' puede hacer que sea más rápido en algunos casos, pero esto depende de cómo va a utilizar esa estructura y la forma en que es perezoso.

Answer 3

No creo que nadie en realidad dijo que la verdadera respuesta en este caso, sin embargo, a menos que me falta algo (que bien puede ser cierto y acogido con downvotes).

Creo que la mayor diferencia en este caso es que foldr construye la lista como esta:

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

Mientras que foldl construye la lista como esta:

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

La diferencia en sutil, pero aviso de que en la versión foldr ++ siempre tiene un solo elemento de la lista como argumento izquierda. Con la versión foldl, hay hasta 999999 elementos de argumento izquierdo de ++ (en promedio alrededor de 500.000), pero sólo uno de los elementos en el argumento de la derecha.

Sin embargo, ++ toma tiempo proporcional al tamaño del argumento de la izquierda, ya que tiene que mirar si toda la lista de argumentos izquierda hasta el final y luego re-apuntar que el último elemento al primer elemento del argumento de la derecha (en el mejor, tal vez lo que realmente necesita hacer una copia). La lista de argumentos es correcta sin cambios, por lo que no importa lo grande que es.

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

Answer 4

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

Optimización de la cola de recursión evita la necesidad de recordar los valores para cada llamada recursiva.

Así, 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 la expresión "foldl (+) 0 [1,2,3]" se evalúa:

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 se acuerda de los valores 0, 1, 2 ..., pero pasan toda la expresión (((0 + 1) 2) 3) como argumento con pereza y no lo evalúa hasta que el última evaluación de foldl, donde alcanza el caso base y devuelve el valor pasado como parámetro segundo (z) wich no se evalúa todaví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 cuando foldl evalúa la expresión completa de la última llamada, evitando la necesidad de volver a alcanzar valores recordados, foldr no. foldr recordar un 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, tratar de calcular esta expresión en abrazos:

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

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

foldr y foldl son equivalentes sólo bajo ciertas condiciones descritas aquí

(lo siento por mi mala Inglés)

Answer 5

Para una, la lista [0.. 100000] necesita ser ampliado de inmediato para que foldr puede comenzar con el último elemento. Luego, a medida que se pliega cosas juntos, los resultados intermedios son

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

Debido a que nadie está autorizado a modificar este valor de lista (Haskell es un lenguaje funcional puro), el compilador es libre de volver a utilizar el valor. Los valores intermedios, como [99999, 100000] pueden incluso ser simplemente punteros en la lista [0.. 100000] ampliado en lugar de listas separadas.

Para b, vistazo a los valores intermedios:

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

Cada una de esas listas intermedias no se puede volver a utilizar, ya que si se cambia el final de la lista a continuación, que ha cambiado ningún otro valor que apuntan a ella. Así que va a crear un montón de listas adicionales que necesitará tiempo para construir en memoria. Así que en este caso pasa mucho más tiempo la asignación y cumplimentación de estas listas que son valores intermedios.

Dado que sólo estás haciendo una copia de la lista, unas carreras más rápido ya que se inicia mediante la ampliación de la lista completa y luego simplemente se sigue moviendo un puntero desde el fondo de la lista en la parte delantera.

Answer 6

Ni foldl ni foldr es cola optimizado. Es solamente foldl'.

Sin embargo, en su caso utilizando ++ con foldl' no es buena idea porque la evaluación sucesiva de ++ causará que atraviesa crecimiento acumulador y otra vez.

Answer 7

Bueno, déjame reescribir sus funciones de una manera que la diferencia debería ser obvio -

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

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

Usted ve que b es más complejo que una. Si quieres ser a precisa necesita una etapa de reducción de valor que se calcula, pero b necesita dos. Eso hace que la diferencia de tiempo que se está midiendo, en el segundo ejemplo el doble que las reducciones se deben realizar.

// editar:. Pero complejidad del tiempo es el mismo, así que no me molestaría mucho en eso