En esta clase vamos a ver las funciones recursivas en listas con algo más de abstracción. Ya vimos que los diferentes tipos de funciones comparten una estructura común, con algunas muy pequeñas variaciones (el predicado que se filtra, la función que se aplica, el operador con el que se acumula). Veremos que en haskell podemos hacer que estas pequeñas variaciones sean un parámetro más de la función. De esta forma vamos a poder generalizar todavía más. Por ejemplo, vamos a crear una función filtro donde el predicado con el que filtramos sea un argumento más de la función. Esto nos va a servir para poder escribir todas las funciones de tipo filtro de forma mucho más concisa.

Este proceso de generalización es muy parecido al proceso que hicimos al definir la función multiplicar :: Int → [Int] → [Int] como generalización de duplicar :: [Int] → [Int], triplicar :: [Int] → [Int], etc: encontramos que había algo dentro de las funciones duplicar y triplicar que se podía tratar como una variable, y que en ese caso las dos funciones eran idénticas. El valor de esta variable pasaba a ser uno de los argumentos requeridos de la función, el que hemos puesto como primer argumento de multiplicar. Así, se puede definir:

duplicar xs = multiplicar 2 xs
triplicar xs = multiplicar 3 xs

Este tipo de generalización es posible en haskell porque haskell tiene una propiedad llamada alto orden que permite que una función sea tomada como argumento de otra función.

Vamos a ver ahora cómo generalizamos los tres diferentes tipos de funciones recursivas en listas. De hecho, el preludio estándar de haskell ya tenemos definidas las funciones generales map, filter y foldr que generalizan aplicaciones, filtros y acumuladores, respectivamente, pero en esta clase vamos a ver cómo se llega a esta generalización para adentrarnos en los procedimientos de generalización.

Algo importante a tener en cuenta es que cuando definimos las versiones generalizadas de aplicaciones, filtros y acumuladores, definimos en esas versiones generalizadas el caso base y caso recursivo. Cuando definimos nuevas funciones usando estas generalizaciones, no tenemos que volver a definir caso base y caso recursivo, ya que las nuevas funciones usan la definición de caso base y caso recursivo de las funciones generalizadas. Véamoslo en concreto con los ejemplos.

¿No estamos ya cansados de escribir siempre lo mismo? Las funciones de tipo aplicación, son todas idénticas, salvo por la operación o función que se aplica a cada elemento.

duplicar :: [Int] -> [Int]
duplicar []     = []
duplicar (x:xs) = 2*x : duplicar xs

veintePorCiento :: [Float] -> [Float] 
veintePorCiento []     = []
veintePorCiento (x:xs) = 0.2*x : veintePorCiento xs

Entonces generalicemos. Podemos definir una función general para cualquier aplicación, donde la operación que se aplica a cada uno de los elementos de la lista viene dada como un argumento más de la función. Esto es, definimos una función (la función aplicación) que toma como parámetro a otra función (la operación que se aplica a cada elemento de la lista). Así, podremos cambiar lo que hace la función aplicación de forma muy sencilla, cambiando esta segunda función cada vez que llamemos a la función aplicación.

La forma generalizada de las funciones de aplicación se compone de lo que tienen en común todas las funciones aplicación que hemos visto hasta ahora:

fRecursiva :: [a] -> [b]
fRecursiva []     = []
fRecursiva (x:xs) = fNoRecursiva x : fRecursiva xs

Ahora lo que queremos hacer es que fNoRecursiva sea un argumento más de fRecursiva. Para eso hay que cambiar la signatura de tipos, incorporando este nuevo argumento. Llamemos aplica a esta nueva fRecursiva.

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

Vemos que la nueva función tiene un nuevo argumento, a → b. Sabemos que este argumento es una función porque es complejo: toma un elemento de tipo a y devuelve un elemento de tipo b. Esta función será precisamente la función que aplicaremos a cada uno de los elementos de la lista, ya sea multiplicar por dos, transformar a binario, o cualquier otra. Entonces, la función aplica combinará esta nueva signatura de tipos con el esquema general de las aplicaciones, donde ahora la función que se aplica es uno de los argumentos de la función. Quedará definida de la siguiente forma:

aplica :: (a -> b) -> [a] -> [b]
aplica f [] = []
aplica f (x:xs) = f x : aplica f xs

Ahora podemos reescribir todas las aplicaciones usando aplica, y definiendo como argumento la función que queremos aplicar a todos los elementos de la lista. Por ejemplo:

duplicar' :: [Int] -> [Int]
duplicar xs = aplica (*2) xs
veintePorCiento' :: [Float] -> [Float]
veintePorCiento xs = veintePorCiento (porCiento 20) xs

De esta forma, las funciones quedan mucho más compactas, más legibles y mucho más fáciles de mantener, ya que al tener que escribir menos, tenemos menos posibilidades de equivocarnos. Fíjense que ni siquiera tenemos que definir caso base y caso recursivo para cada una de las nuevas funciones que definimos con la función aplica, porque ya tenemos definido caso base y caso recursivo en la función aplica, y las funciones que definamos usando aplica usan esa definición de caso base y caso recursivo.

Veamos funciones de tipo filtro que hemos creado:

esPar :: Int -> Bool
esPar = esDivisor 2

soloPares :: [Int] -> [Int]
soloPares [] = []
soloPares (x:xs) | esPar x   =  x : soloPares xs
                 | otherwise =      soloPares xs

primeraEsM :: [Char] -> Bool
primeraEsM xs = cabeza xs == 'm'

empiezaM :: [String] -> [String]
empiezaM [] = []
empiezaM (x:xs) | primeraEsM x = x : empiezaM xs
                | otherwise    =     empiezaM xs

¿Cuál es la estructura que tienen en común estas funciones?

fRecursiva :: [a] -> [a]
fRecursiva [] = []
fRecursiva (x:xs) | predicado x  =  x : fRecursiva xs
                  | otherwise    =      fRecursiva xs

A esta base común hay que añadir un argumento más: la función que se va a evaluar para todos los elementos de la lista. Este tipo de función es un predicado, es decir una función que devuelve un booleano, que decidirá si cada elemento se conserva o se filtra. En el ejemplo anterior, el predicado era primeraEsM, pero en el caso generalizado no lo vamos a especificar en la función sino que vamos a pedir que nos venga dado como un argumento más cuando se llama a la función.

filtrar :: (a -> Bool) -> [a] -> [a]
filtrar p []     = []
filtrar p (x:xs) | p x       = x : filtrar p xs
                 | otherwise =     filtrar p xs

De esta forma, llamando a la función general con diferentes operaciones como argumento, podremos definir las diferentes funciones que hemos visto hasta ahora, por ejemplo:

soloPares xs = filtrar esPar xs
empiezaM xs = filtrar primeraEsM xs

Observemos que en el caso de los filtros, los elementos de la lista resultado tienen que ser del mismo tipo que los elementos de la lista que damos como argumento ([a] → [a]), ya que la función filtro no modifica los elementos, sino que solamente determina si deben o no deben formar parte del resultado. En cambio, en las aplicaciones el resultado puede ser de distinto tipo que el argumento ([a] → [b]), porque la aplicación sí puede modificar los elementos de la lista de entrada, incluso cambiándolos de tipo. Notemos que [a] → [b] significa que podemos encontrar tipos distintos (como en rangoEdad) pero esto no es obligatorio: podemos encontrar que a y b representen el mismo tipo (como en duplicar).

Más y más funciones fueron acumuladores, veamos algunas:

sumatoria :: [Int] -> Int
sumatoria []     = 0
sumatoria (x:xs) = x + sumatoria xs

producto :: Int -> Int -> Int
producto x y = x*y

productoria :: [Int] -> Int
productoria []     = 1
productoria (x:xs) = producto x (productoria xs)

¿Cuál es la estructura común de todas estas funciones? Para poder verla bien, debemos saber que todo operador que usemos entre sus dos argumentos, como +, : o ++, se puede usar también con la misma sintaxis que cualquier otra función, es decir, delante de sus dos argumentos. Para ello hay que poner al operador entre paréntesis, como hemos visto en el último de los ejemplos de arriba con el operador ++. De esta forma, el caso recursivo de la función sumatoria también se puede escribir así:

sumatoria (x:xs) = (+) x (sumatoria xs)

Donde el primer número a sumar es x y el segundo es sumatoria xs, es decir, el resultado de resolver la función sumatoria xs.

Entonces, la estructura común de todas estas funciones es:

_________ :: [a] -> b
_________ []     = _____
_________ (x:xs) = _____ x (_________ xs)

Como el resultado de la función no es una lista, el resultado del caso base no es una lista vacía. El resultado del caso base debe ser definido para cada función, ya que debe ser el neutro del operador que se utilice en la función. Por lo tanto, en los acumuladores tendremos un argumento más que en las aplicaciones y los filtros, justamente, el neutro.

Por lo tanto, la generalización de los acumuladores es la siguiente:

acumular :: (a -> b -> b) -> b -> [a] -> b
acumular f n []     = n
acumular f n (x:xs) =  f x (acumular f n xs)

Ahora podemos escribir todas las funciones que son acumuladores mediante esta generalización.

sumatoria xs = acumular (+) 0 xs
productoria xs = acumular (*) 1 xs
concatenaInt xs = acumular (++) [] xs

O bien aplicando secciones, es decir, sin escribir los argumentos obvios:

sumatoria = acumular (+) 0
productoria = acumular (*) 1
concatenaInt = acumular (++) []