Implicaciones de foldr vs. foldl (o foldl ')

155

En primer lugar, el mundo real Haskell , que estoy leyendo, dice que nunca usefoldl y en su lugar use foldl'. Entonces confío en eso.

Pero estoy nebuloso sobre cuándo utilizar foldrvs foldl'. Aunque puedo ver la estructura de cómo funcionan de manera diferente frente a mí, soy demasiado estúpido para entender cuándo "cuál es mejor". Supongo que me parece que realmente no debería importar cuál se usa, ya que ambos producen la misma respuesta (¿no?). De hecho, mi experiencia previa con esta construcción es de Ruby injecty Clojure reduce, que no parecen tener versiones "izquierda" y "derecha". (Pregunta secundaria: ¿qué versión usan?)

¡Cualquier idea que pueda ayudar a un tipo con problemas de inteligencia como yo sería muy apreciada!

recursion functional-programming fold haskell J Cooper
fuente

Respuestas:

174

La recursividad de foldr f x ysdonde ys = [y1,y2,...,yk]parece

f y1 (f y2 (... (f yk x) ...))

mientras que la recursividad de foldl f x ysparece

f (... (f (f x y1) y2) ...) yk

Una diferencia importante aquí es que si el resultado de f x yse puede calcular usando solo el valor de x, entonces foldrno es necesario examinar la lista completa. Por ejemplo

foldr (&&) False (repeat False)

vuelve Falsemientras

foldl (&&) False (repeat False)

nunca termina (Nota: repeat Falsecrea una lista infinita donde cada elemento esFalse ).

Por otro lado, foldl'es cola recursiva y estricta. Si sabe que tendrá que recorrer toda la lista sin importar qué (por ejemplo, sumar los números en una lista), entonces foldl'es más eficiente en espacio (y probablemente en tiempo) que foldr.

Chris Conway
fuente
2
En foldr se evalúa como f y1 thunk, por lo que devuelve False, sin embargo, en foldl, f no puede conocer ninguno de sus parámetros. En Haskell, no importa si es la recursión de la cola o no, ambos pueden causar desbordamiento de thunks, es decir, thunk es demasiado grande. foldl 'puede reducir thunk inmediatamente a lo largo de la ejecución.
Sawyer
25
Para evitar confusiones, tenga en cuenta que los paréntesis no muestran el orden real de evaluación. Dado que Haskell es vago, las expresiones más externas se evaluarán primero.
Lii
Gran respuesta. Me gustaría agregar que si desea un pliegue que puede detenerse en la mitad de una lista, debe usar foldr; a menos que me equivoque, los pliegues izquierdos no se pueden detener. (Lo insinúa cuando dice "si sabe ... recorrerá toda la lista"). Además, el error tipográfico "usar solo en el valor" debe cambiarse a "usar solo el valor". Es decir, eliminar la palabra "on". (¡Stackoverflow no me permitió enviar un cambio de 2 caracteres!).
Lqueryvg
@Lqueryvg dos formas de detener los pliegues izquierdos: 1. codifíquelo con un pliegue derecho (vea fodlWhile); 2. conviértalo en un escaneo izquierdo ( scanl) y deténgalo con last . takeWhile po similar. Uh, y 3. uso mapAccumL. :)
Will Ness
1
@Desty porque produce una nueva parte de su resultado general en cada paso, a diferencia de lo foldlque recoge su resultado general y lo produce solo después de que todo el trabajo haya terminado y no haya más pasos para realizar. Entonces foldl (flip (:)) [] [1..3] == [3,2,1], por ejemplo , entonces scanl (flip(:)) [] [1..] = [[],[1],[2,1],[3,2,1],...]... IOW, foldl f z xs = last (scanl f z xs)y las listas infinitas no tienen un último elemento (que, en el ejemplo anterior, sería una lista infinita, desde INF hasta 1).
Will Ness
57

foldr Se ve como esto:

Visualización plegado a la derecha

foldl Se ve como esto:

Visualización de pliegue izquierdo

Contexto: Doblar en la wiki de Haskell

Greg Bacon
fuente
33

Su semántica difiere, por lo que no puedes simplemente intercambiar foldly foldr. El primero dobla los elementos desde la izquierda, el otro desde la derecha. De esa manera, el operador se aplica en un orden diferente. Esto es importante para todas las operaciones no asociativas, como la resta.

Haskell.org tiene un artículo interesante sobre el tema.

Konrad Rudolph
fuente
Su semántica solo difiere de una manera trivial, que no tiene sentido en la práctica: el orden de los argumentos de la función utilizada. Por lo que respecta a la interfaz, todavía cuentan como intercambiables. La verdadera diferencia es, al parecer, solo la optimización / implementación.
Evi1M4chine
2
@ Evi1M4chine Ninguna de las diferencias es trivial. Por el contrario, son sustanciales (y, sí, significativos en la práctica). De hecho, si escribiera esta respuesta hoy, enfatizaría aún más esta diferencia.
Konrad Rudolph el
23

En breve, foldres mejor cuando la función del acumulador es perezosa en su segundo argumento. Lea más en Stack Overflow de Haskell wiki (juego de palabras).

Mattiast
fuente
18

La razón foldl'preferida foldlpara el 99% de todos los usos es que puede ejecutarse en espacio constante para la mayoría de los usos.

Toma la función sum = foldl['] (+) 0. Cuando foldl'se usa, la suma se calcula inmediatamente, por lo que la aplicación suma una lista infinita se ejecutará para siempre, y muy probablemente en un espacio constante (si está usando cosas como Ints, Doubles, Floats. IntegerS usará más que un espacio constante si el el número se hace mayor que maxBound :: Int).

Con foldl, se crea un thunk (como una receta de cómo obtener la respuesta, que puede evaluarse más tarde, en lugar de almacenar la respuesta). Estos thunks pueden ocupar mucho espacio, y en este caso, es mucho mejor evaluar la expresión que almacenar el thunk (lo que lleva a un desbordamiento de pila ... y te lleva a ... oh, no importa)

Espero que ayude.

Axman6
fuente
1
La gran excepción es si la función pasada a foldlno hace más que aplicar constructores a uno o más de sus argumentos.
dfeuer
¿Existe un patrón general de cuándo foldles realmente la mejor opción? (Al igual que las listas infinitas cuando foldres la elección incorrecta, en cuanto a optimización.)
Evi1M4chine
@ Evi1M4chine no estoy seguro de lo que quieres decir con foldrser la elección incorrecta para listas infinitas. De hecho, no debe usar foldlo foldl'para listas infinitas. Vea el wiki de Haskell sobre desbordamientos de pila
KevinOrr
14

Por cierto, los de Ruby injecty Clojure reduceson foldl(o foldl1, dependiendo de la versión que uses). Por lo general, cuando sólo hay un formulario en un idioma, es una izquierda pliegue, incluyendo Python reduce, Perl List::Util::reduce, C ++ 's accumulate, C #' s Aggregate, Smalltalk inject:into:, PHP array_reduce, Mathematica Fold, etc. de Common Lisp reducepor defecto a la izquierda veces, pero hay una opción para el derecho pliegue.

newacct
fuente
2
Este comentario es útil pero agradecería las fuentes.
titaniumdecoy
Common Lisp's reduceno es vago, por lo que foldl'muchas de las consideraciones aquí no se aplican.
MicroVirus
Creo que quieres decir foldl', ya que son idiomas estrictos, ¿no? De lo contrario, ¿eso no significará que todas esas versiones causan desbordamientos de pila como lo foldlhace?
Evi1M4chine
6

Como señala Konrad , su semántica es diferente. Ni siquiera tienen el mismo tipo:

ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci>

Por ejemplo, el operador de lista append (++) puede ser implementado con foldrcomo

(++) = flip (foldr (:))

mientras

(++) = flip (foldl (:))

le dará un error de tipo.

Jonas
fuente
Su tipo es el mismo, simplemente cambiado, lo cual es irrelevante. Su interfaz y resultados son los mismos, excepto por el desagradable problema P / NP (léase: listas infinitas). ;) La optimización debido a la implementación es la única diferencia en la práctica, por lo que puedo decir.
Evi1M4chine
@ Evi1M4chine Esto es incorrecto, mire este ejemplo: foldl subtract 0 [1, 2, 3, 4]evalúa a -10, mientras que foldr subtract 0 [1, 2, 3, 4]evalúa a -2. foldles en realidad 0 - 1 - 2 - 3 - 4mientras foldres 4 - 3 - 2 - 1 - 0.
krapht
@krapht, foldr (-) 0 [1, 2, 3, 4]es -2y foldl (-) 0 [1, 2, 3, 4]es -10. Por otro lado, subtractestá al revés de lo que podría esperar ( subtract 10 14es 4), así que foldr subtract 0 [1, 2, 3, 4]es -10y foldl subtract 0 [1, 2, 3, 4]es 2(positivo).
pianoJames