Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza:
introalg:taller09_4

Diferencias

Muestra las diferencias entre dos versiones de la página.

Enlace a la vista de comparación

Ambos lados, revisión anteriorRevisión previa
Próxima revisión		Revisión previa
introalg:taller09_4 [2009/04/20 04:05] – lauraintroalg:taller09_4 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 24: Línea 24:
 ====Patrones==== ====Patrones====
  
-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í:+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í:
 <code> <code>
 nombreFunción arg1 arg2 arg3 | patron1 = resultado1 nombreFunción arg1 arg2 arg3 | patron1 = resultado1
Línea 38: Línea 38:
 </code> </code>
    
-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 ''=''.+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. 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.
Línea 51: Línea 51:
 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.  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.+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:+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:
 <code> <code>
 ordena' :: (Int,Int) -> (Int,Int) ordena' :: (Int,Int) -> (Int,Int)
 ordena' (x,y) |   x <= y    = (x,y) ordena' (x,y) |   x <= y    = (x,y)
-              |   x >= y    = (y,x)+              |   x >  y    = (y,x)
 </code> </code>
-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''.+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**:+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**:
 <code> <code>
 ambospositivos :: Int -> Int -> Bool ambospositivos :: Int -> Int -> Bool
-ambospositivos x y | x >= 0 && y >= 0 = true +ambospositivos x y | x >= 0 && y >= 0 = True 
-                   | x >= 0 && y < 0  = false +                   | x >= 0 && y < 0  = False 
-                   | x < 0 && y >= 0  = false +                   | x < 0 && y >= 0  = False 
-                   | x < 0 && y < 0   = false+                   | x < 0 && y < 0   = False
 </code> </code>
 Si nos fijamos un poco, vemos que los tres últimos patrones se pueden colapsar en uno solo, usando un "o" en lugar de "y": Si nos fijamos un poco, vemos que los tres últimos patrones se pueden colapsar en uno solo, usando un "o" en lugar de "y":
 <code> <code>
 ambospositivos' :: Int -> Int -> Bool ambospositivos' :: Int -> Int -> Bool
-ambospositivos' x y | x >= 0 && y >= 0 = true +ambospositivos' x y | x >= 0 && y >= 0 = True 
-                    | x >= 0 || y < 0  = false+                    | x >= 0 || y < 0  = False
 </code> </code>
-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.+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.
 <code> <code>
 ambospositivos'' :: Int -> Int -> Bool ambospositivos'' :: Int -> Int -> Bool
-ambospositivos'' x y | x >= 0 && y >= 0 = true +ambospositivos'' x y | x >= 0 && y >= 0 = True 
-                     | otherwise        = false+                     | otherwise        = False
 </code> </code>
-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:+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:
 <code> <code>
 ambospositivos''' :: Int -> Int -> Bool ambospositivos''' :: Int -> Int -> Bool
Línea 90: Línea 90:
 <code> <code>
 edad :: (Int, Int, Int) -> (Int, Int, Int) -> Int edad :: (Int, Int, Int) -> (Int, Int, Int) -> Int
-edad (diaN,mesN,anioN) (diaA,mesA,anioA) | mesN <= mesA && diaN < diaA = ( anioA - anioN ) - 1 +edad (diaN,mesN,anioN) (diaA,mesA,anioA) | (mesN < mesA) || (mesN == mesA && diaN < diaA) = (anioA - anioN) - 1 
-                                         | otherwise                   = anioA - anioN+                                         | otherwise                                      = anioA - anioN
 </code> </code>
  
Línea 139: Línea 139:
 <code> <code>
 edad' :: (Int, Int, Int) -> (Int, Int, Int) -> Int edad' :: (Int, Int, Int) -> (Int, Int, Int) -> Int
-edad' (diaN,mesN,anioN) (diaA,mesA,anioA) | compruebaParametros (diaN,mesN,anioN) (diaA,mesA,anioA) && mesN <= mesA && diaN < diaA     = ( anioA - anioN ) - 1 +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) && ( mesN >= mesA || diaN >= diaA )  = anioA - anioN+                                          | compruebaParametros (diaN,mesN,anioN) (diaA,mesA,anioA)                                                   = anioA - anioN
 </code> </code>
 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: 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:
 <code> <code>
 e :: (Int, Int, Int) -> (Int, Int, Int) -> Int e :: (Int, Int, Int) -> (Int, Int, Int) -> Int
-e (d,m,a) (f,n,b) | c (d,m,a) (f,n,b) && m <= n && d < f     = ( b - a ) - 1 +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) && (m >= n || d >= f)  = b - a+                  | c (d,m,a) (f,n,b)                                = b - a
 </code> </code>
  
Línea 158: Línea 158:
 <code> <code>
 compruebaParametros' :: (Int, Int, Int) -> (Int, Int, Int) -> Bool 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 +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 +                                                         | 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 +                                                         | 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+                                                         | otherwise    = diaN > 0 && diaN <= 31 && diaA > 0 && diaN <= 31 && mesN > 0 && mesN <= 12 && mesA > 0 && mesA <= 12 && anioN <= anioA = True
 </code> </code>
  
Línea 176: Línea 176:
 compruebaAnterior :: (Int, Int, Int) -> (Int, Int, Int) -> Bool compruebaAnterior :: (Int, Int, Int) -> (Int, Int, Int) -> Bool
 compruebaAnterior (diaN,mesN,anioN) (diaA,mesA,anioA) | anioA == anioN = mesA > mesN || ( mesA == mesN && diaA > diaN ) compruebaAnterior (diaN,mesN,anioN) (diaA,mesA,anioA) | anioA == anioN = mesA > mesN || ( mesA == mesN && diaA > diaN )
-                                                      | anioA > anioN  = true +                                                      | anioA > anioN  = True 
-                                                      | otherwise      = false+                                                      | otherwise      = False
 </code> </code>
  
Línea 242: Línea 242:
 ==== ej.3: ''pip''==== ==== ej.3: ''pip''====
  
-Tomemos como ejemplo la función //pip//:+Tomemos como ejemplo la función ''pip'':
      
   Suponer el siguiente juego: m jugadores en ronda comienzan a decir los números naturales consecutivamente.   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.   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//.+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:+Con un complicado juego de ''mod'' (resto de la división entera) y ''div'' (división entera) podemos llegar a una solución:
  
 <code> <code>
Línea 277: Línea 277:
   True   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. 
- 
-<code> 
-digitos :: Int -> [Int] 
-digitos 0 = [] 
-digitos n = n `mod` 10 : (digitos (n `div` 10)) 
-</code> 
- 
-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] 
  
 =====Definiciones locales===== =====Definiciones locales=====
Línea 332: Línea 311:
 Si no lo hicieron el día anterior, traten de resolver los siguientes problemas: Si no lo hicieron el día anterior, traten de resolver los siguientes problemas:
  
-  - //esVaciaOPrimer0 xs//, //esVaciaOPrimer0 :: [Int] -> Bool// que dada una lista //xs// decida si //xs// es vacía o bien su primer elemento es 0. +  - ''esVaciaOPrimer0 :: [Int] -> Bool'' que dada una lista decida si es vacía o bien su primer elemento es 0. 
-  - //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. +  - ''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 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 +  - ''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 caracteres 
-  - Definan, según su propio criterio para otorgar becas, la 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. Apliquen modularización.+  - Definan, según su propio criterio para otorgar becas, la función ''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. Apliquen modularización.
  
 Nuevos problemas: Nuevos problemas:
introalg/taller09_4.1240200354.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)