Implicaciones de foldr vs. foldl (o foldl ‘)

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 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 (fx 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, sumr los números en una lista), foldl' es más eficiente en espacio (y probablemente en tiempo) que foldr .

foldr ve así:

Visualización de doblez derecho

foldl ve así:

Visualización de doblez izquierdo

Contexto: Doble sobre la wiki de Haskell

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 artículo sobre el tema.

En breve, foldr es mejor cuando la función del acumulador es floja en su segundo argumento. Lee más en Haskell wiki’s Stack Overflow (juego de palabras intencionado).

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 sum 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 stack … y te lleva a … oh, no importa)

Espero que ayude.

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.

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.

    Intereting Posts