====== 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.
esDivisor :: Int -> Int -> Bool
esDivisor p n = n `mod` p == 0
Dado que el //constructor de tipos funcionales// (ver Práctico 5) asocia a derecha, tenemos que en realidad:
esDivisor :: Int -> (Int -> Bool)
Esto lo podemos leer como que //esDivisor// es una función que toma un entero y **devuelve una función** de tipo //Int->Bool//.
Esto es lo mismo que pasa en los ejercicios 5f, 5g y 5i del Práctico 5, y muestra que 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.
Para ganar confianza podemos preguntar a Hugs por el tipo de la aplicación parcial.
Main> :t esDivisor 2
esDivisor 2 :: Int -> Bool
Pero ... que significa ''esDivisor 2''?
Vemos la siguiente definición:
esPar :: Int -> Bool
esPar x = esDivisor 2 x
La función devuelve //True// si y solo si el entero es divisible por 2!
Notamos que esta definición es idéntica a esta versión **sin argumentos** que utiliza el mecanismo de secciones
esPar' :: Int -> Bool
esPar' = esDivisor 2
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]] ((Si si, el lenguaje Haskell se llama así por Haskell Curry.)).
Este mecanismo de aplicación parcial de argumentos resulta muy elegante para escribir funciones.
Por ejemplo:
incrementa :: Int -> Int
incrementa = (+1)
o bien las usamos 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]
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 el tercer ejemplo 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]
=== Ejercicio ===
* Utilizando aplicación parcial en //( /= )//, definir la función //noEsCero :: Int -> Bool// que decide si un entero //x// es distinto a 0.
===== Generalización de las funciones vistas (map, filter, fold) =====
==== Aplicaciones ====
?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 **generalizemos** definiendo una función que toma como primer argumento la función que se aplicará a cada elemento de la lista.
Vemos nuevamente la aplicación del **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**.
De nuevo, se dice que en Haskell las funciones son //ciudadanos de primera categoría//.
Esto no ocurre en la mayoría de los //lenguajes imperativos// como C, C++, Pascal, Basic, etc. .
Notar que ya vimos funciones que devuelven funciones! Por ejemplo.
esDivisor :: Int -> (Int -> Bool)
esDivisor 2 :: Int -> Bool
=== Ejercicio ===
* Definir la función //mapNumeros.f.xs//, //mapNumeros : (Int -> Int) -> [Int] -> [Int]// que dada una función //f// y una lista de enteros //xs//, les aplica una función aritmética //f// y concatena el resultado en una lista. Ejemplo: //mapNumeros.(+2).[0,1,2,3] = [2,3,4,5]//.
probar con mapNumeros.(*2).[0,1,2,3], mapNumeros.absoluto.[-10,0,10].
==== Filtros ====
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
Entonces plantemos el mismo tipo de ejercicio, una generalización que tome como primer parámetro un **predicado**, es decir una función que devuelve un booleano, que decidirá si cada elemento se conserva o se filtra.
=== Ejercicio ===
* Definir la función //filtraNumeros.p.xs//, //filtraNumeros : (Int -> Bool) -> [Int] -> [Int]// que dada un predicado //p// y una lista de enteros //xs// devuelve la lista que contiene sólo aquellos números de //xs// que devuelven //True// en la predicado //p//. Ejemplo: //filtraNumeros.entre0y9.[11,4,37,3,10] = [4,3]//. Un ejemplo con algunas implicaciones más: //filtraNumeros.(esDivisor.3).[1,2,3,4,5,6,7,8,9,10] = [3,6,9]//.
probar con filtraNumeros.entre0y9.[], filtraNumeros.entre0y9.[10,20,30].
==== Acumuladores ====
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)
=== Ejercicio ===
Definir la primera generalización.
* Definir la función //paraTodoInt.p.xs//, //paraTodoInt : (Int->Bool) -> [Int] -> Bool//, que dado un predicado //p// retorna verdadero si y solo si, el predicado es válido para todos los elementos de la lista. Ejemplo //paraTodoInt.multiplo2.[2,4,6] = True//.
probar con paraTodoInt.multiplo2.[2,3,4], paraTodoInt.entre0y9.[1,2,4,2,1], paraTodoInt.multiplo2.[].
Y luego esta que es casi completa.
* Definir la función //acumulaInt.f.z.xs//, //acumulaInt : (Int->Int->Int) -> Int -> [Int] -> Int//, que dado un operador //f//, un elemento //z// neutro del operador y una lista //xs//, retorna la acumulación del operador con //z// (cero) y con cada uno de los elementos de la lista. Ejemplo: //acumulaInt.max.0.[1,9,3,7,0] = 9//.
probar con acumulaInt.(+).0.[1,2,3], acumulaInt.(*).1.[1,2,3].
===== Escribamos las versiones más generales =====
Hasta ahora trabajamos con las generalizaciones de las funciones desde el punto de vista que le podíamos dar cualquier función para que operara sobre los valores.
Es posible generalizar estas funciones a los **tipos**.
==== Aplicaciones (map) ====
Si escribimos la definición de //mapNumeros// vemos que solo importa que la función //f// toma un elemento del tipo de la primer lista y genera un elemento del tipo de la segunda lista, luego podemos utilizar variables de tipo y definir la función:
* Generalizar //mapNumero// y //mapNumeroString// con //mapa.f.xs//, //mapa : (a -> b) -> [a] -> [b]// que dada una función que lleva algo de tipo //a// a tipo //b// y una lista //xs// de cualquier tipo //a// devuelve una lista //b// con el resultado de aplicar la función //f// a cada elemento de //xs//.
probar con mapa.ordena.[(1,0)(0,1)], mapa.segundo3.[(10,20,30),(12,22,32),(14,24,34)],
mapa.longitud.[[],[1],[1,2]], mapa.(\x -> [x,x])."tartamuda".
La escribamos:
mapa :: (a -> b) -> [a] -> [b]
mapa f [] =
mapa f (x:xs) =
==== Filtros (filter) ====
Lo mismo para //filtraNumeros// podemos filtrar los elementos de una lista de cualquier tipo:
* Generalice la función //filtraNumeros// para listas de cualquier tipo. Defina //filtro.f.xs//, //filtro : (a -> Bool) -> [a] -> [a]// que dado un predicado //p// y una lista //xs// de tipo //a//, devuelve una lista del mismo tipo que contiene sólo aquellos elementos de //xs// que son //True// en la función //p//.
probar con filtro.esMultiplo2.[1,2,3,4,5,6], filtro.(esMultiplo.3).[1,2,3,4,5,6,7,8,9,10],
filtro.(==0).[1,2,3,4].
La escribamos:
filtro :: (a->Bool) -> [a] -> [a]
filtro p [] =
filtro p (x:xs) =
==== Acumuladores (fold) ====
La generalización de los acumuladores a distintos tipos es un poco más complicada.
Veamos la función de acumulación que dice si todos los elementos son 0 y 1.
todos0y1 :: [Int] -> Bool
todos0y1 [] = True
todos0y1 (x:xs) = (x==0 || x==1) && todos0y1 xs
Detectamos:
* Un "**cero**" respecto a la acumulación (//True// es neutro de la conjunción).
* Una función de acumulación que a partir del elemento actual y lo acumulado en la llamada recursiva sobre //xs//, obtiene el valor de lo acumulado en el total //x:xs//.
Podemos reescribirla de la siguiente manera para que la función de acumulación sea más explícita.
ceroUnoYAnteriores :: Int -> Bool -> Bool
ceroUnoYAnteriores x b = (x==0 || x==1) && b
todos0y1' :: [Int] -> Bool
todos0y1' [] = True
todos0y1' (x:xs) = ceroUnoYAnteriores x (todos0y1' xs)
La defunición general sería:
* Generalice la función anterior para operadores y listas de cualquier tipo. Definir //acumula.f.z.xs//, //acumula : (a->b->b) -> b -> [a] -> b//, que dado un operador binario //f// (asociativo a derecha), un elemento //z// neutro (a derecha) del operador y una lista //xs//, retorna la acumulación del operador con //z// (cero) y con cada uno de los elementos de la lista. Ejemplo: //acumula.(++).[].["Hola", " ", "que", " ", "tal"] = "Hola que tal"//.
probar con todos los ejemplos de las versiones menos generales.
Nuevamente la escribimos.
acumula :: (a->b->b) -> b -> [a] -> b
acumula f z [] =
acumula f z (x:xs) =
===== Reescribiendo funciones usando map, fold y filter =====
==== Ejercicios ====
* Escribir //duplicar// y //multiplicar// con //mapa//.
* Reescribir ambas utilizando aplicación parcial sobre //mapa// para evitar escribir el argumento de la lista.
* Utilizando //mapa// escribir la función //largos :: [String] -> [Int]// que dada una lista de cadenas, retorna la lista con la longitud de cada una.
* Escribir //soloPares// y //quitar0s// con //filtro//.
* Reescribir ambas utilizando aplicación parcial sobre //mapa// para evitar escribir el argumento de la lista.
* Escribir //concatenaInt// usando //acumula//.
* Escribir //sumatoria// usando aplicación parcial con //acumula//.
* Escribir //paraTodoInt// usando //acumula//.
* Escribir //longitud// usando //acumula//.
* Escribir //reversa// usando //acumula//.
* **(DIFÍCIL)** Escribir //mapa// y //filtro// usando //acumula//.