Introducción A HASKELL
Introducción A HASKELL
Introducción A HASKELL
Haskell es un lenguaje de programación con tipos polimórficos, con evaluación perezoso (lazy), y
El lenguaje toma el nombre de Haskell BrooksCurry (1900-1982 Millis, Massachusetts, USA), cuyos
Haskell está basado en el cálculo lambda, de aquí el símbolo (lambda) que aparece en el logo.
VOLVER
En un lenguaje funcional se pueden definir funciones las cuales se usan en una expresión y cuyo valor tiene
que ser calculado. Para calcular el valor de una expresión se necesita un programa que entienda las definicio-
nes de las funciones. Tal programa se llama intérprete.
Tal intérprete analiza primero las funciones estándar, cuyas definiciones están en el fichero prelude
(preludio), que se examina antes de definir nuevas funciones. Finalmente, el intérprete comunica que
se puede teclear.
Type :? for help
Prelude>
El signo de interrogación indica que el interprete esta listo para calcular el valor de una expresión.
En el prelude están definidas, entre otras, las funciones aritméticas. Se puede usar el interprete como
calculadora.
Prelude> 5+2*3
11
(5 reductions, 9 cells)
Prelude>
El interprete:
Calcula el valor de la expresión: 11 que resulta de 5 + ( 2 x 3 ) = 5 + 6
Indica que para el calculo usó: 5 reductions: Medida para el tiempo utilizado
NOMBRES DE FUNCIONES Y PARÁMETROS: Empiezan con minúscula luego pueden seguir con
minúsculas, mayúsculas, ó números, y los símbolos ’ _. Ej:
Case, class, data, else, if, in, infix, infixl, infixr, instance, let, of, primitive, then, type, where
OPERADORES:
Operadores permitidos:
+ ++ && || <= == /= . //
fromInteger Convierte entero a numero real
OPERADORES BOOLEANOS:
== Igual a
/= Distinto de.
Ejemplos:
Prelude>1<2
True
Prelude> 2<1
False
take: Tiene dos parámetros: un numero y una lista. Si el numero es n, el resultado es una lista con
los primeros n elementos de la lista.
VOLVER
Sigue el modelo de una calculadora donde se establece una sesión interactiva entre el
ordenador y el usuario.
El sistema muestra un prompt Prelude> y espera a que el usuario introduzca una expresión inicial y
Cuando la entrada se ha completado, el sistema evalúa la expresión e imprime su valor antes de volver
El valor 40 puede generarse introduciendo en prelude (2+3)*8
Prelude>(2+3)*8
40
La lista de enteros desde 1 hasta 10, y sum es una función estándar que devuelve la suma de una lista de enteros: 1 +
2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55
Prelude> sum[1..10]
55
El usuario puede definir sus propias funciones y guardarlas para que el sistema pueda utilizarlas en
la evaluación, que consiste en tomar una expresión e ir transformándola aplicando las definiciones de
funciones, hasta que no pueda transformarse más. La expresión resultante se denomina representación
canónica y es mostrada al usuario. Ejemplos
Llamada por valor: Se evalúa los argumentos antes de llamar a la función, y se asocia
con la evaluación ansiosa.
cuadrado (3+4)
= { evaluando la suma }
cuadrado 7
= { utilizando la definición
cuadrado x = x * x }
7*7
= { evaluando la multiplicación }
49
Llamada por nombre: Se utiliza la definición de la función antes de evaluar los argumentos
y está asociado a la evaluación perezosa.
cuadrado (3+4)
= { utilizando la definición
cuadrado x = x * x }
(3+4) * (3+4)
= { evaluando la parte izquierda
de la multiplicación }
7 * (3+4)
= { evaluando la parte derecha
de la multiplicación }
7*7
= { evaluando la multiplicación }
49
Los valores son entidades abstractas que podemos considerar como la respuesta a un calculo
5 -1 8
Cada valor tiene asociado un tipo (< valor > :: < tipo >)
(2*3)+(4-5)
La reducción o evaluación de una expresión consiste en aplicar una serie de reglas que
(2*3)+(4-5)
Un valor es una expresión irreducible
Toda expresión tiene un tipo: el tipo del valor que resulta de reducir la expresión (Sistema
Fuertemente Tipado).
(2*3)+(4-5) :: Int
El tipo de una expresión debe establecerse en tiempo de compilación sin evaluar la expresión
(Tipado Estático)
El compilador calcula el tipo de una expresión, normalmente, sin ninguna anotación del
Tipos Basicos
Int: subconjunto de los enteros (normalmente, los enteros representables por una palabra del
procesador): 2, -1...
VOLVER
Tipos Básicos
El sistema de tipos es utilizado para detectar errores en expresiones y definiciones de función, para ello,
cada tipo tiene asociadas un conjunto de operaciones que no tienen significado para otros tipos, por ejemplo,
se puede aplicar la función (+) entre enteros pero no entre caracteres o funciones.
Como Haskell permite asociar un único tipo a toda expresión bien formada, es un lenguaje fuertemente
tipado; así, cualquier expresión que no pueda asociarse a un tipo será rechazada como incorrecta
antes de la evaluación.
El análisis tiene dos fases:
Análisis de tipo: Verifica que todas las expresiones tienen un tipo correcto
INFORMACIÓN DE TIPO
Además de las definiciones de función, se puede incluir información de tipo mediante una expresión de
la forma
VOLVER
Incluyen los enteros positivos y negativos tales como el -273, el 0 ó el 383. El rango de los
(+) suma,
(*) multiplicación,
(-) substracción,
FLOTANTES Float [Float]
Representan fraccionarios así como cantidades muy largas o muy pequeñas. Un valor numérico
También se puede utilizar notación científica; por ejemplo 1.0e3 equivale a 1000.0, mientras que 5.0e-2
equivale a 0.05.
El standar prelude incluye también múltiples funciones de manipulación de flotantes: pi, exp, log, sqrt,
Representan caracteres individuales por ejemplo: 'a', '0', '.' y 'Z'. Algunos caracteres especiales
deben ser introducidos utilizando un código de escape; cada uno de éstos comienza con el
caracter de barra invertida (\) , seguido de uno o más caracteres que seleccionan el caracter
requerido. Ejemplo
VOLVER
Sus valores se construyen utilizando otros tipos, por ejemplo: funciones, listas y tuplas.
FUNCIONES
Si a y b son dos tipos, entonces a->b es el tipo de una función que toma como argumento un
(+) Función de un argumento de tipo Int que devuelve una función de tipo Int->Int.
VOLVER
Además de las funciones que ya están en el preludio, podemos definir nuevas funciones, con el siguiente pro-
cedimiento:
Además de las funciones que ya están en el preludio, podemos definir nuevas funciones, con el siguiente pro-
cedimiento:
1. En Haskell, usamos el comando ‘:edit’, seguido por el nombre
2. de un fichero: Prelude> :edit nuevo; se activa el editor de
3. texto que ocupa temporalmente el lugarde Haskell y en el
4. escribimos la definición de la nueva función.
5. Por ejemplo
6. factorialDe ::Integer->Integer
7. factorialDe n=product[1..n]
8. Guardamos como: funcionFactorial.hs y luego cerramos
9. el editor
10.
15.
:load fichero(s) Permite conocer las funciones que están definidas en los ficheros especificados.
:also fichero(s) permite añadir definiciones de otros ficheros, sin eliminar las definiciones existentes.
:edit fichero Crear o modificar un fichero. Sin nombre, edit usa el ultimo fichero recuperado y,
:set ±letra Permite aplicar o eliminar algunas opciones. Activa y desactiva número de reducciones y
VOLVER
LISTAS
Si a es un tipo cualquiera, entonces [a] representa el tipo de listas cuyos elementos son valores de
tipo a. Así, todos los elementos de una lista deben ser del mismo tipo.
Las listas no vacías pueden ser construidas
Prelude>length [1,3,10]
3
VOLVER
CADENAS
Las cadenas son tratadas como listas de caracteres y el tipo String se toma como una abreviación de
"[Char]". Pueden ser escritas como secuencias de caracteres encerradas entre comillas dobles.
Todos los códigos de escape utilizados para los caracteres, pueden utilizarse para las cadenas.
Ej.
Prelude>"hola"
hola
Puesto que las cadenas son representadas como listas de caracteres, todas las funciones del estándar
prelude para listas pueden ser utilizadas también con cadenas:
Ej.
Prelude> length "Hola"
4
VOLVER
TUPLAS
A diferencia de las listas cuyos elementos deben ser del mismo tipo, las tuplas pueden agrupar
elementos de diferentes tipos, pero su tamaño es fijo. Así, un registro de personas puede contener
nombres (cadenas), si alguien es masculino o no (booleano) y fechas de nacimiento (enteros).
En las tuplas, el orden de los elementos es importante y para cada combinación de tipos se crea un
nuevo tipo. Así, si: t1, t2, ..., tn son tipos y <B=2, entonces hay un tipo de n-tuplas escrito: (t1, t2, ..., tn)
cuyos elementos pueden ser escritos también como (x1, x2, ..., xn) donde cada x1, x2,..., xn tiene
tipos t1,t2, ..., tn respectivamente.
Ejemplos:
o (1, ’{a}’) :: (Int, Char): Tupla con los elementos 1 (entero) y ’a’ (caracter)
o ("mono", True, 2) :: ([Char], Bool, Int) Tupla con tres elementos: la cadena "mono", el
o ([1,2], sqrt) :: ([Int], Float->Float) Tupla con dos elementos: la lista de enteros [1,2]
o
o Existe una tupla especial con 0 elementos denominada tipo unidad y se escribe como ().
Ejemplos para definir funciones sobre tuplas: mediante análisis por patrones.
Estas funciones son polimorficas, pero por supuesto también es posible escribir funciones que
operen solamente con un tipo de tupla determinado:
Para agrupar dos elementos del mismo tipo, se puede usar una lista. Pero, en algunos casos, una
tupla es más útil. Un punto en dos dimensiones se describe por dos números de tipo Float.
Tal punto puede ser descrito por una lista o por una pareja. En los dos casos es posible definir
funciones que hagan algo con puntos. Por ejemplo, una función que calcule la distancia hasta el
origen. La función distanciaL es la versión que usa una lista, distanciaT es la versión para una tupla:
Mientras se llame la función correctamente, no existe diferencia. Sin embargo, podría suceder que
se llamase a la función (por error al teclear, o error lógico) en algún lugar en el programa con tres
coordenadas.
Con el uso de distanciaT, el intérprete da un aviso durante el análisis de las funciones: una tupla con
tres elementos es diferente de una tupla con dos elementos. En el caso de distanciaL el intérprete no
dice nada: el programa no tiene conflictos de tipos.
Pero cuando se usa el programa, resulta que la función distanciaL no esta definida para listas con
tres elementos. El uso de tuplas en vez de listas es entonces útil para detectar errores lo antes
posible.
Otro caso en que las tuplas son realmente útiles es cuando se necesitan funciones con más de un
resultado. Las funciones de varios parámetros son posibles gracias al mecanismo de currificacion;
las funciones que tienen varios resultados solamente son posibles agrupando los resultados en una
tupla. La tupla en total es entonces un resultado.
Un ejemplo de una función que en realidad tiene dos resultados, es la función splitAt que esta
definida en el preludio. Esta función devuelve los resultados de take y drop de una vez.
Por tanto, se puede definir la función de la siguiente forma:
El trabajo de estas dos funciones se puede hacer de una vez, por eso se ha definido realmente la
función splitAt de forma mas eficiente:
VOLVER
DEFINICIONES DE TIPOS
Cuando se usan mucho las listas y tuplas, las declaraciones de tipos llegan a ser bastante
complicadas. Por ejemplo, con las funciones sobre puntos como la función distancia . Las funciones
mas simples son entendibles:
Sin embargo, es mías complicado con listas sobre puntos, y con funciones de orden superior:
Una definición de tipo es muy útil en estos casos. Con una definición de tipo es posible dar un
nombre (mías claro) a un tipo, por ejemplo:
Con esta definición se pueden escribir las declaraciones de tipo de forma más clara:
La palabra type es una palabra reservada especialmente para estas definiciones de tipo;
El nombre de un tipo debe empezar por una letra mayúscula (es una constante, no es una variable);
Una declaración de un tipo especifica el tipo de una función; una definición de tipo define un nuevo
nombre para un tipo. El intérprete usa el nombre definido simplemente como una abreviatura. Si se
pide el tipo de una expresión al intérprete, este muestra (Float,Float) en vez de Punto.
Entonces se pueden usar los dos nombres indistintamente. Un Punto es lo mismo que un Complejo
y este es lo mismo que un (Float,Float)
VOLVER
UNIÓN DE TIPOS
Todos los elementos de una lista deben ser del mismo tipo. En una tupla se pueden representar
valores de diferentes tipos, pero en las tuplas no es variable el número de elementos. Algunas veces
se quiere hacer una lista que tenga elementos del tipo entero y del tipo caracter.
Con una definición de datos se puede construir un tipo IntOrChar que tenga como elementos
enteros y caracteres:
xs :: [IntOrChar]
xs = [ Ent 1, Car ’a’, Ent 2, Ent 3 ]
El único precio es que se tiene que marcar cada elemento con una función constructora Ent o Car.
Estas funciones se pueden interpretar como funciones de conversión;
VOLVER
TIPOS ABSTRACTOS
Entonces se pueden usar los dos para la misma cosa. Se pueden usar ‘fechas’ como ‘n´umeros
racionales’, sin que el comprobador de tipos (en inglés, type-checker) devuelva errores.
Con las definiciones de datos realmente se pueden hacer nuevos tipos, de modo que no se pueda
intercambiar un Ratio con cualquier otro tipo (Int,Int). En vez de la definición de tipos podemos
escribir la siguiente definición de datos:
data Ratio = Rat (Int,Int)
Existe entonces solamente una función constructora. Para hacer una fracción con el numerador 3 y
el denominador 5, no es suficiente escribir (3,5), sino se tiene que escribir Rat (3,5). Como tipos de
unión se puede interpretar a la función Rat como función de conversión de (Int,Int) a Ratio.
Este método se usa mucho para hacer tipos abstractos. Un tipo abstracto consiste en una definición
de datos y una serie de funciones que se pueden aplicar al tipo definido (en el caso de Ratio por
ejemplo:
qSum, qRes, qMul en qDiv).
Como nombre de una función constructora, muchas veces se elige el mismo nombre que el tipo. Por
ejemplo:
VOLVER
En la definición de una función se pueden usar las funciones estándar y las funciones definidas por
el usuario, pero también se puede usar la propia función que se define en su definición. A tal
definición se la llama definición recursiva, como: f x = f x
Las funciones recursivas tienen sentido bajo las siguientes dos condiciones
El parámetro de la llamada recursiva es mas simple que el parámetro de la función que se quiere definir
Una definición recursiva de la función factorial es:
fac n | n==0 = 1
Donde
Otra manera de distinguir estos dos casos (caso base y caso recursivo) es usando patrones:
fac 0 = 1
fac (n+1) = (n+1) * fac n
El parámetro de la llamada recursiva (n) es menor que el parámetro de la función que se quiere
definir (n+1).
El uso de patrones tiene mucha relación con la tradición matemática del usar inducción.
Así, la definición matemática de la función potencia puede ser usada casi directamente como
función
x^0=1
x ^ (n+1) = x * x^n
La definición recursiva que usa patrones para distinguir diferentes casos, en lugar de expresiones
booleanas, se llama también definición inductiva.
Las funciones sobre listas también pueden ser recursivas. Una lista es ‘menor’ que otra si tiene
menos elementos. Así, función suma, puede ser definida de diferentes maneras.
suma lista | lista==[] = 0 (Sume la lista; si la lista esta vacía de por resultado igual a cero)
| otherwise = head lista + suma (tail lista) (sino sume la cabeza de lista más la suma de cola)
suma [] = 0
Es mas clara una definición con patrones, porque las diferentes partes en el patrón pueden conseguir
un nombre directamente, como cabeza y cola en la función suma, cuya versión recursiva requiere funciones
VOLVER
Comparación de Patrones
Un patrón es una expresión como argumentoen una ecuación.
Es posible definir una función dando más deuna ecuación paraésta.
Al aplicar la función a un parámetro concretola comparación de patrones
determina la ecuación a utilizar.
Regla para la comparación de patrones
ecuación.
Patrones constantes
Un patrón constante puede ser un número, uncaráctero un
constructor de dato.
f :: Integer →Bool
f 1 =True
f 2 =False
La definición de la conjunción y disyunción devalores lógicosusa
patrones constantes (TrueyFalseson dos constructores de datos
para el tipoBool)
Patrones para listas
Es posible utilizar patrones al definirfuncionesque trabajen con
listas.
[ ] sólo unificacon un argumento que sea unalista
vacía.
[x ], [x ,y], etc. sólo unifican con listas de uno,dos, etc.
argumentos.
(x :xs) unificacon listas con al menos un elemento
suma :: [Integer] →Integer
suma [ ] = 0
suma (x :xs) = x + suma xs
Patrones para tuplas
primero2 :: (Integer,Integer) →Integer
primero2 (x ,y) = x
primero3 :: (Integer,Integer,Integer) →Integer
primero3 (x ,y,z ) = x
Los patrones pueden anidarse.
sumaPares:: [(Integer,Integer)] →Integer
sumaPares[ ] = 0
sumaPares((x ,y) :xs) = x + y +sumaPares xs
Patrones aritméticos
Es unpatrón de la forma (n + k), donde k esun valor constante natural.
factorial :: Integer →Integer
factorial 0 = 1
factorial (n + 1) = (n + 1) *factorial n
VOLVER
Se llaman parámetros formales a los parámetros de una función en la definición de la misma, por
ejemplo x e y en: fxy=x*y
En una llamada a la función se dan parámetros actuales a la función, así en: f 17 (1+g 6)
Los parámetros actuales se sustituyen en los lugares de los parámetros formales cuando se llama a
una función. El resultado del anterior ejemplo es por tanto 17*(1+g 6). Por tanto, los parámetros
actuales son expresiones. Los parámetros formales eran hasta ahora solamente nombres
VOLVER
La declaración de una función f está formada por un conjunto de ecuaciones con el formato:
f < pat1 > < pat2 > . . . < patn > = < expresion >
Donde cada una de las expresiones < pat1 > < pat2 > . . . representa un argumento de la
función y se denominado un patrón. El número n de argumentos se denomina paridad.
Cuando una función está definida mediante más de una ecuación, será necesario evaluar una o más
argumentos de la función para determinar cuál de las ecuaciones aplicar.
Este proceso se denomina encaje de patrones. En los ejemplos anteriores se utilizó el patrón más
simple: una variable.
Así, en la definición de factorial: fact n = product [1..n], si se desea evaluar la expresión "fact 6"
es necesario:
Luego evaluar la expresión obtenida a partir de "product [1..n]" substituyendo la "n" con el "6".
VOLVER
ANÓNIMOS: Se representan por el caracter (_) y encajan con cualquier valor, pero no es posible
referirse posteriormente a dicho valor. Ejemplo:
cabeza (x:_) = x
cola (_:xs) = xs
PATRONES CON NOMBRE: Para poder referirnos al valor que está encajando, por ejemplo, en
lugar de definir f como:
f (x:xs) = x:x:xs
f p@(x:xs) = x:p
PATRONES n+k: Encajan con un valor entero mayor o igual que k. El valor referido por la
variable n es el valor encajado menos k. Ejemplo:
x^0=1
x ^ (n+1) = x * (x ^ n)
VOLVER
Las funciones pueden ser más flexibles utilizando funciones como parámetros. Muchas funciones
sobre listas tienen una función como parámetro. A estas se les llama funciones de orden superior.
map: Función de orden superior basada en el principio general ‘recorrer todos los elementos de
una lista’.
La función parámetro de map se aplica a cada elemento de la lista. La función map aplica su
xs = [ 1 , 2 , 3 , 4 , 5 ]
map cuadrado xs = [ 1 , 4 , 9 , 16 , 25 ]
[2,3,4,5,6,7,8,9,10,11]
filter (filtro). Función devuelve los elementos de una lista que cumplen alguna condición que se
xs = [ 1 , 2 , 3 , 4 , 5 ]
[4, 6, 8, 10]
foldr: Pliega la lista a un valor colocando un operador (uno de los dos parámetros), entre los
elementos de la lista. La función empieza por la derecha con el valor inicial (el otro parámetro).
Existe también una función foldl, que empieza por la izquierda. La función foldr inserta un
operador entre todos los elementos de una lista, empezando a la derecha con un valor dado:
xs = [ 1 , 2 , 3, 4, 5]
VOLVER
Escribir un carácter:
putChar :: Char → IO ()
No hacer nada
done :: IO ()
(>>) :: IO () → IO () → IO ()
Escribir un String
write :: String → IO ()
write [] = done
writeln :: String → IO ()
Leer un carácter
getChar :: IO Char
Generalización de done
return :: a → IO a
Implementaci on de done
done :: IO ()
done = return ()
(>>) :: IO a → IO b → IO b
Generalización de (>>)
(>>=) :: = IO a → (a → IO b) → IO b
Leer n caracteres
readn 0 = return []
Clase Monad
return :: a → m a
(>>=) :: m a → (a → m b) → m b
Notación do
readn 0 = return []
readn n = c ← getChar
cs ← readn (n-1)
return (c:cs)
VOLVER
p >>= return == p
(return e) >>= q = q e