====== Clase 4 ======
===== Aplicación parcial (secciones) =====
Tomemos la siguente función Haskell que es una ligera variación de //esMultiplo// que está en el problemario: la función //esDivisor//, que toma dos enteros y devuelve True si el segundo es divisor del primero.
esDivisor :: Int -> Int -> Bool
esDivisor p n = n `mod` p == 0
Ahora podemos usar la función //esDivisor// para definir la función //esPar//:
esPar :: Int -> Bool
esPar x = esDivisor 2 x
Por lo tanto, podemos ver que la función //esDivisor//, con dos argumentos //Int// y un resultado //Bool//, puede leerse también como una función con un argumento //Int// y un resultado //Int -> Bool//, es decir, que su resultado puede ser una **función**.
esDivisor :: Int -> (Int -> Bool)
Esta agrupación es un efecto del hecho que el //constructor de tipos funcionales// asocia a derecha.
Por lo tanto, una función es un ciudadano de primera categoría en Haskell, puede ser devuelto como resultado de una función y también veremos que puede ser un parámetro de entrada.
Gracias a esta forma de agruparse, podemos definir las funciones sin especificar sus argumentos, siempre que estos vengan dados por el contexto de forma inequívoca. Por ejemplo, veamos esta versión de la función //esPar// donde no ha sido necesario escribir el argumento:
esPar' :: Int -> Bool
esPar' = esDivisor 2
Como se ve, en esta definición no hemos especificado el argumento //x//, que es al que se le aplican las funciones que estamos usando. No es necesario especificarlo porque en ambos casos se trata del único argumento que requiere la función.
Esta forma de escribir funciones se denomina [[http://en.wikipedia.org/wiki/Currying|currificación]], en honor al lógico [[http://es.wikipedia.org/wiki/Haskell_Curry|Haskell Curry]] ((Sí, sí, el lenguaje Haskell se llama así por Haskell Curry.)).
Este mecanismo de aplicación parcial de argumentos, o secciones, proporciona una forma elegante de escribir funciones.
Por ejemplo:
incrementa :: Int -> Int
incrementa = (+1)
En esta definición de //incrementa//, está claro que el número al que se le va a sumar 1 es el que se dá como único argumento de la función.
También podemos usar las secciones directamente en la función //map//:
Main> map (+1) [2,3,4,5]
[3,4,5,6]
Main> map (*2) [2,3,4,5]
[4,6,8,10]
Main> map (==0) [2,3,4,5]
[False,False,False,False]
Main> map (esDivisor 2) [2,3,4,5]
[True,False,True,False]
En este caso, la función toma como argumento cada uno de los elementos de la lista sucesivamente.
Tiene que quedar claro que esta es una forma **elegante** y **compacta** de definir nuevas funciones a partir de otras, pero no es imprescindible. Por ejemplo, para //map (==0)// podemos definir la función auxiliar
igual0 :: Int -> Bool
igual0 x = x == 0
y aplicar esta función sobre la lista
Main> map igual0 [2,3,4,5]
[False,False,False,False]
===== Generalización de las funciones vistas (map, filter, fold) =====
==== Aplicaciones (map) ====
¿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
cuadrado :: Int -> Int
cuadrado x = x^2
cuadrados :: [Int] -> [Int]
cuadrados [] = []
cuadrados (x:xs) = cuadrado x : cuadrados xs
rangoEdades :: [Int] -> [String]
rangoEdades [] = []
rangoEdades (x:xs) = rangoEdad x : rangoEdades xs
Entonces **generalicemos**. Vemos que todas las funciones son iguales excepto por la operación que se aplica a cada uno de los elementos de la lista. Entonces, 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).
Como ya hemos visto, esto es perfectamente posible en Haskell. Recibe el nombre de **alto orden**, un nombre muy pomposo para algo bastante natural: **las funciones son un tipo más que puede ser tomado como parámetro y devuelto como resultado**. Recordemos el ejemplo de divisor, que devolvía como resultado una función de tipo //Int -> Bool//.
esDivisor :: Int -> (Int -> Bool)
esDivisor 2 :: Int -> Bool
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, tomamos la definición de la función //rangoEdades// y nos quedamos con la parte común a todas las aplicaciones:
rangoEdades :: [Int] -> [String]
rangoEdades [] = []
rangoEdades (x:xs) = rangoEdad x : rangoEdades xs
___________ :: [Int] -> [String]
___________ [] = []
___________ (x:xs) = _________ x : ___________ xs
Si queremos hacer esta expresión independiente de tipos, usaremos los comodines de tipo //a//, //b//, etc. en lugar de los tipos comunes //Int//, //String//, etc.
___________ :: [a] -> [b]
___________ [] = []
___________ (x:xs) = _________ x : ___________ xs
A esta base común hay que añadir un argumento más: la función que se aplicará a todos los elementos de la lista. En el ejemplo anterior, la función era //rangoEdad//, pero en el caso generalizado no la vamos a especificar en la función sino que vamos a pedir que nos venga dada como un argumento más cuando se llama a la función.
aplicar :: (a -> b) -> [a] -> [b]
aplicar f [] = []
aplicar f (x:xs) = f x : aplicar f 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:
duplicar xs = aplicar (*2) xs
cuadrados xs = aplicar (^2) xs
rangoEdades xs = aplicar rangoEdad xs
O bien aplicando secciones, es decir, sin escribir los argumentos obvios:
duplicar = aplicar (*2)
cuadrados = aplicar (^2)
rangoEdades = aplicar rangoEdad
==== Filtros (filter) ====
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?
__________ :: [Int] -> [Int]
__________ [] = []
__________ (x:xs) | ______ x = x : _____________ xs
| otherwise = _____________ xs
Si queremos hacer esta expresión independiente de tipos, usaremos los comodines de tipo a, b, etc. en lugar de los tipos comunes Int, String, etc.
__________ :: [a] -> [a]
__________ [] = []
__________ (x:xs) | ______ x = x : _____________ xs
| otherwise = _____________ 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
O bien aplicando secciones, es decir, sin escribir los argumentos obvios:
soloPares = filtrar esPar
empiezaM = filtrar primeraEsM
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//).
==== Acumuladores (foldr) ====
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)
concatenaInt :: [[Int]] -> [Int]
concatenaInt [] = []
concatenaInt (xs:xss) = (++) xs (concatenaInt xss)
¿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 (++) []
===== Ejercicios =====
* Escribir //duplicar// y //multiplicar// con //aplicar//.
* Reescribir ambas utilizando aplicación parcial sobre //mapa// para evitar escribir el argumento de la lista.
* Utilizando //aplicar// escribir la función //largos :: [String] -> [Int]// que dada una lista de strings, retorna la lista con la longitud de cada una. //Ayuda: recordar que los strings son listas de caracteres.//
* Escribir //soloPares// y //quitar0s// con //filtrar//.
* Reescribir ambas utilizando aplicación parcial sobre //aplicar// para evitar escribir el argumento de la lista.
* Escribir //concatenaInt// usando //acumular//.
* Escribir //sumatoria// usando aplicación parcial con //acumular//.
* Escribir //paraTodoInt// usando //acumular//.
* Escribir //longitud// usando //acumular//.
* Escribir //reversa// usando //acumular//.
* **(DIFÍCIL)** Escribir //aplicar// y //filtrar// usando //acumular//.
* Definir la función //cuantosCumplen//, //cuantosCumplen :: (Int -> Bool) -> [Int] -> Int//, que dado un predicado //p// y una lista de enteros //xs//, cuenta cuántos elementos de la lista cumplen con //p//.
* Definir la función //sumaPares//, //sumaPares :: [Int] -> Int//, que suma sólo los elementos pares de una lista.
* Definir la función //estudiantesMayores35//, //estudiantesMayores35 :: [(String,Int,Int,Int)] -> Int//, que dada una lista de cuatro-uplas //(String,Int,Int,Int)// que se corresponden con //(Nombre,Año-Nacimiento,Año-Inicio-Estudios,Año-Fin-Estudios)//, devuelve la cantidad de estudiantes que fueron mayores de 35 años en algún momento en el transcurso de sus estudios.
* Definir la función //listaMayorQue//, //listaMayorQue :: Int -> [ [ a ] ] -> Bool//, que dado un número //n// y una lista de listas, devuelve True si todas las listas de la lista tienen por lo menos //n// elementos.
* Definir la función //totalSueldos//, //totalSueldos :: [Int] -> Int//, que dada una lista con el monto de cada uno de los sueldos que paga una empresa, aplica una suba del 5% a todos los sueldos y devuelve el monto total que gastará la empresa en sueldos.
* Definir la función //impuestoLujo//, //impuestoLujo :: [(String,Int)] -> [(String,Int)]//, que dada una lista de tuplas //(Producto, Precio)//, aplica un impuesto del 21% extra a todos los productos que salen más de 10000 pesos.
* Definir la función //cuentaInteresantes//, //cuentaInteresantes :: [(String,Bool)] -> Int//, que cuenta la cantidad de libros interesant es que hay en una biblioteca. Los libros están representados mediante una tupla //(String, Bool)//, que contiene el título del libro en el primer elemento y en el segundo el elemento contiene True si el libro es interesante y False si no lo es.
* Definir la función //edadPromedio//, //edadPromedio:: [(String,Int)] -> Int//, que dada una lista de pares //(nombre,edad)//, retorna el promedio de edad de las personas.