Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza:
introalg:taller09_3

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_3 [2009/04/11 23:41] – lauraintroalg:taller09_3 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 8: Línea 8:
  
 A Hugs se lo invoca desde la //línea de comandos// o cliqueando sobre el icono en nuestro entorno gráfico. A Hugs se lo invoca desde la //línea de comandos// o cliqueando sobre el icono en nuestro entorno gráfico.
-Una vez que el intérprete está activo, la pantalla se presenta con un //prompt// a la espera de **expresiones** a ser evaluadas o **comandos**.+Una vez que el intérprete está activo, la pantalla se presenta con un //prompt// a la espera de //comandos// o //expresiones// a ser evaluadas.
 <code> <code>
   [laura@azul Taller]$ hugs   [laura@azul Taller]$ hugs
Línea 24: Línea 24:
 </code> </code>
  
-De este modo Hugs se convierte en una calculadora, esperando que se introduzca una expresión para evaluarla e imprimir el resultado. Después, nuestra calculadora Hugs queda lista para volver a pedir una expresión.  +A diferencia de prolog, el intérprete de haskell tiene muchas funciones ya definidas, las que se incluyen en el llamado [[http://www.haskell.org/onlinereport/standard-prelude.html | preludio estándar]]. Entre ellas están todas las aritméticas y las lógicas básicas, pero también otras muchas, como por ejemplo "reverse". Veamos algunos ejemplos de cómo funcionan:
- +
-A diferencia de prolog, el intérprete de haskell tiene muchas funciones ya definidas, las que se incluyen en el llamado [[http://www.haskell.org/onlinereport/standard-prelude.html | preludio estándar]]. Entre ellas están todas las aritméticas y las lógicas básicas, pero también otras muchas, como por ejemplo "reverse":+
  
 <code> <code>
Línea 46: Línea 44:
   [laura@azul Taller]$   [laura@azul Taller]$
 </code> </code>
-Así volvemos al modo normal de la computadora. 
  
 =====Incorporando conocimiento===== =====Incorporando conocimiento=====
  
-Para poder dar nuevas definiciones y/o funciones, además de las que se encuentran en el [[http://www.haskell.org/onlinereport/standard-prelude.html | preludio estándar]], necesitamos escribir un programa de Haskell. Lo haremos con un archivo terminado en ''.hs'', donde escribiremos en texto plano todas las definiciones que conforman el programa. +Para poder dar nuevas definiciones y/o funciones, además de las que se encuentran en el [[http://www.haskell.org/onlinereport/standard-prelude.html | preludio estándar]], necesitamos escribir un programa de haskell. Lo haremos con un archivo terminado en ''.hs'', donde escribiremos en texto plano todas las definiciones que conforman el programa.
- +
-Como ejemplo, vamos a ver todo el proceso de **creación del programa - carga en memoria - prueba - modificación del programa - recarga**, con el Ejercicio 8.3 del apunte [[http://cs.famaf.unc.edu.ar/introalg/calculo_extracto.pdf|Extracto del Cálculo de Programas]]: +
- +
-  sgn :: Int → Int  +
-  -- dado un entero x, //sgn// retorna su signo, de la siguiente forma:  +
-  -- retornará 1 si x es positivo, -1 si es negativo y 0 en cualquier otro caso.+
  
 +Como ejemplo, vamos a ver todo el proceso de **creación del programa - carga en memoria - prueba - modificación del programa - recarga**, con el Ejercicio 8.3 del apunte [[http://cs.famaf.unc.edu.ar/introalg/calculo_extracto.pdf|Extracto del Cálculo de Programas]], que tiene el siguiente enunciado:
 +<code>
 +sgn :: Int → Int 
 +-- dado un entero x, //sgn// retorna su signo, de la siguiente forma: 
 +-- retornará 1 si x es positivo, -1 si es negativo y 0 en cualquier otro caso.
 +</code>
 Para crear un programa se puede hacer mediante un editor de texto cualquiera (kate, bloc de notas, emacs...) o, si no, se puede invocar el comando para editar un (nuevo) archivo '':e cap8.hs'' desde el intérprete mismo:  Para crear un programa se puede hacer mediante un editor de texto cualquiera (kate, bloc de notas, emacs...) o, si no, se puede invocar el comando para editar un (nuevo) archivo '':e cap8.hs'' desde el intérprete mismo: 
 <code> <code>
-  Hugs.Base> :e cap8.hs+Hugs.Base> :e cap8.hs
 </code> </code>
-Una posible solución para el problema de la función signo es la siguiente:+Se nos ocurre la siguiente solución para el problema de la función ''sgn'':
 <code> <code>
 sgn :: Int -> Int sgn :: Int -> Int
Línea 74: Línea 71:
 ERROR "cap8.hs":4 - Syntax error in input (unexpected `=') ERROR "cap8.hs":4 - Syntax error in input (unexpected `=')
 </code> </code>
-Pero el intérprete indica un error! Por qué? Porque "=" es el símbolo de definición, mientras que la comparación es "==".+Pero el intérprete indica un error! Por qué? En la última línea del programa, vemos que usamos el mismo símbolo "=" para dos cosas muy distintas: para separar una condición de la forma como se calcula el resultado si la condición es cierta y para comparar dos valores. Pero en realidad el símbolo "=" sólo se puede usar para definir. Para comparar tenemos que usar el símbolo "==".
  
 Las traducciones de los símbolos son más o menos directas, de todas formas preparamos una tabla de [[http://cs.famaf.unc.edu.ar/introalg/PDF/traduccion.pdf|Traducción de "Cálculo de Programas" a Haskell]]. Las traducciones de los símbolos son más o menos directas, de todas formas preparamos una tabla de [[http://cs.famaf.unc.edu.ar/introalg/PDF/traduccion.pdf|Traducción de "Cálculo de Programas" a Haskell]].
  
-Para solucionar el error, volvemos a editar el script con '':e'' (el nombre ya no lo necesitamos ya que tenemos cargado este script) y corregimos ''x=0'' por ''x==0''.+Para solucionar el error, corregimos ''x=0'' por ''x==0''.
 <code> <code>
 sgn :: Int -> Int sgn :: Int -> Int
Línea 92: Línea 89:
 Ahora sí, la función es correcta y por ello el intérprete nos muestra el prompt ''Main'', que indica que hemos cargado alguna función más de las que hay en el preludio estándar, y que las funciones que hemos cargado son correctas. Ahora sí, la función es correcta y por ello el intérprete nos muestra el prompt ''Main'', que indica que hemos cargado alguna función más de las que hay en el preludio estándar, y que las funciones que hemos cargado son correctas.
  
-Podemos probar la nueva función con //casos de test//:+Podemos probar la nueva función con //casos de test//, y vamos a fijarnos en qué casos nos dá errores y por qué: 
 +<code> 
 +Main> sgn 1 
 +1 
 +Main> sgn 0 
 +0 
 +</code> 
 +Ningún problema: funciona para los casos del manual :). 
 +<code> 
 +Main> sgn 123123123123
  
-  Main> sgn 1 +Program error: arithmetic overflow
-  1 +
-  Main> sgn 0 +
-  0 +
-  Main> sgn -1 +
-  ERROR - Cannot infer instance +
-  *** Instance   : Num (Int -> Int) +
-  *** Expression : sgn - 1+
      
-  Main> sgn (-1) +Main> sgn 123123123 
-  -1 +1 
-  Main> sgn 123123123123 +</code> 
-   +El número es demasiado grande y el intérprete se queda sin capacidad para tratarlo, si le damos un número más chico, sí funciona. 
-  Program error: arithmetic overflow +<code> 
-   +Main> sgn (-1 
-  Main> sgn 123123123 +ERROR - Syntax error in expression (unexpected end of input) 
-  1 +</code> 
-  Main> sgn 1.1 +Error de sintaxis: no cerramos el paréntesis! 
-  ERROR - Cannot infer instance +<code>   
-  *** Instance   : Fractional Int +Main> sgn "hola" 
-  *** Expression : sgn 1.1 +ERROR - Type error in application 
-   +*** Expression     : sgn "hola" 
-  Main> sgn (-1 +*** Term           : "hola" 
-  ERROR - Syntax error in expression (unexpected end of input) +*** Type           : String 
-   +*** Does not match : Int 
-  Main> sgn "hola" +</code> 
-  ERROR - Type error in application +Error de tipos: la función está definida para trabajar con enteros (Int), no con el tipo cadena de caracteres (String). 
-  *** Expression     : sgn "hola" +<code> 
-  *** Term           : "hola" +Main> sgn 1.1 
-  *** Type           : String +ERROR - Cannot infer instance 
-  *** Does not match : Int +*** Instance   : Fractional Int 
-   +*** Expression : sgn 1.1 
-  Main> map sgn [-10..10] +</code> 
-  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,1,1,1,1,1,1,1,1,1,1]+Error de tipos: la función está definida para trabajar con enteros (Int), no con el tipo decimal (Fractional). 
 +<code> 
 +Main> sgn -1 
 +ERROR - Cannot infer instance 
 +*** Instance   : Num (Int -> Int) 
 +*** Expression : sgn - 1
  
 +Main> sgn (-1)
 +-1
 +</code>
 +Error de precedencia: la aplicación de funciones tiene precedencia sobre cualquier otra operación, y por lo tanto el intérprete aplica primero la función. Al hacerlo, se encuentra con un error de tipos: en lugar de un número, encuentra como argumento otra función (la función "-"), y ese no es el tipo de dato que está esperando, porque está esperando un entero (Int). Para evitar ese problema, usamos paréntesis para indicar que primero hay que aplicar "-" a "1", el resultado de eso será un número entero y a eso sí vamos a poder aplicarle la función ''sgn''. 
  
-Notamos los distintos tipos de errores que se producen por problemas de +=====Cómo declaramos el conocimiento en haskell?=====
-  * Precedencia (''sgn -1'') +
-  * Tipos (''sgn 1.1'') +
-  * Sintaxis (''sgn (-1'')+
  
 +La declaración del conocimiento en haskell tiene algunos parecidos y algunas diferencias con la declaración del conocimiento en prolog. 
  
-===== Tipos de datos, comparación de patrones =====+Vemos que haskell declara el conocimiento en forma de //funciones// y no mediante //reglas//. Sin embargo, las funciones son muy parecidas a las cláusulas de Horn que veíamos en prolog: encontramos una cabeza y un cuerpo, separados por el símbolo "=". Veamos más atentamente la función ''sgn''. 
 +<code> 
 +sgn :: Int -> Int 
 +sgn x   | 0<x    = 1 
 +        | x<0    = -1 
 +        | x==0   = 0 
 +</code> 
 +La primera línea es la //signatura de tipos//, de la que vamos a hablar en la siguiente sección. Las otras tres líneas son la definición de la función. Podemos ver que esta función está definida por análisis por casos, distinguiendo tres casos: cuando x es positivo (''0<x''), cuando x es negativo (''x<0'') o cuando x es 0 (''x==0''). Estos tres casos se relacionan entre ellos mediante el símbolo "|", que indica disyunción. El intérprete va a ir evaluando cada uno de los casos en el orden en el que los encuentra en el archivo del programa, y cuando encuentre uno con el que pueda unificar lo que quiere resolver, lo va a aplicar y va a terminar.
  
-Haskell es un lenguaje tipado, es decir, todos dato pertenece a una clase o tipo de datos. En general, la definición de una función va precedida de su //signatura de tipos//, donde declaramos los tipos que están involucrados en la función:+Por lo tanto, lo que hay a la izquierda del símbolo "|" tiene una función parecida a la de la cabeza de una regla de prolog, lo que hay a la derecha sería parecido al cuerpo de una regla, con algunas diferencias. Noten que la cabeza de una regla prolog tiene toda la información sobre el nombre de la función y sus argumentos, al igual que la parte izquierda de una definición de función en haskell. Sin embargo, en haskell hay un elemento implícito, el resultado, que en prolog debe estar explícito. Si escribiéramos la función ''sgn'' en prolog, la escribiríamos así:
 <code> <code>
-  sgn :: Int -> Int     -- esta línea es la signatura de tipos de la función sgn +sgn(X,Y) :- (0<X , Y=1) ; (X<0 , Y=(-1)) ; (X=0, Y=0). 
-  sgn x   | 0<x   = 1 +</code> 
-          | x<0   = -1 +y la consultaríamos de la siguiente manera: 
-          | x==0  = 0+<code> 
 +?- sgn(33,Y). 
 +Y = 1 . 
 +</code> 
 +De esta forma, indicamos que la variable "Y" va a guardar el valor del resultado de la función, lo cual está implícito en haskell. Como ven, aunque en los dos lenguajes escribamos programas que calculan lo mismo con los mismos resultados, escribir la función ''sgn'' resulta mucho más natural en haskell que en prolog. Esto es así porque cada lenguaje está orientado a tratar un cierto tipo de problemas. 
 + 
 +Al igual que en prolog, las variables que se usan en haskell tienen alcance únicamente dentro de la definición de la función, pero, a diferencia de prolog, las variables se escriben en minúscula, de la misma forma que el nombre de las funciones. 
 + 
 +Vemos que al definir ''sgn'' en haskell hemos distinguido dos partes del cuerpo, mediante el símbolo "=". A la izquierda de "=" hemos escrito una condición y, si ésta se cumple, se calcula el resultado de la forma que se especifica a la derecha. Si no se cumple, se pasa al siguiente elemento de la disyunción. En prolog no disponemos de ese mecanismo, y por lo tanto nos hemos visto obligados a especificar esas dos partes de cada elemento de la disyunción con la misma categoría dentro de la proposición. Si derivamos la prueba de cada programa, vamos a ver que el resultado de ambos es el mismo, pero la función en haskell resulta mucho más natural y más fácil de leer. 
 + 
 +Vamos a ver que en haskell hay varias formas de expresar estas condiciones para que se cumpla una determinada forma de calcular un resultado, en el apartado sobre [[#comparacion_de_patrones|comparación de patrones]]. Ahora vamos a ver un poco más sobre tipos de datos en haskell. 
 + 
 + 
 +===== Tipos de datos===== 
 + 
 +Haskell es un lenguaje tipado, es decir, todo dato pertenece a una clase o tipo de datos. En general, la definición de una función va precedida de su //signatura de tipos//, donde declaramos los tipos que están involucrados en la función: 
 +<code> 
 +sgn :: Int -> Int     -- esta línea es la signatura de tipos de la función sgn 
 +sgn x   | 0<x   = 1 
 +        | x<0   = -1 
 +        | x==0  = 0
 </code> </code>
  
 La signatura de tipos está formada por el nombre de la función y el tipo de sus parámetros y resultado. El nombre va seguido de ''::'' y los parámetros y el resultado van separados por ''->''. Por ejemplo: La signatura de tipos está formada por el nombre de la función y el tipo de sus parámetros y resultado. El nombre va seguido de ''::'' y los parámetros y el resultado van separados por ''->''. Por ejemplo:
 <code> <code>
-  sgn :: Int -> Int +sgn :: Int -> Int 
-  reverse :: [a] -> [a] +reverse :: [a] -> [a] 
-  map :: (a -> b) -> [a] -> [b]+map :: (a -> b) -> [a] -> [b]
 </code> </code>
 Pequeño ejercicio sobre la aridad((Recuerden que la aridad es el número de argumentos de la función: unaria si tiene un argumento, binaria si tiene dos, etc.)) de las funciones: cuál de estas tres funciones es unaria, cuál binaria, cuál ternaria?  Pequeño ejercicio sobre la aridad((Recuerden que la aridad es el número de argumentos de la función: unaria si tiene un argumento, binaria si tiene dos, etc.)) de las funciones: cuál de estas tres funciones es unaria, cuál binaria, cuál ternaria? 
Línea 188: Línea 221:
 De esta forma, nos resulta imposible escribir cualquier expresión que esté mal tipada, es decir, usando tipos distintos a los que se declaran en la definición de la función. De hecho, corre el rumor de que, en una versión de desarrollo de un popular intérprete de haskell (GHC), si el intérprete encontraba un error de tipos, borraba todo el código fuente! :-}  De esta forma, nos resulta imposible escribir cualquier expresión que esté mal tipada, es decir, usando tipos distintos a los que se declaran en la definición de la función. De hecho, corre el rumor de que, en una versión de desarrollo de un popular intérprete de haskell (GHC), si el intérprete encontraba un error de tipos, borraba todo el código fuente! :-} 
  
-Veamos algunos de los tipos de datos que maneja haskell: diferentes tipos de números, tuplas y listas.+Los tipos de datos se declaran con la primera letra en mayúscula: Int, Float, Char, String, etc. En cambio, las variables se declaran en minúscula. 
  
-====Números====+Veamos algunos de los tipos de datos que maneja haskell: diferentes tipos de números, letras, tuplas y listas.
  
-Los patrones numéricos consisten en constantes y expresiones numéricas simples.+====Letras y números====
  
-====Variables, patrones irrefutables====+En haskell tenemos diferentes tipos de números. Los que más vamos a estar usando son los enteros, que se llaman ''Int'', pero también tenemos los decimales (''Float'').
  
-<code> +También tenemos el tipo ''Char'' que engloba caracteres, como 'a', 'b', etc. Los elementos que pertenecen a este tipo se usan entre comillas simples. El tipo ''String'' es una forma abreviada de escribir listas de caracteres. En lugar de escribir ''['h','o','l','a']'', el tipo ''String'' posibilita que podamos escribir ''"hola"'', lo cual queda mucho más legible :).
-esCeroOUno :: Int -> Bool +
-esCeroOUno 0 = True +
-esCeroOUno _ = False +
-esCeroOUno 1 = True +
-</code>+
  
-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: 
- 
-<code> 
-esCeroOUno :: Int -> Bool 
-esCeroOUno 0 = True 
-esCeroOUno 1 = True 
-esCeroOUno _ = False 
-</code> 
- 
-Podemos combinar de manera libre estas posibilidades como se muestra a continuación. 
- 
-<code> 
-sumaCabeza :: [(Int,Int)] -> Int 
-sumaCabeza [] = 0 
-sumaCabeza ((x,y):xs) = x+y 
-</code> 
- 
-<code> 
-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) 
-</code> 
- 
-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) 
  
 ====Tuplas==== ====Tuplas====
Línea 257: Línea 238:
 Veamos algunos ejemplos: Veamos algunos ejemplos:
 <code> <code>
-  suma3upla :: (Int,Int,Int) -> Int +suma3upla :: (Int,Int,Int) -> Int 
-  suma3upla (x,y,z) = x+y+z +suma3upla (x,y,z) = x+y+z 
-   +</code> 
-  sumaYResta :: Int -> Int -> (Int,Int) +<code>   
-  sumaYResta x y = (x+y, x-y)+sumaYResta :: Int -> Int -> (Int,Int) 
 +sumaYResta x y = (x+y, x-y)
 </code> </code>
  
Línea 287: Línea 269:
 esVacia (x:xs) = False esVacia (x:xs) = False
 </code> </code>
-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.+ 
 +Pero no sólo podemos distinguir el primer elemento de una lista, podemos distinguir //cualquier fracción inicial//. Cuando decimos que podemos distinguir cualquier fracción inicial de una lista, lo que queremos decir es que nos podemos referir al n-ésimo elemento de una lista, eso sí, para hacerlo tenemos que hacerlo con un patrón en el que se representen todos los elementos desde el primero hasta el n-1. Por ejemplo, si queremos referirnos al tercer elemento de una lista, tendremos que referirnos también al primero y al segundo, aunque sea mediante un patrón irrefutable, por ejemplo, de esta forma: 
 +<code> 
 +tercero [a] -> a 
 +tercero [_:_:x:_] = x 
 +</code> 
 + 
 +Sin embargo, podemos dejar el resto de la lista sin detallar cuántos elementos hay. No podemos distinguir fracciones finales de las listas porque la estructura de tuplas requiere que para distinguir el //n+1// elemento de una tupla hayamos distinguido el elemento //n//. 
 + 
 +Definimos un predicado que decide si //hay 2 o más elementos en una lista//: 
 +<code> 
 +alMenos2 :: [a] -> Bool 
 +alMenos2 []       = False 
 +alMenos2 [x]      = False 
 +alMenos2 (x:y:xs) = True 
 +</code> 
 + 
 +=====Comparación de patrones===== 
 + 
 +En haskell, como en prolog, las diferentes funciones se aplican por **unificación**. Es decir, cuando el intérprete trata de resolver algo, lo resuelve buscando alguna definición de función cuya parte izquierda pueda unificarse con lo que el intérprete está tratando de resolver.  
 + 
 +Cómo hace el intérprete para llegar desde nuestra pregunta al resultado? En el siguiente ejemplo: 
 +<code> 
 +Main> alMenos2 [1,2,3,4,5] 
 +True 
 +</code> 
 +El intérprete busca alguna definición de función que pueda unificar con ''alMenos2 [1,2,3,4,5]''. En primer lugar, encuentra un primer caso en el que se define ''alMenos2'': 
 +<code> 
 +alMenos2 []       = False 
 +</code> 
 +Pero este caso no le sirve porque no puede unificar la lista vacía ''[]'' con la lista no vacía ''[1,2,3,4,5]''. 
 + 
 +Después encuentra otro caso en el que se define ''alMenos2'', pero tampoco puede unificar una lista de un elemento con una lista de 5. 
 +<code> 
 +alMenos2 [x]      = False 
 +</code> 
 +Finalmente, encuentra un caso de una lista con dos o más elementos, con la que sí puede unificar: 
 +<code> 
 +alMenos2 (x:y:xs) = True 
 +</code> 
 +Vamos a prestar un poco más de atención al patrón que describe listas con uno o más elementos. En primer lugar vemos que se usan paréntesis. No es porque se trate de una tupla, sino para evitar errores de precedencia con el operador "'':''". Este operador es una función binaria que toma un elemento y una lista y nos indica que ese elemento está dentro de la lista, en su cabeza. Si hacemos el árbol de tipado de la expresión ''alMenos2 (x:y:xs)'', nos quedará de la siguiente forma: 
 +<code> 
 +alMenos2    ( x : y :  xs ) 
 +-----------  --- ---  ---- 
 +[a] -> Bool   a   a : [a] 
 +                 --------- 
 +                :   [a] 
 +             ------------- 
 +                 [a] 
 +-------------------------- 
 +       Bool 
 +</code> 
 +Notemos que hemos usado la variable ''xs'' para describir una lista con un número indeterminado de elementos. En este caso hemos usado ''xs'' que es un nombre de variable muy usado en haskell para listas, pero podríamos haber usado cualquier otra variable: ''cola'', ''resto'', ''lista'', ''a'' o lo que fuera. La variable representa una lista porque si no no podría tipar con el operador ":", que requiere que su segundo argumento sea una lista. En cualquier caso, esta lista puede ser una lista cualquiera, incluyendo la lista vacía. 
 + 
 +A la unificación también se la llama correspondencia de patrones o //pattern matching//, y a los elementos que unifican se los puede llamar patrones. Así, los diferentes casos que especificamos al definir por casos una función se pueden llamar también "patrones". 
 + 
 +====El patrón irrefutable==== 
 + 
 +Hemos visto que las variables se escriben con minúscula. Como en prolog, también tenemos una variable comodín, que puede unificar con cualquier cosa, y se escribe de la misma forma que en prolog, con el guión bajo "_".  
 + 
 +Veamos algunos ejemplos de uso del patrón irrefutable. Recuerden que habíamos visto la función ''esVacia'': 
 +<code> 
 +esVacia :: [a] -> Bool 
 +esVacia []     = True 
 +esVacia (x:xs) = False 
 +</code> 
 +Podemos usar comodines en ambas partes del segundo patrón o bien un patrón irrefutable y comodín a la vez.
 <code> <code>
 esVacia' :: [a] -> Bool esVacia' :: [a] -> Bool
Línea 298: Línea 346:
 </code> </code>
  
-Pero no sólo podemos distinguir el primer elemento de una lista, podemos distinguir //cualquier fracción inicial// No podemos distinguir fracciones finales de las listas porque la estructura de tuplas requiere que para distinguir el //n+1// elemento de una tupla hayamos distinguido el elemento //n//. +También se puede aplicar a la función ''alMenos2'', que definíamos originalmente así:
- +
-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. +
 <code> <code>
 alMenos2 :: [a] -> Bool alMenos2 :: [a] -> Bool
Línea 307: Línea 352:
 alMenos2 [x]      = False alMenos2 [x]      = False
 alMenos2 (x:y:xs) = True alMenos2 (x:y:xs) = True
 +</code> 
 +Esta segunda versión es bastante más difícil de leer que la primera, por el uso y abuso del orden de evaluación de los patrones, patrones irrefutables y comodines. Los patrones irrefutables son muy útiles, pero no debemos dejar que nos impidan entender lo que escribimos ;). 
 +<code>
 alMenos2' :: [a] -> Bool alMenos2' :: [a] -> Bool
 alMenos2' (_:_:_) = True alMenos2' (_:_:_) = True
Línea 313: Línea 360:
 </code> </code>
  
 +Veamos ahora un ejemplo de **mal** uso del patrón irrefutable:
  
-===== Ejemplo: la función bisiesto =====+<code> 
 +esCeroOUno :: Int -> Bool 
 +esCeroOUno 0 = True 
 +esCeroOUno _ = False 
 +esCeroOUno 1 = True 
 +</code> 
 + 
 +Si probamos 
 +<code> 
 +Main> esCeroOUno 1 
 +False 
 +</code> 
 + 
 +Por qué nos devuelve falso? Porque en haskell, como en prolog, los patrones se aplican en el **orden** en el que se encuentran en el archivo de la base de conocimiento: se evalúan de arriba a abajo y el primero que coincide se toma, y se finaliza la ejecución((En haskell no hay //backtracking// (vuelta atrás), como en prolog)). Como "_" unifica con cualquier cosa, entonces el intérprete encuentra un patrón que unifica con lo que está buscando, devuelve el resultado que hay a la derecha y finaliza la ejecución. 
 + 
 +El programa que hace lo que nosotros esperamos tiene esto en cuenta y ordena los patrones de forma que se aplique el patrón irrefutable sólo cuando todo el resto falla. 
 + 
 +<code> 
 +esCeroOUno :: Int -> Bool 
 +esCeroOUno 0 = True 
 +esCeroOUno 1 = True 
 +esCeroOUno _ = False 
 +</code> 
 + 
 + 
 +===== Un ejemplo: la función bisiesto =====
  
 A manera de ejemplo veamos el ejercicio 8.7 del apunte, donde tenemos que definir una función muy útil para cualquier aparato que maneje un calendario (relojes, celulares, PDAs, computadoras, DVD-R, etc.). A manera de ejemplo veamos el ejercicio 8.7 del apunte, donde tenemos que definir una función muy útil para cualquier aparato que maneje un calendario (relojes, celulares, PDAs, computadoras, DVD-R, etc.).
Línea 326: Línea 399:
 Una definición matemática concisa sería //bisiesto n = 4|n /\ (100|n => 400|n)//. Una definición matemática concisa sería //bisiesto n = 4|n /\ (100|n => 400|n)//.
  
-Entonces podemos seguir agregando definiciones de funciones a nuestro archivo ''cap8.hs'' con el comando '':e''. 
 Veamos tres versiones distintas ((Esto es una mala copia de [[http://www.willamette.edu/~fruehr/haskell/evolution.html|The Evolution of a Haskell Programmer]])). Veamos tres versiones distintas ((Esto es una mala copia de [[http://www.willamette.edu/~fruehr/haskell/evolution.html|The Evolution of a Haskell Programmer]])).
  
-**La del viejo programadora/or**+**La del programadora/or imperativo**
  
   bisiesto'' :: Int -> Bool   bisiesto'' :: Int -> Bool
Línea 343: Línea 415:
                   | n `mod` 4 == 0 = n `mod` 100 /= 0 || n `mod` 400 == 0                   | n `mod` 4 == 0 = n `mod` 100 /= 0 || n `mod` 400 == 0
  
-**El que cursó [[http://cs.famaf.unc.edu.ar/introalg/|Introducción a los Algoritmos]] ;-)**+**El que entiende mucho de programación declarativa ;-)**
  
   bisiesto :: Int -> Bool   bisiesto :: Int -> Bool
   bisiesto n = n `mod` 4 == 0 && (n `mod` 100 /= 0 || n `mod` 400 == 0)   bisiesto n = n `mod` 4 == 0 && (n `mod` 100 /= 0 || n `mod` 400 == 0)
  
- 
-=====Comparando haskell y prolog===== 
- 
-Ejemplo de la familia. 
  
 ===== Ejercicios ===== ===== Ejercicios =====
  
 +Hay muchos ejercicios para hacer, no se preocupen si no pueden terminarlos todos!! Vamos a ver algunos de ellos en la próxima clase para consolidar los conceptos que hemos visto en esta.
  
- +  * Definir una función //ordena (x,y)//, //ordena :: (Int,Int) -> (Int,Int)// que, dados dos enteros, los ordena de  menor a mayor.
-  * Definir la función //sumaRat (a,b) (c,d)//, //sumaRat : (Int,Int) -> (Int,Int) -> (Int,Int)// que suma dos números racionales. En esta función vamos a usar las tuplas para agrupar datos. En este caso, vamos a representar un número racional mediante una tupla, de forma que el numerador sea el primer elemento de la tupla, y el denominador sea el segundo. Por ejemplo, representamos ''3/4'' como ''(3,4)'', representamos ''5/2'' como ''(5,2)'', etc.  +
- +
- No es necesario realizar ninguna simplificación al resultado. +
- +
-  probar con (1,2) y (1,2), (1,4) y (1,4). +
- +
- +
-  * Definir una función //ordena.(x,y)//, //ordena : (Int,Int) -> (Int,Int)// que, dados dos enteros, los ordena de  menor a mayor.+
  
   probar con (0,1), (2,2), (3,1).   probar con (0,1), (2,2), (3,1).
  
-  * Definir una función //ambospositivos.x.y//, //ambospositivos : Int -> Int -> Bool//, que dados dos enteros devuelve //True// si los dos son positivos.+  * Definir una función //ambospositivos x y//, //ambospositivos :: Int -> Int -> Bool//, que dados dos enteros devuelve //True// si los dos son positivos.
  
   probar con 5 y 9, con -8 y 9, con -10 y -1, con 0 y 0 y con 0 y 3   probar con 5 y 9, con -8 y 9, con -10 y -1, con 0 y 0 y con 0 y 3
  
   * Ejercicio 8.7 del Apunte\\   * Ejercicio 8.7 del Apunte\\
-Definir la función //edad : (Int, Int, Int) -> (Int, Int, Int) -> Int// que dadas dos fechas indica los años transcurridos entre ellas. Por ejemplo edad.(20,10,1968).(30,4,1987) = 18.+Definir la función //edad :: (Int, Int, Int) -> (Int, Int, Int) -> Int// que dadas dos fechas indica los años transcurridos entre ellas. Por ejemplo edad (20,10,1968) (30,4,1987) = 18.
 Suponer que las fechas están siempre bien formadas y que la primera es menor o igual a la segunda. Suponer que las fechas están siempre bien formadas y que la primera es menor o igual a la segunda.
  
Línea 382: Línea 443:
 En un prisma rectangular, llamemos //h// a la altura, //b// al ancho y //d// a la profundidad. Completar En un prisma rectangular, llamemos //h// a la altura, //b// al ancho y //d// a la profundidad. Completar
 la siguiente definición del área del prisma: \\ la siguiente definición del área del prisma: \\
-//area.h.b.d = 2 ∗ frente + 2 ∗ lado + 2 ∗ arriba// \\+//area h b d = 2 ∗ frente + 2 ∗ lado + 2 ∗ arriba// \\
 //|[   ...aca va la definicion...   ]|// \\ //|[   ...aca va la definicion...   ]|// \\
 donde //frente//, //lado// y //arriba// son las caras frontal, lateral y superior del prisma respectivamente.\\ donde //frente//, //lado// y //arriba// son las caras frontal, lateral y superior del prisma respectivamente.\\
  
-Completar la función //area.h.b.d// //area : Int -> Int -> Int -> Int// que calcula el área de un prisma rectangular:+Completar la función //area h b d// //area :: Int -> Int -> Int -> Int// que calcula el área de un prisma rectangular:
  
       area :: Int -> Int -> Int -> Int          area :: Int -> Int -> Int -> Int   
-      area.h.b.d = 2*frente + 2*lado + 2*tapa+      area h b d = 2*frente + 2*lado + 2*tapa
            where            where
               frente = ...               frente = ...
               lado   = ...               lado   = ...
               tapa   = ...               tapa   = ...
 +
 +  * Programar en haskell una [[http://www.cs.famaf.unc.edu.ar/wiki/doku.php?id=introalg:taller09_soluciones#familia|solución al problema de la familia]] que vimos en prolog.
 +
 +  * 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.
introalg/taller09_3.1239493270.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)