Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza:
introalg:taller08_1

Diferencias

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

Enlace a la vista de comparación

Próxima revisión		Revisión previa
introalg:taller08_1 [2008/03/18 21:11] – creado lauraintroalg:taller08_1 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 1: Línea 1:
-====== Taller de Programación Funcional ====== +====== Clase 1 ======
-====== Introducción a los Algoritmos 2008 ======+
  
  
  
 +===== Introducción al uso de Hugs=====
  
 +[[http://haskell.org/hugs/|Hugs]] es un intérprete del lenguaje funcional puro [[http://haskell.org/|Haskell]].
  
 +Durante este taller escribiremos, probaremos y utilizaremos programas funcionales.
  
-===== Clases =====+A Hugs se lo invoca desde la //línea de comandos// o picando 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**.
  
-|Abr 8-10 | [[IntroAlg:taller08_1|Clase 1]] | Introducción, manejo de Hugs, ciclo de edición, inferencia de tipos, tuplas, análisis por casos | +  [laura@azul Taller]$ hugs 
-|Abr 15-17 | [[IntroAlg:taller08_2|Clase 2]] | Pattern matching numérico, tuplas y listas, divide y conquista, estilo de código |  +  __   __ __  __  ____   ___      _________________________________________ 
-|Abr 22-24 | [[IntroAlg:taller08_3|Clase 3]] | Recursión lineal, aplicaciones, filtros, acumuladores |  +  ||   || ||  || ||  || ||__      Hugs 98: Based on the Haskell 98 standard 
-|May 29-1   |                                 | Día del Trabajador, 29 Abr refuerzo generalizaciones (todas las comisiones) | +  ||___|| ||__|| ||__||  __||     Copyright (c) 1994-2005 
-|May 6-8  | **Parcialito 1**       | Predicados y funciones simples, tuplas, composición, análisis por caso, recursión lineal | +  ||---||         ___||           World Wide Web: http://haskell.org/hugs 
-|May 13-15 | [[IntroAlg:taller08_4|Clase 4]] | Aplicación parcial (secciones), generalización de las funciones vistas (map, filter, fold, etc.), alto orden | +  ||   ||                         Report bugs to: hugs-bugs@haskell.org 
-|May 20-22 |                                 | Semana de Mayo,  refuerzo generalizaciones y práctica de programas (todas las comisiones) | +  ||   || Version: March 2005     _________________________________________ 
-|May 27-29 | [[IntroAlg:taller08_5|Clase 5]] | Recursión doble, más funciones politípicas, análisis de rendimiento | +   
-|Jun 3-5   [[IntroAlg:taller08_6|Clase 6]] | Práctica de programas | +  Haskell 98 mode: Restart with command line option -98 to enable extensions 
-|Jun 10-12   | **Parcialito 2**       | Funciones recursivas | +   
-|Jun 17 | [[IntroAlg:taller08_7|La Guinda]] | la guinda del taller |+  Type :? for help 
 +  Hugs.Base>
  
-===== Problemas =====+De este modo Hugs se convierte en una calculadora, esperando que se introduzca una expresión para evaluarla e imprimir el resultado (lazo **leer-evaluar-imprimir**). Después, nuestra calculadora Hugs queda lista para volver a pedir una expresión. 
  
-  * [[introalg:problemas08|Problemario del taller]], con todos los problemas que vas a resolver en el taller de Haskell.+Gracias al [[http://www.haskell.org/onlinereport/standard-prelude.html | preludio estándar]] tenemos muchas funciones ya definidas, entre ellas, todas las aritméticas y las lógicas básicas. Pero también tenemos otras muchas, como por ejemplo "reverse".
  
-  * [[introalg:rincon08|Wiki de Scripts Haskell]], aca podés dejar código [[http://es.wikipedia.org/wiki/Haskell | Haskell]] de manera libre.+  Hugs.Base> 21+21 
 +  42 
 +  Hugs.Base> True && False 
 +  False 
 +  Hugs.Base> 2*4 == 10 `div` 5 && True 
 +  False 
 +  Hugs.Base> [2,3,5,7,11]++[1,2] 
 +  [2,3,5,7,11,1,2] 
 +  Hugs.Base> reverse "dabale arroz a la zorra el abad" 
 +  "daba le arroz al a zorra elabad"
  
-===== Programas =====+Podemos salir del intérprete Hugs con ''CTRL-D'' o con el comando ":q".
  
-Para los usuarios de Windows y [[http://es.wikipedia.org/wiki/Unix|*nix]], hay versiones para bajar desde [[http://cvs.haskell.org/Hugs/pages/downloading.htm|Downloading Hugs]]. \\ +  Hugs.Base> :q 
-Las principales distribuciones Linux (Debian, Ubuntu, Fedora y Gentoo) incluyen Hugs como un paquete de instalación. \\ +  [Leaving Hugs] 
-En Windows tenemos [[http://cvs.haskell.org/Hugs/downloads/2006-09/MinHugs-Sep2006.exe|MinHugs]] una versión pequeña de solo 1.4MiB de descarga.+  [laura@azul Taller]$
  
-===== Bibliografía =====+Así volvemos al modo normal de la computadora.
  
-  * José Gallardo, Paco Gutiérrez y Blas Ruiz, [[http://www.lcc.uma.es/~pepeg/pfHaskell/gentle | "Una introducción agradable a Haskell versión 98"]], Febrero de 2001. + 
-    * Traducción de [[http://haskell.org/tutorial | "A gentle introduction to Haskell Version 98"]]. +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 funcional// o //script// Haskell. 
-  * Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo, [[http://www.lcc.uma.es/~pepeg/pfHaskell/index.html | "Razonando con Haskell"]], Thompson, 2004. + 
-  * Jose E. Labra G., [[http://horru.lsi.uniovi.es/~labra/FTP/IntHaskell98.pdf|Introducción al lenguaje Haskell]], Universidad de Oviedo, Departamento de Informática, Octubre 1998. +Un programa funcional es un [[http://es.wikipedia.org/wiki/Archivo_inform%C3%A1tico|archivo]] con terminación **''.hs''** donde se escriben en //texto plano// todas las definiciones que conforman el programa funcional. 
-  * Simon Thompson, [[http://www.cs.kent.ac.uk/people/staff/sjt/craft2e/|Haskell The Craft of Functional Programming]], 2da edición, Addison-Wesley, 1999. + 
-  * Mucho material en inglés de [[http://haskell.org/haskellwiki/Books_and_tutorials#Introductions_to_Haskell|Introductions to Haskell]].+Como ejemplo, vamos a ver todo el proceso de **creación-carga-prueba-modificación-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. 
 + 
 +Para crear un //script// basta con invocar el comando para editar un (nuevo) archivo '':e cap8.hs''. También se puede crear el script mediante un editor de texto cualquiera (//emacs//, //bloc de notas//, //kate//, //vi//,...). 
 + 
 +  Hugs.Base> :e cap8.hs 
 + 
 +Una posible solución para el problema de la función signo es la siguiente: 
 + 
 +  sgn :: Int -> Int 
 +  sgn x   | 0<x   = 1 
 +          | x<0   = -1 
 +          | x=0   = 0 
 + 
 + 
 +Luego de guardar el programa, hay cargarlo para que el intérprete Hugs pueda empezar a usar la nueva función que hemos creado. 
 + 
 +  Hugs.Base> :l cap8.hs 
 +  ERROR "cap8.hs":4 - Syntax error in input (unexpected `=') 
 + 
 +Pero el intérprete indica un error! Por qué? Porque "=" es el símbolo de definición, mientras que la comparación es "==". 
 + 
 +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''. 
 + 
 +  sgn :: Int -> Int 
 +  sgn x   | 0<x   = 1 
 +          | x<0   = -1 
 +          | x==0  = 0 
 + 
 + 
 +Luego de guardar el programa, hay que **volver a cargarlo** para que el intérprete pueda usar la función corregida, si no lo cargamos, el intérprete se queda en el estado anterior, en el que no tenía la función porque ésta tenía un error. 
 + 
 +  Hugs.Base> :l cap8.hs 
 +  Main> 
 + 
 +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// para ganar confianza en su **corrección**. 
 + 
 +  Main> sgn 1 
 +  1 
 +  Main> sgn 0 
 +  0 
 +  Main> sgn -1 
 +  ERROR - Cannot infer instance 
 +  *** Instance   : Num (Int -> Int) 
 +  *** Expression : sgn - 1 
 +   
 +  Main> sgn (-1) 
 +  -1 
 +  Main> sgn 123123123123 
 +   
 +  Program error: arithmetic overflow 
 +   
 +  Main> sgn 123123123 
 +  1 
 +  Main> sgn 1.1 
 +  ERROR - Cannot infer instance 
 +  *** Instance   : Fractional Int 
 +  *** Expression : sgn 1.1 
 +   
 +  Main> sgn (-1 
 +  ERROR - Syntax error in expression (unexpected end of input) 
 +   
 +  Main> sgn "hola" 
 +  ERROR - Type error in application 
 +  *** Expression     : sgn "hola" 
 +  *** Term           : "hola" 
 +  *** Type           : String 
 +  *** Does not match : Int 
 +   
 +  Main> map sgn [-10..10] 
 +  [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,1,1,1,1,1,1,1,1,1,1] 
 + 
 + 
 +Notamos los distintos tipos de errores que se producen por problemas de 
 +  * Precedencia (''sgn -1'') 
 +  * Tipos (''sgn 1.1'') 
 +  * Sintaxis (''sgn (-1'') 
 + 
 + 
 +===== Inferencia de tipos ===== 
 + 
 +Haskell es un lenguaje tipado, es decir, todos los datos pertenecen a una clase o tipo de datos. Hugs tiene una maquinaria para //inferir// tipos, tanto los declarados 
 + 
 +  Main> :t sgn 
 +  sgn :: Int -> Int 
 + 
 +Como expresiones en general 
 + 
 +  Main> :t 1 + 2.1 
 +  1 + 2.1 :: Fractional a => a 
 +   
 +  Main> :t 1+ sqrt 64 
 +  1 + sqrt 64 :: Floating a => a 
 +   
 +  Main> :t 1+ "a" 
 +  ERROR - Cannot infer instance 
 +  *** Instance   : Num [Char] 
 +  *** Expression : 1 + "a" 
 +   
 +  Main> :t "hola" ++ "que" ++ "tal" 
 +  "hola" ++ "que" ++ "tal" :: [Char] 
 +   
 +  Main> :t reverse 
 +  reverse :: [a] -> [a] 
 +   
 +  Main> :t map 
 +  map :: (a -> b) -> [a] -> [b] 
 + 
 + 
 +Esta maquinaria **impide** que escribamos cualquier expresión que esté mal tipada.   
 + 
 +Todas las funciones suelen ir encabezadas por su signatura, es decir, el nombre de la función junto al tipo de sus parámetros y resultado. El nombre va seguido de ''::'' y los parámetros y el resultado van separados por ''->''. Por ejemplo: 
 + 
 +  sgn :: Int -> Int 
 +  reverse :: [a] -> [a] 
 +  map :: (a -> b) -> [a] -> [b] 
 + 
 + 
 +===== Tuplas ===== 
 + 
 +Haskell maneja n-uplas de manera directa. Las n-uplas nos permiten agrupar datos para manejarlos como una sola cosa, como veremos más adelante. 
 + 
 +Incorporamos a ''cap8.hs'' las siguientes definiciones: 
 + 
 +  suma3upla :: (Int,Int,Int) -> Int 
 +  suma3upla (x,y,z) = x+y+z 
 +   
 +  sumaYResta :: Int -> Int -> (Int,Int) 
 +  sumaYResta x y = (x+y, x-y) 
 + 
 +Y las probamos desde el //prompt//. 
 + 
 +  Main> suma3upla (2,3,4) 
 +  9 
 +  Main> sumaYResta 2 3 
 +  (5,-1) 
 + 
 +Haskell también maneja listas de manera directa, pero lo veremos más adelante. 
 + 
 + 
 +===== 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.). 
 +La signatura es //bisiesto: Int -> Bool//, y es un predicado que devuelve //true// si el año es bisiesto y //false// en caso contrario. 
 +Recordemos cuando un año es [[http://es.wikipedia.org/wiki/Bisiesto|bisiesto]]: 
 + 
 +  La regla para los años bisiestos según el calendario gregoriano es: 
 +  Un año es bisiesto si es divisible por 4, excepto los principios de siglo (aquellos divisibles por 100), 
 +  que para ser bisiestos, también deben ser divisibles por 400.  
 + 
 +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]])). 
 + 
 +**La del viejo programadora/or** 
 + 
 +  bisiesto'' :: Int -> Bool 
 +  bisiesto'' n = if  n `mod` 4 /= 0 then False 
 +                  else if n `mod` 100 /= 0 then True 
 +                          else if n `mod` 400 == 0 then True 
 +                                  else False 
 + 
 +**El que está aprendiendo Haskell** 
 + 
 +  bisiesto' :: Int -> Bool 
 +  bisiesto' n     | n `mod` 4 /= 0 = False 
 +                  | 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]] ;-)** 
 + 
 +  bisiesto :: Int -> Bool 
 +  bisiesto n = n `mod` 4 == 0 && (n `mod` 100 /= 0 || n `mod` 400 == 0) 
 + 
 +Podemos poner las tres versiones en nuestro script y probarlas rápidamente usando la función ''filter'' para que obtener solo los años bisiestos desde 1945 al 2006. 
 + 
 +  Main> filter bisiesto [1945..2006] 
 +  [1948,1952,1956,1960,1964,1968,1972,1976,1980,1984,1988,1992,1996,2000,2004] 
 +  Main> filter bisiesto' [1945..2006] 
 +  [1948,1952,1956,1960,1964,1968,1972,1976,1980,1984,1988,1992,1996,2000,2004] 
 +  Main> filter bisiesto'' [1945..2006] 
 +  [1948,1952,1956,1960,1964,1968,1972,1976,1980,1984,1988,1992,1996,2000,2004] 
 + 
 +Vemos que las tres funciones operan correctamente en el rango de números dados ((No queremos decir que sean correctas en su totalidad, solo decimos que en ese rango no tienen fallas)). 
 + 
 + 
 + 
 + 
 + 
 + 
 + 
 +===== Ejercicios ===== 
 + 
 +Para realizar en lo que resta de la clase. 
 + 
 +  * 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). 
 + 
 +  * 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 
 + 
 +  * 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. 
 +Suponer que las fechas están siempre bien formadas y que la primera es menor o igual a la segunda. 
 + 
 +  probar con (16,4,1980) y (17,5,1992), (16,4,1980) y (14,5,1992), (16,4,1980) y (15,4,1992) y con (16,4,1980) y (17,5,1972). 
 + 
 + 
 +  * Ejercicio 8.8 del Apunte.\\ 
 +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: \\ 
 +//area.h.b.d = 2 ∗ frente + 2 ∗ lado + 2 ∗ arriba// \\ 
 +//|[   ...aca va la definicion...   ]|// \\ 
 +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: 
 + 
 +      area :: Int -> Int -> Int -> Int    
 +      area.h.b.d = 2*frente + 2*lado + 2*tapa 
 +           where 
 +              frente = ... 
 +              lado   = ... 
 +              tapa   = ...
introalg/taller08_1.1205874704.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)