Comprender foldl y foldr en Haskell: asociatividad, evaluación y uso de espacio

Tanto `foldl` como `foldr` procesan una lista desde el primer elemento hasta el último, pero difieren en cómo asocian la operación de combinación. Con `foldl`, la operación está asociada a la izquierda, construyendo la expresión (((v ⊗ e0) ⊗ e1) ⊗ e2) …, mientras que `foldr` está asociada a la derecha, produciendo e0 ⊗ (e1 ⊗ (e2 ⊗ … (en ⊗ v)…)). Los elementos de la lista aparecen en el mismo orden en ambas expresiones; solo cambia el agrupamiento de las aplicaciones. (fuente: primaria)

En un lenguaje estricto, la evaluación procede de adentro hacia afuera. Para `foldl`, se necesita inmediatamente el primer elemento de la lista, lo que permite una implementación recursiva de cola que usa un espacio de pila constante. En cambio, `foldr` debe llegar al final de la lista antes de que pueda comenzar cualquier reducción, por lo que necesariamente construye una pila de llamadas proporcional a la longitud de la lista. Cuando la operación de combinación es asociativa y conmutativa (por ejemplo, (+)), ambas funciones producen el mismo resultado final, pero las secuencias de reducción difieren. (fuente: primaria)

En un lenguaje perezoso como Haskell, la evaluación procede de afuera hacia adentro, demandando resultados solo cuando se necesitan. Aquí `foldl` resulta problemático: cada paso crea un thunk para la operación parcialmente aplicada, y como el thunk más externo no se fuerza hasta el final, se acumula una cadena de thunks lineal respecto al tamaño de la lista, lo que lleva a un consumo de espacio lineal. La variante estricta `foldl'` fuerza el acumulador en cada paso, evitando la acumulación de thunks y restaurando el comportamiento de espacio constante. Por el contrario, `foldr` puede ser perezoso en su segundo argumento; si la función de combinación es perezosa allí, `foldr` puede devolver un resultado en forma normal débil de cabeza sin recorrer toda la lista, lo que permite ahorrar trabajo y la capacidad de operar con listas infinitas. (fuente: primaria)

Como regla práctica, use `foldl'` cuando la función de acumulación sea estricta, y use `foldr` cuando la función sea perezosa en su segundo argumento; evite usar `foldl` y `foldr'` simples en listas. Para otras estructuras de datos, la elección óptima depende de su asociatividad, y `foldMap`/`foldMap'` suelen ser mejores cuando la asociatividad es irrelevante. (fuente: primaria)