recursion - recursive - Implicaciones de foldr vs. foldl(o foldl '')
haskell recursive function (7)
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 agregar lista (++) se puede implementar con foldr como
(++) = flip (foldr (:))
mientras
(++) = flip (foldl (:))
le dará un error de tipo.
En primer lugar, Real World Haskell , que estoy leyendo, dice que nunca uses foldl y en su lugar utilices foldl'' . Así que confío en eso.
Pero no entiendo cuándo usar foldr vs. foldl'' . Aunque puedo ver la estructura de cómo funcionan de forma diferente frente a mí, soy demasiado estúpido para entender cuándo "qué 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 proviene de Ruby''s inject y Clojure''s reduce , que no parecen tener versiones de "izquierda" y "derecha". (Pregunta complementaria: ¿qué versión usan?)
¡Cualquier idea que pueda ayudar a un tipo desafiado por la inteligencia como yo sería muy apreciada!
La razón por la cual foldl'' es preferible a foldl para el 99% de todos los usos es que puede ejecutarse en un espacio constante para la mayoría de los usos.
Tome la función sum = foldl[''] (+) 0 . Cuando se usa foldl'' , la suma se calcula inmediatamente, por lo que la aplicación de sum a una lista infinita solo se ejecutará para siempre, y probablemente en espacio constante (si está usando cosas como Int s, Double s, Float s. Integer s use más espacio constante si el número es mayor que maxBound :: Int ).
Con foldl , se foldl un thunk (como una receta de cómo obtener la respuesta, que se puede evaluar más adelante, 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.
La recursión para foldr fx ys donde ys = [y1,y2,...,yk] ve como
f y1 (f y2 (... (f yk x) ...))
mientras que la recursión de foldl fx ys parece a
f (... (f (f x y1) y2) ...) yk
Una diferencia importante aquí es que si el resultado de fxy se puede calcular utilizando solo el valor de x , entonces foldr no ''necesita examinar toda la lista. Por ejemplo
foldr (&&) False (repeat False)
devuelve False mientras
foldl (&&) False (repeat False)
nunca termina. (Nota: repeat False crea una lista infinita donde cada elemento es False .)
Por otro lado, foldl'' es cola recursiva y estricta. Si sabe que tendrá que atravesar toda la lista sin importar qué (por ejemplo, sumar los números en una lista), foldl'' es más eficiente en espacio (y probablemente en tiempo) que foldr .
Por cierto, la inject de Ruby y la reduce de Clojure son foldl (o foldl1 , dependiendo de la versión que uses). Por lo general, cuando solo hay un formulario en un idioma, es un pliegue izquierdo, incluyendo Python''s reduce , Perl''s List::Util::reduce , C ++ ''s accumulate , C #'' s Aggregate , Smalltalk''s inject:into: PHP''s array_reduce , Mathematica''s Fold , etc. Los Lisp comunes reduce valores predeterminados al doblez a la izquierda, pero hay una opción para doblar a la derecha.
Su semántica es diferente por lo que no puedes simplemente intercambiar foldl y foldr . El uno dobla los elementos desde la izquierda, el otro desde la derecha. De esta forma, el operador se aplica en un orden diferente. Esto es importante para todas las operaciones no asociativas, como la resta.
Haskell.org tiene un interesante article sobre el tema.