¡Esta es una revisión vieja del documento!
Tabla de Contenidos
Introducción a la Programación Funcional
Después de iniciarnos en la programación lógica en prolog, vamos a empezar con la programación funcional en haskell.
Iniciando haskell
Al igual que con prolog, vamos a estar usando un intérprete de haskell. Un intérprete de haskell es un programa que entiende haskell, por lo tanto, puede entender y ejecutar los programas que vamos a hacer en haskell. El intérprete que vamos a estar usando es Hugs.
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.
[laura@azul Taller]$ hugs __ __ __ __ ____ ___ _________________________________________ || || || || || || ||__ Hugs 98: Based on the Haskell 98 standard ||___|| ||__|| ||__|| __|| Copyright (c) 1994-2005 ||---|| ___|| World Wide Web: http://haskell.org/hugs || || Report bugs to: hugs-bugs@haskell.org || || Version: March 2005 _________________________________________ Haskell 98 mode: Restart with command line option -98 to enable extensions Type :? for help Hugs.Base>
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 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”:
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"
Podemos salir del intérprete Hugs con CTRL-D o con el comando “:q”.
Hugs.Base> :q [Leaving Hugs] [laura@azul Taller]$
Así volvemos al modo normal de la computadora.
Incorporando conocimiento
Para poder dar nuevas definiciones y/o funciones, además de las que se encuentran en el 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 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 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:
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
Escribimos esta función en el archivo, lo guardamos, y lo cargamos en la memoria del intérprete para que esté disponible para usarla. Para cargar el archivo, usamos la instrucción :l:
Hugs.Base> :l cap8.hs ERROR "cap8.hs":4 - Syntax error in input (unexpected `=')
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: para definir (parecido a como usábamos “:-” en prolog) y para comparar, 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 Traducción de "Cálculo de Programas" a Haskell.
Para solucionar el error, 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, y vamos a fijarnos en qué casos nos dá errores y por qué:
Main> sgn 1 1 Main> sgn 0 0
Ningún problema: funciona para los casos del manual :).
Main> sgn 123123123123 Program error: arithmetic overflow Main> sgn 123123123 1
El número es demasiado grande y el intérprete se queda sin capacidad para tratarlo.
Main> sgn (-1 ERROR - Syntax error in expression (unexpected end of input)
Error de sintaxis: no cerramos el paréntesis!
Main> sgn "hola" ERROR - Type error in application *** Expression : sgn "hola" *** Term : "hola" *** Type : String *** Does not match : Int
Error de tipos: la función está definida para trabajar con enteros (Int), no con el tipo cadena de caracteres (String).
Main> sgn 1.1 ERROR - Cannot infer instance *** Instance : Fractional Int *** Expression : sgn 1.1
Error de tipos: la función está definida para trabajar con enteros (Int), no con el tipo decimal (Fractional).
Main> sgn -1 ERROR - Cannot infer instance *** Instance : Num (Int -> Int) *** Expression : sgn - 1 Main> sgn (-1) -1
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.
Cómo declaramos el conocimiento en haskell?
La declaración del conocimiento en haskell tiene algunos parecidos y algunas diferencias con la declaración del conocimiento en prolog.
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.
sgn :: Int -> Int
sgn x | 0<x = 1
| x<0 = -1
| x==0 = 0
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.
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. Si escribiéramos la función sgn en prolog, la escribiríamos así:
sgn(X,Y) :- (0<X , Y=1) ; (X<0 , Y=(-1)) ; (X=0, Y=0).
y la consultaríamos de la siguiente manera:
?- sgn(33,Y). Y = 1 .
Vemos que en haskell distinguimos dos partes mediante el símbolo “=”: a la izquierda escribimos una condición y, si ésta se cumple, se calcula el resultado de la forma que se especifica a la derecha. En prolog especificamos esas dos partes con la misma categoría dentro de la misma proposición, usando una variable (Y) para guardar el resultado en ella. Pero vemos que en ambos casos se calcula lo mismo y se escriben las cosas de forma bastante parecida.
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.
Tipos de datos, comparación de patrones
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:
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
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:
sgn :: Int -> Int reverse :: [a] -> [a] map :: (a -> b) -> [a] -> [b]
Pequeño ejercicio sobre la aridad1) de las funciones: cuál de estas tres funciones es unaria, cuál binaria, cuál ternaria?
Pero incluso si no hiciéramos la declaración de tipos mediante la signatura (lo cual sería muy mala práctica!), Hugs tiene una maquinaria para inferir el tipo de los datos de cualquier función. Podemos consultarlos mediante la instrucción :t:
Main> :t sgn sgn :: Int -> Int
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]
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.
Números
Los patrones numéricos consisten en constantes y expresiones numéricas simples.
Variables, patrones irrefutables
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
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)
Tuplas
Las n-uplas son conjuntos con un número y orden de elementos predefinido. Se escriben entre paréntesis y se separan los elementos mediante comas. Los más conocidos son las tuplas, conjuntos de dos elementos, pero también hay triplas, cuatruplas, etc. La utilidad de las n-uplas es que nos permiten agrupar datos para manejarlos como una sola cosa.
Veamos algunos ejemplos:
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 los probamos desde el prompt.
Main> suma3upla (2,3,4) 9 Main> sumaYResta 2 3 (5,-1)
Las tuplas pueden contener cualquier elemento de cualquier tipo, y se pueden mezclar tipos dentro de una misma tupla. Por ejemplo, podemos tener que el primer elemento de una tupla sea una cadena de caracteres y el segundo un número, el primero, una lista, el segundo elemento un booleano y el tercero otra lista, y así todas las combinaciones que se les ocurran.
Listas
Las listas son conjuntos de elementos ordenados, pero, a diferencia de las tuplas, tienen un número indeterminado de elementos, posiblemente ninguno. También a diferencia de las tuplas, los elementos de una lista tienen que ser todos del mismo tipo. Por ejemplo, si tenemos que el primer elemento de una lista es un entero, entonces todos tienen que ser enteros. Podemos tener listas de cualquier tipo de datos: listas de números, de tuplas, de triplas, listas de listas, listas de listas de listas…
Las listas se escriben entre corchetes y se separan los elementos mediante comas. Pero esta forma de representar las listas es una forma abreviada de escribir lo que haskell interpreta internamente como una anidación de tuplas de profundidad indeterminada. De hecho [1,2,3] = (1,(2,(3,[]))).
Dado que las listas son en realidad anidaciones de tuplas, podemos trabajar con su estructura como tuplas, y separar la parte inicial de la lista del resto, lo que se suele llamar cabeza y cola. Por ejemplo, en la siguiente función:
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
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.
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
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 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 2).
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ó Introducción a los Algoritmos 
bisiesto :: Int -> Bool bisiesto n = n `mod` 4 == 0 && (n `mod` 100 /= 0 || n `mod` 400 == 0)
Comparando haskell y prolog
Ejemplo de la familia.
Ejercicios
- 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/4como(3,4), representamos5/2como(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 = ...