Funciones de "plegado" Foldr foldl , que oscuras pueden ser!!

Hay dos funciones en Haskell que son muy interesantes, estas son: foldr y foldl.

Consideremos los siguientes ejemplos de funciones en Haskell

prod [] = 1
prod (x:xs) = x * (prod xs)

suma [] = 0
suma (x:xs) = x + (suma xs)

Observemos que todas estas funciones siguen un patrón, estan definidas para un caso base, la lista vacia, y para un caso mas general (x:xs), si sustituimos el nombre de cada función por f tendriamos que todas ellas tiene la siguiente forma

f [] = e
f (x:xs) = g x (f n)

Podriamos definir a todas las funciones que siguen este patrón de la siguiente manera:

foldr g e [] = e
foldr g e (x:xs) = g x (foldr g e xs )

Podemos entonces reescribir las definiciones de las funciones anteriores ,como:

prod = foldr (*) 1

suma = foldr (+) 0

Se puede ver.... mas bien, no se puede ver tan facilmente que se esta definiendo al hacer uso de foldr, es por eso que pueder llegar a ser un tanto oscura.
Una explicación mas sencilla de lo que hace Foldr podría la suiguiente:

usando un ejemplo:

suma = foldr (+) 0

suma [7,4,8] = (foldr (+) 0 )[7,4,8]
= (+ 7 ((foldr (+) 0 ) [4,8]))
= (+ 7 (+ 4 ( (foldr (+) 0 ) [8] ) ) )
= (+ 7 (+ 4 (+ 8 ((foldr (+) 0)[] ))))
= (+7 ( + 4 (+ 8 0)))

Escribimos a (+) como una funcion prefija que la podemos poner como infija quedando:

= (7 + ( 4 + ( 8 + 0))))
= 7+4+8 = 19

Podemos darnos cuenta que si a (+) la cambiamos por (:) y al 0 por [] tendiramos como resultado la misma lista.

foldl funciona de manera muy similar, su definición es:

foldl g e [] = e
foldl g e (x:xs) = foldl g (g e x) xs


basado en las notas del curso de programacion funcional y lógica