Funciones recursivas en listas parte 2

Seguimos con Funciones recursivas en listas 

Si deseamos realizar una operación en cada elemento de una lista map es la función indicada. map aplica una función a cada elemento de una lista

map f [x0,x1,x2] -- > [f x0, f x1, f x2]

map es una de las herramientas más utilizadas en programación funcional. Un estilo común es definir un conjunto de cálculos simples usando el map y componerlos.

map f (map g xs) = map (f . g) xs

Map se puede definir de esta manera: 

map :: (a -> b) -> [a] -> [b]

map _ []     = []

map f (x:xs) = f x : map f xs

Una iteración sobre una lista para producir un valor se llama pliegue y existen varias variaciones: plegado desde la izquierda, plegado desde la derecha y varias variaciones que tienen que ver con la "inicialización" y algunas variaciones más avanzadas.

Los pliegues pueden parecer difíciles al principio, pero son extremadamente poderosos y se usan mucho. Y en realidad no son muy complicados.

foldl se pliega desde la izquierda y ed como una iteración en una lista, de izquierda a derecha.

Una aplicación típica es por ejemplo, foldl f z xs

Donde z es un valor inicial

El argumento xs :: [a] es una lista de valores que combinamos sistemáticamente utilizando la función proporcionada f

Una intuición útil: piense en el argumento z :: b como un "acumulador".

La función f toma el valor actual del acumulador y un elemento de lista, y da el nuevo valor del acumulador.

foldl :: (b-> a-> b) -> b -> [a] -> b

Similar a foldl, pero funciona de derecha a izquierda

foldr :: (a -> b -> b) -> b -> [a] -> b

Hemos visto que una lista [x0, x1, x2] también se puede escribir como

    x0: x1: x2: []

cons (:) sobre una lista usando la lista vacía [] como el acumulador da:

foldr (:) [] [x0, x1, x2]

  ->

  x0: x1: x2: []

¡Esto es idéntico a construir la lista usando (:) y []! Podemos formalizar esta relación de la siguiente manera:

foldr cons [] xs = xs

 

Veamos algunos ejemplos: 

suma xs = foldr (+) 0 xs

producto xs = foldr (*) 1 xs

De hecho, podemos "factorizar" las x que aparecen a la derecha de cada lado de la ecuación, y escribir:

sum = foldr (+) 0

producto = foldr (*) 1

(Esto a veces se denomina estilo "point free" porque está programando únicamente con las funciones; los datos no se mencionan directamente).