====== Clase 2 ====== ===== Comparación de Patrones (pattern matching) ===== ==== Tuplas ==== En la clase anterior vimos de manera implícita como podíamos "destruir" una tupla en sus componentes segundo :: (Int,Int) -> Int segundo (x,y) = y Haskell brinda dos expresiones idiomáticas con patrones que son útilies para escribir código más claro. * Patrones nombrados * Comodines Veamos un ejemplo del primero ordenaSiPositivos :: (Int,Int) -> (Int,Int) ordenaSiPositivos p@(x,y) | ambosPositivos x y = ordena p | otherwise = p Los **patrones nombrados** son una forma de //referirse a una parte del patrón// en el lado derecho de la expresión. En cuanto a los **comodines** los utilizamos cuando no necesitamos darle nombre a alguna parte del patrón. Por ejemplo si queremos devolver la tercera coordenada de una tupla, las dos primeras no las necesitamos y esto lo indicamos con un comodín. tercero3 :: (Int,Int,Int) -> Int tercero3 (_,_,z) = z ==== Numéricos ==== Los patrones numéricos consisten en constantes y expresiones numéricas simples. esCeroOUno :: Int -> Bool esCeroOUno 0 = True esCeroOUno _ = False esCeroOUno 1 = True Si probamos Main> esCeroOUno 1 False El problema surge del hecho que los patrones tienen un **orden**. Se evalúan de arriba a abajo y el primero que coincide se toma. \\ En éste caso el segundo patrón es **irrefutable** y con //1// de vuelve //True//. \\ El programa correcto sería: esCeroOUno :: Int -> Bool esCeroOUno 0 = True esCeroOUno 1 = True esCeroOUno _ = False Un ejemplo típico que ejercita los patrones numéricos es la [[http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Fibonacci | Sucesión de Fibonacci]] que la vemos implementada en el siguiente programa ((Esta es una versión muy poco eficiente.)). fib :: Int -> Int fib 0 = 1 fib 1 = 1 fib (n+2) = fib (n+1) + fib n ==== Listas ==== Con las listas tenemos un mecanismo básico para **dividir cabeza y cola**, tal y como si fuera un par ((A bajo nivel un par y una lista no son distintos, de hecho //[1,2,3] = (1,(2,(3,[])))// en la representación interna.)). esVacia :: [a] -> Bool esVacia [] = True esVacia (x:xs) = False Por cierto que podemos usar comodines en ambas partes del segundo patrón o bien un patrón irrefutable y comodín a la vez. esVacia' :: [a] -> Bool esVacia' [] = True esVacia' (_:_) = False esVacia'' :: [a] -> Bool esVacia'' [] = True esVacia'' _ = False Veamos que tenemos más posibilidades que cabeza y cola. Definimos un predicado que decide si //hay 2 o más elementos en una lista// y damos dos versiones una bastante legible y la otra ultracompacta y un tanto más críptica que hace uso y abuso del orden de evaluación de los patrones, patrones irrefutables y comodines. alMenos2 :: [a] -> Bool alMenos2 [] = False alMenos2 [x] = False alMenos2 (x:y:xs) = True alMenos2' :: [a] -> Bool alMenos2' (_:_:_) = True alMenos2' _ = False La probamos para ver si funciona de manera correcta y notamos el uso de **listas de listas** para que //map// haga operar a la función //alMenos2// sobre cada elemento. Main> map alMenos2 [ [], [1..1], [1..2], [1..3], [1..4], [1..10000] ] [False,False,True,True,True,True] Main> map alMenos2' [ [], [1..1], [1..2], [1..3], [1..4], [1..10000] ] [False,False,True,True,True,True] ==== Mezclas ==== Podemos combinar de manera libre estas posibilidades como se muestra a continuación. sumaCabeza :: [(Int,Int)] -> Int sumaCabeza [] = 0 sumaCabeza ((x,y):xs) = x+y ordenaCabeza :: [(Int,Int)] -> (Int,Int) ordenaCabeza [] = error "No hay cabeza" ordenaCabeza (h@(x,y):xs) = ordena h where ordena (x,y) | x<=y = (x,y) | otherwise = (y,x) Probamos estos códigos Main> sumaCabeza [(1,5),(1,2)] 6 Main> ordenaCabeza [(10,20),(10,20)] (10,20) Main> ordenaCabeza [(20,10),(10,20)] (10,20) Main> ordenaCabeza [] Program error: No hay cabeza Main> ordenaCabeza (take 10 (repeat (2,1))) (1,2) ===== Dividiendo el problema en partes ===== Muchas veces es posible llegar a una solución mas elegante y legible dividiendo el problema en partes y haciendo que la solución se obtenga componiendo las partes. Es una versión sin recursión del [[http://es.wikipedia.org/wiki/Algoritmo_divide_y_vencer%C3%A1s | Divide y Vencerás]]. 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// y //div// 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 Y hasta podemos generalizar las funciones //unidad, decena, etc.// en una que nos dé el dígito n-ésimo de la representación decimal, pero para eso necesitamos usar **funciones recursivas**.\\ Eso será tema de la próxima clase, pero veamos de todas maneras la "pinta" de la función. digitos :: Int -> [Int] digitos 0 = [] digitos n = n `mod` 10 : (digitos (n `div` 10)) La probamos para ver como opera Main> digitos 0 [] Main> digitos 1 [1] Main> digitos 10 [0,1] Main> digitos 120 [0,2,1] Main> digitos 123123123 [3,2,1,3,2,1,3,2,1] ==== Otro ejemplo ==== 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) ===== Estilo de Código (coding style) ===== ==== Reglas de sangrado (layout) (distribución) ==== Haskell usa una sintaxis bi-dimensional que evita el uso de puntuación a que se ven obligados otros lenguajes para evitar la ambigüedad al distinguir bloques en un programa. Por esta razón, en Haskell podemos escribir sin usar los miles de punto y coma, paréntesis y llaves que encontramos en otros lenguajes. Sin embargo, Haskell también permite la opción de usar esta puntuación para separar los diferentes bloques de un programa. Las reglas de distribución son bastante intuitivas, sencillamente, hay que tener en cuenta: * las funciones se separan entre ellas por una o más líneas en blanco * el código que forma parte de una expresión (o bloque) tiene que indentarse más adentro que la línea que contiene el principio de esa expresión. Por ejemplo, cuando usamos una lista de instrucciones de la misma clase dentro de una función, deben estar todas indentadas a la misma altura, como si estuvieran formando una **columna**, o, si no, más adentro. Vean en el siguiente ejemplo como "//frente//", "//lado//" y "//tapa//" están todas a la misma altura de indentación, formando una columna, y más indentadas que la palabra "//where//", que introduce la expresión dentro de la cual se encuentran: area a b c = 2*frente + 2*lado + 2*tapa where frente = a*b lado = b*c tapa = a*c PREGUNTA: ¿Cómo podemos escribir esta función usando puntuación en lugar de indentación? Esto sigue siendo válido si escribimos: area a b c = 2*frente + 2*lado + 2*tapa where frente = a*b lado = b*c tapa = a*c Pero no cuando las //definiciones locales// están en la misma columna que la definición global de ''area''. area a b c = 2*frente + 2*lado + 2*tapa where frente = a*b lado = b*c tapa = a*c Simplemente no sabe que el ''b'' de la definición de frente es el parámetro ''b'' de ''area''. Main> :e ERROR "1.hs":69 - Undefined variable "b" Para ver más ejemplos, vayan al [[http://en.wikibooks.org/wiki/Haskell/Indentation|apartado sobre indentación]] del [[http://en.wikibooks.org/wiki/Haskell/|wikibook de Haskell]]. Para saber más, vean la [[http://haskell.org/onlinereport/lexemes.html#lexemes-layout|descripción informal]] o [[http://haskell.org/onlinereport/syntax-iso.html#layout|más formal]] de este tema en el [[http://haskell.org/onlinereport/|Haskell Report]]. Y ya que estamos, sepan que toda **línea** que comienza por dos guiones (o signos "menos") no será interpretada por el intérprete de Haskell, de esta forma se pueden introducir comentarios en los programas. Y para evitar que se interpreten **bloques completos**, a éstos los demarcamos con ''{- bloque -}'' -- Nada de esto se toma {- Y esto tampoco! -} ==== Case sensitiveness (sensibilidad a la caja) ==== Como habrán notado, en Haskell no se pueden usar minúsculas y mayúsculas indistintamente, ya que el intérprete es sensible a la caja de los caracteres, es decir, ve como caracteres distintos una "A" y una "a". Esto significa que una función //primeroTres// será distinta de una función //primerotres//, y que por lo tanto si hemos definido //primeroTres// en nuestro script, no podemos pretender llamarlo como //primerotres// en el intérprete. Por otro lado, además de ser consistentes en el uso de mayúsculas y minúsculas, hay ciertas cosas que no podemos olvidar al escribir Haskell: * toda palabra que comienza con **mayúscula** es un **tipo de datos**: //Int, Bool, Char, Float, String//,... por lo tanto, nuestras funciones y variables no pueden empezar con mayúscula porque el intérprete va a pensar que estamos hablando de un tipo de datos y, si no encuentra un tipo con el nombre que le hemos dado, nos dará un error. * los nombres de **funciones y variables** comienzan con **minúscula** ==== Nombres de variables ==== En general se intenta que el código sea auto explicativo, en el sentido que baste con leerlo para comprender como funciona. Algo que resulta muy sencillo y útil es dar nombres significativos a las variables. Podríamos haber escrito la función área de la siguiente manera. area a1 a2 a3 = 2*a4 + 2*a5 + 2*a6 where a4 = a1*a2 a5 = a2*a3 a6 = a1*a3 o bien de manera equivalente e igualmente eficiente, pero mucho más comprensible: area b a p = 2*frente + 2*lado + 2*tapa where frente = b * a lado = p * a tapa = b * p ===== Ejercicios ===== * Definir la función //cabeza.xs//, //cabeza : [a] --> a//, que devuelve el primer elemento de una lista. probar con [1,2,3], con [3,3,3] y con []. * Definir la función //cola.xs//, //cola : [a] --> [a]//, que devuelve toda la lista menos el primer elemento. probar con [1,2,3], con [3,3,3] y con []. * Definir una función //esVaciaOPrimer0.xs//, //esVaciaOPrimer0 : [Int] -> Bool// que dada una lista //xs// decida si //xs// es vacía o bien su primer elemento es 0. probar con [1,2,3], con [3,3,3], con [0], con [0,1] y con []. * Definir una función //segundoEsSegundo.(x,y).zs//, //segundoEsSegundo : (Int,Int) -> [Int] -> Bool// que dada una tupla de enteros //(x,y)// y una lista de enteros //zs// comprueba si el segundo elemento de la tupla es igual al segundo elemento de la lista. probar con (1,2) y [3,2,4,5], (0,0) y [], (1,2) y [2,3,4,5]. * Definir una función //recortaDia.xs//, //recortaDia : [Char] -> [Char]// que dada una lista de caracteres //xs//, 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 caracteres! probar con ['l','u','n','e','s'], ['d','o','m','i','n','g','o'], []. * Definir una función //otorgaBeca.(x,y,z)//, //otorgaBeca : (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.