El blog de Haskell rescata la explicación clásica de foldl frente a foldr
Alexis King explicó en 2019 por qué los dos pliegues recorren la lista en el mismo orden y por qué eso decide el consumo de memoria en un lenguaje perezoso.
El blog oficial de Haskell ha rescatado un texto de Alexis King sobre la diferencia entre foldl y foldr, escrito en 2019 dentro de una discusión en el repositorio de Hasura y reproducido ahora con permiso de la autora. La tesis incomoda a quien aprendió de memoria lo de plegar "por la izquierda" y "por la derecha": ninguno de los dos recorre la lista en direcciones opuestas. Ambos van de izquierda a derecha. Lo que cambia es cómo se agrupan las aplicaciones de la operación.
Asociatividad, no dirección
Con foldl (⨂) v [e0 ... en] el cálculo es (...((v ⨂ e0) ⨂ e1)...) ⨂ en, asociado por la izquierda. Con foldr es e0 ⨂ (e1 ⨂ (... (en ⨂ v))), asociado por la derecha. La lista se lee igual en los dos casos; el paréntesis cae en otro sitio.
En un lenguaje estricto la evaluación va de dentro hacia fuera. Eso permite implementar foldl como un bucle recursivo de cola: basta el primer elemento para empezar a reducir y el espacio es constante. foldr no puede, porque necesita el último elemento antes de tocar nada y levanta n marcos de pila. De ahí lo de "plegar desde la derecha", aunque recorra la lista al revés de lo que sugiere el nombre.
En un lenguaje perezoso se rompe
Haskell no evalúa de dentro hacia fuera, sino de fuera hacia dentro: solo reduce lo que alguien demande. foldl (+) 0 [1,2,3,4] no se compila a un bucle, sino que se expande a una cadena de thunks anidados, ⟨⟨⟨⟨0+1⟩+2⟩+3⟩+4⟩, que solo se fuerza cuando se pide el resultado. El consumo de memoria pasa de constante a lineal respecto al tamaño de la entrada. Y el destrozo es mayor de lo que sugiere esa cuenta, porque en un lenguaje perezoso la lista se comporta como un stream que puede no materializarse entero en memoria.
La salida es foldl', que impone una demanda sobre el acumulador en cada paso y nunca construye un thunk mayor que una sola aplicación de la operación. foldr, con una operación estricta, sigue gastando espacio lineal, pero por un motivo distinto. Para el caso concreto de cuál elegir, hay una respuesta de Stack Overflow que resume las alternativas.
Quien haya escrito foldl donde tocaba foldl' ya sabe cómo acaba: una fuga que no aparece con listas de diez elementos y tumba el proceso con un millón. Lo que aporta el texto no es vocabulario, sino el mecanismo: el orden de recorrido y el orden de evaluación son dos cosas distintas, y en un lenguaje perezoso la segunda decide si el programa consume memoria constante o proporcional a la entrada.
