En la clase anterior vimos que haskell es un lenguaje tipado. La definición de una función suele venir siempre precedida de su signatura de tipos, que tiene la siguiente forma:
nombreFunción :: TipoArgumento1 -> TipoArgumento2 ... -> TipoArgumentoN -> TipoResultado
Por ejemplo:
ordena :: (Int,Int) -> (Int,Int) ambospositivos :: Int -> Int -> Bool edad :: (Int, Int, Int) -> (Int, Int, Int) -> Int cabeza :: [a] -> a cola :: [a] -> [a] esVaciaOPrimer0 :: [Int] -> Bool segundoEsSegundo :: (Int,Int) -> [Int] -> Bool recortaDia :: [Char] -> [Char]
En estos ejemplos hemos visto los tipos más básicos con los que vamos a trabajar en la clase: enteros Int, booleanos Bool, caracteres Char, tuplas (a,b,…,n) y listas [a,b,…].
Vimos también que en haskell se puede expresar muy naturalmente la definición de una función mediante análisis por casos. Estos casos son lo que en haskell se conoce como patrones, y se aplican mediante comparación de patrones (en inglés, pattern matching). Cada patrón está separado por un símbolo = de la forma como se tiene que calcular el resultado si ese patrón evalúa a True. El esquema general de las definiciones de funciones mediante patrones sería así:
nombreFunción arg1 arg2 arg3 | patron1 = resultado1
| patron2 = resultado2
| patron3 = resultado3
...
Los patrones son expresiones booleanas, que en general involucran a las variables a las que se asigna nombre al definir la función (arg1, arg2, x, y, xs). Por ejemplo, podríamos concretar el ejemplo anterior de esta forma.
nombreFunción arg1 arg2 arg3 | arg1 + arg2 == arg3 = arg3
| arg1 - arg2 == arg3 = (-arg3)
| arg1 + arg2 /= arg3 = error "el tercer argumento no es ni la suma ni la resta de los dos primeros"
Para resolver una expresión, el intérprete de haskell funciona de forma muy parecida al de prolog: dada una expresión, el intérprete busca una definición de función con la que pueda unificar, de la misma forma que el intérprete de prolog buscaba una regla con cuya cabeza pudiera unificar la expresión. Luego, si esta definición tiene patrones, el intérprete se fija si esos patrones evalúan a True. Si es así, el intérprete devuelve como resultado lo que hay a la derecha del símbolo =.
Veamos algunos ejemplos de definición de funciones mediante análisis por casos en patrones, y luego veamos cómo funcionan los mecanismos de unificación.
La función ordena (x,y), con signatura de tipos ordena :: (Int,Int) → (Int,Int), toma una tupla de dos enteros y devuelve una tupla con los dos números, ordenados de mayor a menor. Se nos ocurren tres casos posibles con los que tiene que tratar esta función: cuando el primer número es mayor que el segundo, cuando el segundo es mayor que el primero y cuando ambos son iguales. Lo definimos así:
ordena :: (Int,Int) -> (Int,Int)
ordena (x,y) | x < y = (x,y)
| x > y = (y,x)
| x == y = (x,y)
Veamos que hemos hecho una sola definición para la función, en la que hemos asignado nombres de variables a su argumento, llamando x al primer elemento de la tupla e y al segundo. Después hemos desglosado los diferentes casos como patrones alternativos para la función.
Dada una expresión como ordena (4,3) el intérprete busca alguna definición de función con la que pueda unificar. Encuentra que puede unificar con ordena (x,y), asignando a x el valor 4 y a y el valor 3. Con esta asignación de valores a las variables, pasa a evaluar los patrones. El primer patrón, x < y, se convierte en 4 < 3 y evalúa a falso. En cambio, el segundo, x > y, se convierte en 4 > 3 y evalúa a True, con lo cual se calcula el resultado como (y,x), que en este caso será (3,4), que es el resultado que nos devuelve el intérprete.
Fíjense que habría otras formas de definir la función, más legibles, más cortas y más eficientes, ya que algunos casos se evaluarían a True en menos pasos:
ordena' :: (Int,Int) -> (Int,Int)
ordena' (x,y) | x <= y = (x,y)
| x > y = (y,x)
Efectivamente, ordena' es más eficiente que ordena porque en los casos en los que x == y evalúa a True en el primer patrón, mientras que en ordena tiene que evaluar tres patrones para encontrar el que devuelve True.
La función ambospositivos x y, con signatura de tipos ambospositivos :: Int → Int → Bool, dados dos enteros devuelve True si los dos son positivos, se podría escribir de varias formas. La primera es la que uno escribe sin pensar mucho antes de escribir:
ambospositivos :: Int -> Int -> Bool
ambospositivos x y | x >= 0 && y >= 0 = True
| x >= 0 && y < 0 = False
| x < 0 && y >= 0 = False
| x < 0 && y < 0 = False
Si nos fijamos un poco, vemos que los tres últimos patrones se pueden colapsar en uno solo, usando un “o” en lugar de “y”:
ambospositivos' :: Int -> Int -> Bool
ambospositivos' x y | x >= 0 && y >= 0 = True
| x >= 0 || y < 0 = False
Pero además, vemos que también podemos expresar lo mismo de otra forma: que nos devuelva True en el primer caso y False en cualquier otro, usando algún tipo de patrón irrefutable. El patrón irrefutable para las alternativas que se introducen con el símbolo | se escribe con la palabra clave otherwise, que quiere decir en cualquier otro caso y siempre se encuentra al final de una lista de alternativas.
ambospositivos'' :: Int -> Int -> Bool
ambospositivos'' x y | x >= 0 && y >= 0 = True
| otherwise = False
Pero si reflexionamos bien bien sobre el asunto, nos damos cuenta de que en realidad, si el resultado que buscamos es un booleano, ya lo teníamos, delante de nuestros ojos: el primer patrón es un booleano que evalúa a True si los dos enteros son positivos, y False en cualquier otro caso. Podemos escribir el programa más corto, más legible y más eficiente de la siguiente forma:
ambospositivos''' :: Int -> Int -> Bool ambospositivos''' x y = x >= 0 && y >= 0
La función edad es un buen ejemplo de cómo analizar bien el problema, contemplando todos los casos, puede resultar crucial para encontrar la solución adecuada. La función edad, con signatura de tipos edad :: (Int, Int, Int) → (Int, Int, Int) → Int, dadas dos fechas indica los años transcurridos entre ellas. Por ejemplo edad (20,10,1968) (30,4,1987) = 18. Es importante darse cuenta de que, por la forma como se organiza el calendario, dada la segunda fecha, nos encontramos con dos situaciones posibles: que el mes y el día de la primera fecha ya hayan pasado o que no hayan pasado todavía. Si ya ha pasaron el mes y el día de la primera fecha, el resultado se calculará simplemente restando los años. Si no pasaron todavía, el resultado será la resta de los años menos uno:
edad :: (Int, Int, Int) -> (Int, Int, Int) -> Int
edad (diaN,mesN,anioN) (diaA,mesA,anioA) | (mesN < mesA) || (mesN == mesA && diaN < diaA) = (anioA - anioN) - 1
| otherwise = anioA - anioN
Las funciones cabeza y cola aplican patrones sobre listas. Veremos también una forma distinta de usar los patrones, directamente en el momento en que nombramos la función y sus parámetros, sin usar el símbolo |. Por ejemplo, la función cabeza, que devuelve el primer elemento de una lista, puede definirse así:
cabeza :: [a] -> a cabeza (x:xs) = x
Pero qué pasa si decimos cabeza []? El intérprete no encuentra patrón para aplicar. Por lo tanto, hay que definir también qué hacer en el caso de encontrarse con una lista vacía. No podemos devolver una lista vacía porque el resultado tiene que ser un elemento, y no podemos devolver un elemento arbitrario (por ejemplo, 0), porque la lista puede ser de cualquier tipo de elementos, y el resultado tiene que ser del mismo tipo que los elementos de la lista. Por eso usamos la variable de tipo a en la signatura de tipos, para indicar que puede tratarse de cualquier tipo pero que el tipo del resultado tiene que ser el mismo que el de los elementos de la lista. Si el tipo del resultado pudiera ser independiente del tipo de los elementos de la lista, lo escribiríamos así: cabeza :: [a] → b. Entonces, cómo podemos hacer para resolver el problema de la lista vacía? podemos devolver un error, de la siguiente forma:
cabeza' :: [a] -> a cabeza' (x:xs) = x cabeza' [] = error "la lista es vacía y por lo tanto no tiene cabeza!"
Fíjense que para la definición de cabeza podemos usar el patrón irrefutable, porque hay partes de los patrones que no necesitamos recuperar para calcular el resultado. Así, podemos prescindir de xs:
cabeza'' :: [a] -> a cabeza'' (x:_) = x cabeza'' [] = error "la lista es vacía y por lo tanto no tiene cabeza!"
Pero incluso podemos usar el patrón irrefutable en el segundo caso, ya que éste sólo se aplica si el primero falla, y si el primero falla, claramente se tratará de una lista vacía:
cabeza''' :: [a] -> a cabeza''' (x:_) = x cabeza''' _ = error "la lista es vacía y por lo tanto no tiene cabeza!"
Pero esta última solución presenta el inconveniente de que resulta más difícil de leer, así que no deberíamos usarla.
En la definición de cola nos encontramos con un caso muy parecido al de cabeza. Esta función devuelve toda la lista menos el primer elemento, y podría definirse así:
cola :: [a] -> [a] cola (_:xs) = xs cola [] = []
Como el tipo del resultado es lista, para el caso de la lista vacía podemos devolver como resultado una lista vacía, o bien un error, como se prefiera.
Para hacer un programa que resuelva un problema complejo, lo mejor es analizar bien el problema para dividirlo en partes más chicas. Solucionaremos estas partes más chicas cada una por separado, comprobando que efectivamente cada una hace lo que esperamos que haga. Finalmente, las uniremos para llevar a cabo la tarea compleja que nos planteábamos al principio. A esta estrategia se la conoce como modularización, ya que cada una de las partes en las que se divide el problema se llama módulo o subrutina, pero informalmente también se conoce como “divide y vencerás”, ya que lo que hacemos es parecido a dividir un ejército muy numeroso en partes más pequeñas para vencerlas a cada una por separado.
Por ejemplo, para la función de la edad tenemos que suponer que las fechas están siempre bien formadas y que la primera es menor o igual a la segunda. Podríamos incluir esas comprobaciones dentro de la función edad, pero quedaría muy largo y difícil de entender. Hacer una función separada que se encargue de eso y llamarla desde la función edad resulta mucho más elegante, fácil de leer y fácil de modificar. Vendría a ser algo de esta forma:
edad' :: (Int, Int, Int) -> (Int, Int, Int) -> Int
edad' (diaN,mesN,anioN) (diaA,mesA,anioA) | compruebaParametros (diaN,mesN,anioN) (diaA,mesA,anioA) && (mesN < mesA) || (mesN == mesA && diaN < diaA) = ( anioA - anioN ) - 1
| compruebaParametros (diaN,mesN,anioN) (diaA,mesA,anioA) = anioA - anioN
Podemos usar nombres más cortos para que quede toda la función dentro de una línea, pero entonces nos resultará más difícil recordar qué representa cada variable o función:
e :: (Int, Int, Int) -> (Int, Int, Int) -> Int
e (d,m,a) (f,n,b) | c (d,m,a) (f,n,b) && (m < n || (m == n && d < f) = ( b - a ) - 1
| c (d,m,a) (f,n,b) = b - a
Veamos ahora cómo podríamos plantear la función compruebaParametros:
compruebaParametros :: (Int, Int, Int) -> (Int, Int, Int) -> Bool compruebaParametros (diaN,mesN,anioN) (diaA,mesA,anioA) = diaN > 0 && diaN <= 31 && diaA > 0 && diaA <= 31 && mesN > 0 && mesN <= 12 && mesA > 0 && mesA <= 12 && anioN <= anioA
Pero cuidado! esta función permitiría un día 31 de febrero! cómo podemos hacerla más específica? añadiendo una restricción para el mes de febrero, tanto para la primera fecha como para el mes de la segunda:
compruebaParametros' :: (Int, Int, Int) -> (Int, Int, Int) -> Bool
compruebaParametros' (diaN,mesN,anioN) (diaA,mesA,anioA) | mesN == 2 && mesA == 2 = diaN > 0 && diaN <= 28 && diaA > 0 && diaA <= 28 && anioN <= anioA = True
| mesN == 2 = diaN > 0 && diaN <= 28 && diaA > 0 && diaA <= 31 && mesA > 0 && mesA <= 12 && anioN <= anioA = True
| mesA == 2 = diaN > 0 && diaN <= 31 && diaA > 0 && diaA <= 28 && mesN > 0 && mesN <= 12 && anioN <= anioA = True
| otherwise = diaN > 0 && diaN <= 31 && diaA > 0 && diaN <= 31 && mesN > 0 && mesN <= 12 && mesA > 0 && mesA <= 12 && anioN <= anioA = True
Y qué pasa con los meses que tienen 30 días y no 31? y con los años bisiestos? la función se complica… si queremos que resulte legible y modificable, tendremos que modularizarla. Una opción de modularización sería lo que sigue:
compruebaParametros'' :: (Int, Int, Int) -> (Int, Int, Int) -> Bool
compruebaParametros'' (diaN,mesN,anioN) (diaA,mesA,anioA) | compruebaMesDia (diaN,mesN,anioN) && compruebaMesDia (diaA,mesA,anioA) && compruebaAnterior (diaN,mesN,anioN) (diaA,mesA,anioA)
compruebaMesDia :: (Int,Int,Int) -> Bool
compruebaMesDia (mes,dia,anio) | mes == 2 = dia > 0 && ( ( bisiesto anio && dia <= 29 ) || dia <= 28 )
| mes == 4 || mes == 6 || mes == 9 || mes == 11 = dia > 0 && dia <= 30
| otherwise = dia > 0 && dia <= 31
compruebaAnterior :: (Int, Int, Int) -> (Int, Int, Int) -> Bool
compruebaAnterior (diaN,mesN,anioN) (diaA,mesA,anioA) | anioA == anioN = mesA > mesN || ( mesA == mesN && diaA > diaN )
| anioA > anioN = True
| otherwise = False
Como ven, un problema complejo resulta mucho más fácil de abordar si hacemos el esfuerzo inicial de analizarlo con detenimiento, detectar cuáles son sus subpartes y las relaciones entre ellas, y programar en función de ese análisis.
Imaginemos un elaborado sistema de descuentos en un supermercado. Por ejemplo, imaginemos que el super hace un descuento del 20% en el monto total si hacemos una compra de 257 pesos, de 350 pesos, de 489 pesos o mayor a 1000. En cambio, si hacemos una compra menor a 100 pesos el descuento es del 5%. Si el monto está entre 200 y 500 pesos, pero no es ninguno de los anteriores, el descuento es del 10%, si es mayor a 500 pero menor a 1000, el descuento es del 15%, excepto si se trata de una compra de 768 pesos, de 999 o de 573, que tienen un descuento del 20 por ciento. Además, los descuentos también dan puntos: los del 20% aportan un número de puntos 10 veces mayor al monto total de la compra, los del 15% aportan un número de puntos 5 veces mayor al monto total de la compra, los del 10% aportan el doble de puntos que el monto de la compra, y si la compra es menor a 200 pesos, el número de puntos es igual al monto de la compra. Por último, si compramos con tickets, en un descuento del 20% nos devuelven el 10% del monto total, en un descuento del 15% nos devuelven el 5% y en un descuento del 10% nos devuelven en 2%. La devolución en tickets se devuelve en tickets, no se aplica un descuento al monto total a pagar.
Cómo podemos hacer un programa que nos calcule el descuento, los puntos y el descuento en tickets para un monto dado? Veamos una función que traduzca literalmente lo que dijimos acá arriba.
descuento :: (Float,Bool) -> (Float,Float,Float)
-- argumento: un par que representa el monto (Float) y si tenemos tickets (Bool)
-- resultado: una tresupla (Float,Float,Float) que representa el monto total,
-- restando el descuento correspondiente, el número de puntos
-- y el descuento en tickets, respectivamente.
descuento (x,y) | x == 257 && y = ( x - 0.2*x , 10*x, 0.1*x)
| x == 257 && not y = ( x - 0.2*x , 10*x, 0)
| x == 350 && y = ( x - 0.2*x , 10*x, 0.1*x)
| x == 350 && not y = ( x - 0.2*x , 10*x, 0)
| x == 489 && y = ( x - 0.2*x , 10*x, 0.1*x)
| x == 489 && not y = ( x - 0.2*x , 10*x, 0)
| x > 1000 && y = ( x - 0.2*x , 10*x, 0.1*x)
| x > 1000 && not y = ( x - 0.2*x , 10*x, 0)
| x == 768 && y = ( x - 0.2*x , 10*x, 0.1*x)
| x == 768 && not y = ( x - 0.2*x , 10*x, 0)
| x == 999 && y = ( x - 0.2*x , 10*x, 0.1*x)
| x == 573 && not y = ( x - 0.2*x , 10*x, 0)
| x > 500 && x <= 1000 && y = ( x - 0.15*x , 5*x, 0.05*x)
| x > 500 && x <= 1000 && not y = ( x - 0.15*x , 5*x, 0)
| x > 200 && x <= 500 && y = ( x - 0.1*x , 2*x, 0.02*x)
| x > 200 && x <= 500 && not y = ( x - 0.1*x , 2*x, 0)
| x <= 200 = ( x , x , 0)
Como pueden ver, este código es muy grande, bastante ilegible y difícil de mantener. Qué haríamos, por ejemplo, si ahora el supermercado decidiera reducir el número de puntos que dá a los descuentos del 20%? Aplicando la estrategia “divide y vencerás”, podemos crear algo mucho más compacto, legible y fácil de mantener:
descuento' :: (Float,Bool) -> (Float,Float,Float)
descuento' (x,y) | x == 257 || x == 350 || x == 489 || x == 768 || x == 999 || x == 573 = descuento20 (x,y)
| x > 1000 = descuento20 (x,y)
| x > 500 && x <= 1000 = descuento15 (x,y)
| x > 200 && x <= 500 = descuento10 (x,y)
| x <= 200 = descuento0 (x,y)
descuento20 :: (Float,Bool) -> (Float,Float,Float)
descuento20 (x,y) | y == True = ( x - 0.2*x , 10*x, 0.1*x)
| y == False = ( x - 0.2*x , 10*x, 0)
descuento15 :: (Float,Bool) -> (Float,Float,Float)
descuento15 (x,y) | y == True = ( x - 0.15*x , 5*x, 0.05*x)
| y == False = ( x - 0.15*x , 5*x, 0)
descuento10 :: (Float,Bool) -> (Float,Float,Float)
descuento10 (x,y) | y == True = ( x - 0.1*x , 2*x, 0.02*x)
| y == False = ( x - 0.1*x , 2*x, 0)
descuento0 :: (Float,Bool) -> (Float,Float,Float)
descuento0 (x,y) = ( x , x , 0)
Tomemos como ejemplo la función pip:
Suponer el siguiente juego: m jugadores en ronda comienzan a decir los números naturales consecutivamente. Cuando toca un multiplo de 7 o un número con algún dígito igual a 7, el jugador debe decir pip en lugar del número.
Se pide: encontrar un predicado pip n, pip :: Int → Bool que dado un número 0 ⇐ n < 10000 devuelva diga cuando el jugador debe decir pip.
Con un complicado juego de mod (resto de la división entera) y div (división entera) podemos llegar a una solución:
pip :: Int -> Bool pip n = n `mod` 7 == 0 || n `mod` 10 == 7 || (n `div` 10) `mod` 10 == 7 || (n `div` 100) `mod` 10 == 7 || (n `div` 1000) `mod` 10 == 7
Si en cambio dividimos el problema en partes, obtenemos una versión mucho más simple de comprender.
pip' :: Int -> Bool pip' n = n `mod` 7 == 0 || unidad n == 7 || decena n == 7 || centena n == 7 || unidadDeMil n == 7 unidad, decena, centena, unidadDeMil :: Int -> Int unidad n = n `mod` 10 decena n = (n `div` 10) `mod` 10 centena n = (n `div` 100) `mod` 10 unidadDeMil n = (n `div` 1000) `mod` 10
Siempre es conveniente ser desconfiado y probamos que ambas funciones sean iguales en el rango [0,9999]
Main> filter pip [0..9999] == filter pip' [0..9999] True
A veces queremos modularizar pero queremos que los módulos sólo estén disponibles para el programa que estamos haciendo en este momento, y no para todo el resto. Por ejemplo, si queremos definir la función “compruebaParametros” de forma distinta para cada función.
Podemos definir módulos (en el caso de haskell, funciones) de forma que sólo las pueda usar un determinado programa, definiéndolas localmente. Vimos un ejemplo de esto en la clase anterior, para definir la función que calcula el área de un prisma:
area :: Int -> Int -> Int -> Int
area alto ancho fondo = 2*frente + 2*lado + 2*tapa
where
frente = alto * ancho
lado = alto * fondo
tapa = ancho * fondo
En este ejemplo hemos definido localmente las funciones frente, lado y tapa. Eso quiere decir que si tratamos de usarlas fuera de esta función, el intérprete nos dirá que no las conoce, o aplicará otras funciones con el mismo nombre pero definidas en otro lugar. En cambio, cuando usemos la función area, vamos a usar las definiciones que hemos definido localmente. Las variables definidas en la definición que contiene las definiciones globales siguen manteniendo su referencia en las definiciones locales. En este caso, las funciones frente, lado y tapa usan las variables alto, ancho y fondo como si estuviéramos en la función area, porque de hecho estamos definiendo cosas dentro en la función area.
Para definir funciones locales a otra función, usamos la palabra clave where y el espacio horizontal y vertical: las definiciones locales (y la palabra clave where) tienen que estar como mínimo un espacio más a la derecha que la función dentro de la cual se definen, y no pueden estar separadas por una línea en blanco. Veamos qué pasa cuando no respetamos estas normas de sintaxis? Veamos por ejemplo si no respetamos el espacio horizontal:
area a b c = 2*frente + 2*lado + 2*tapa where frente = a*b lado = b*c tapa = a*c
El intérprete va a entender que las funciones frente, lado y tapa son independientes de area, por lo tanto no va a entender que la variable b es la misma que la de la definición de area.
Main> :e ERROR "1.hs":69 - Undefined variable "b"
Si no lo hicieron el día anterior, traten de resolver los siguientes problemas:
esVaciaOPrimer0 :: [Int] → Bool que dada una lista decida si es vacía o bien su primer elemento es 0.segundoEsSegundo :: (Int,Int) → [Int] → Bool que dada una tupla de enteros y una lista de enteros comprueba si el segundo elemento de la tupla es igual al segundo elemento de la lista.recortaDia :: [Char] → [Char] que dada una lista de caracteres, comprueba si las letras de la lista forman el nombre de un día de la semana, si es así, si el día no es del fin de semana, devuelven la primera letra solamente, en cambio, si el día es de fin de semana, devuelven el nombre del día completo. Ayuda: fíjense que el resultado siempre debe ser una lista de caracteresotorgaBeca :: (Int,Int,Int) → String que dada una tresupla con la edad del candidato, su promedio y su ingreso anual, devuelva una recomendación sobre su adecuación para un programa de becas, en tres rangos: “Muy Adecuado”, “Adecuado” y “Poco Adecuado”. Aplicando “divide y vencerás”, usar procedimientos distintos para candidatos menores de 30 años y mayores de 30, para candidatos con un ingreso anual mayor que 15000, entre 15000 y 10000 y menor que 10000, y para candidatos con un promedio mayor a 8, entre 6 y 8, entre 6 y 4 y menor a 4. Apliquen modularización.Nuevos problemas:
averaver, con signatura de tipos averaver :: (Int,Int,Int) → (Int,Int,Int) que, dada una tresupla de enteros, si todos son positivos, invierte su orden, si todos son negativos, los cambia a positivos, y en cualquier otro caso, devuelve la misma tresupla. Ayuda: usar otherwise.ordenaSiPositivos, con signatura de tipos ordenaSiPositivos :: (Int,Int) → (Int,Int), que ordena los números de una tupla de enteros si ambos son positivos, pero si son negativos los deja sin ordenar. Ayuda: reusen funciones que ya han definido antes!!Viejos problemas, nuevas soluciones: re-piensen los problemas difíciles que planteamos en la segunda clase de prolog usando modularización:
conectadas(Tarragona,Barcelona). . ¿Cómo sería un programa que nos ayudara a saber si podemos llegar de una ciudad a otra, es decir, si existe una lista de conexiones que nos lleve de una ciudad a otra, o bien eso es imposible? Primero, traten de hacer un programa que nos diga si podemos llegar de una ciudad a otra directamente o bien en dos o en tres pasos…