Herramientas de usuario

Herramientas del sitio


introalg:taller07_2

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 Sucesión de Fibonacci que la vemos implementada en el siguiente programa 1).

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 2).

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 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 apartado sobre indentación del wikibook de Haskell.

Para saber más, vean la descripción informal o más formal de este tema en el 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.
1)
Esta es una versión muy poco eficiente.
2)
A bajo nivel un par y una lista no son distintos, de hecho [1,2,3] = (1,(2,(3,[]))) en la representación interna.
introalg/taller07_2.txt · Última modificación: 2018/08/10 03:03 por 127.0.0.1