Clase 4

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 currificación, en honor al lógico 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]

• Utilizando aplicación parcial en ( /= ), definir la función noEsCero :: Int → Bool que decide si un entero x es distinto a 0.

?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

• 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].

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.

• 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].

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)

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].

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.

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) =

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) =

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) =

• 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.