Una Introducción agradable a Haskell
anterior siguiente
inicio
Puesto que Haskell es un lenguaje funcional puro, todos los cómputos vienen descritos a través de la evaluación de expresiones (términos sintácticos) para producir valores (entidades abstractas que son vistas como respuestas). Todo valor tiene asociado un tipo. (Intuitivamente, podemos pensar que los tipos son conjuntos de valores.) Ejemplos de expresiones son los valores atómicos tales como el entero 5, o el carácter 'a', o la función \x -> x+1, y los valores estructurados como la lista [1,2,3] y el par ('b',4).
Ya que las expresiones denotan valores, las expresiones de tipo son términos sintácticos que denotan tipos. Ejemplos de expresiones de tipo son los tipos atómicos Integer (enteros con precisión ilimitada), Char (caracteres), Integer->Integer (funciones que aplican Integer sobre Integer), así como los tipos estructurados [Integer] (lista homogénea de enteros) y (Char,Integer) (par formado por un carácter y un entero).
Todos los valores de Haskell son de primera categoría
("first-class") ---pueden ser argumentos o resultados
de funciones, o pueden ser ubicados en estructuras de datos, etc.
Por otro lado, los tipos de Haskell no son de primera
categoría. En cierto sentido, los tipos describen valores, y la
asociación de un valor con su tipo se llama un tipificado (typing).
Usando los ejemplos anteriores, podemos escribir
"tipificaciones" como los siguientes:
5 :: Integer
'a' :: Char
inc :: Integer -> Integer
[1,2,3] :: [Integer]
('b',4) :: (Char,Integer)
El símbolo "::" puede leerse "tiene
el tipo".
En Haskell las funciones se definen usualmente a través de
una colección de ecuaciones. Por ejemplo, la función inc
puede definirse por una única ecuación:
inc n = n+1
Una ecuación es un ejemplo de declaración. Otra
forma de declaración es la declaración de tipo de una función
o type signature declaration (§4.4.1), con la
cual podemos dar de forma explícita el tipo de una función; por
ejemplo, el tipo de la función inc:
inc :: Integer -> Integer
Veremos más detalles sobre definiciones de funciones en la
Sección 3.
Por razones pedagógicas, cuando queramos indicar que una expresión e1 se evalúa, o "reduce" a otra expresión o valor e2, escribiremos:
e1 => e2
Por ejemplo:
inc (inc 3) => 5
El sistema de tipificación estático de Haskell define formalmente la relación entre tipos y valores (§4.1.4). Esta tipificación estática asegura que un programa Haskell está bien tipificado (type safe); es decir, que el programador no puede evaluar expresiones con tipos erróneos. Por ejemplo, no podemos sumar dos caracteres, ya que la expresión 'a'+'b' está mal tipificada. La ventaja principal del tipificación estática es bien conocida: todos los errores de tipificado son detectados durante la compilación. No todos los errores son debidos al sistema de tipos; una expresión tal como 1/0 es tipificable pero su evaluación provoca un error en tiempo de ejecución. No obstante, el sistema de tipos puede encontrar errores durante la compilación, lo que proporciona al programador una ayuda para razonar sobre los programas, y también permite al compilador generar un código más eficiente (por ejemplo, no se requiere ninguna información de tipo o pruebas durante la ejecución).
El sistema de tipos también asegura que los tipos que el usuario proporciona para las funciones son correctos. De hecho, el sistema de tipos de Haskell es lo suficientemente potente como para describir cualquier tipo de función (con algunas excepciones que veremos más tarde) en cuyos caso diremos que el sistema de tipos infiere tipos correctos. No obstante, son aconsejables las oportunas declaraciones de tipos para las funciones, como la proporcionada para la función inc, ya que el tipificado de funciones es una forma eficiente de documentar y ayudar al programador a detectar errores.
[El lector habrá notado que los identificadores que comienzan con mayúscula denotan tipos específicos, tales como Integer y Char, pero no los identificadores que denotan valores, como inc. Esto no es un convenio: es obligatorio debido a la sintaxis de Haskell. Además, todos los caracteres, mayúsculas y minúsculas, son significativos: foo, fOo, y fOO son identificadores distintos.]
Haskell proporciona tipos polimóficos ---tipos que son cuantificados universalmente sobre todos los tipos. Tales tipos describen esencialmente familias de tipos. Por ejemplo, (para_todo a)[a] es la familia de las listas de tipo base a, para cualquier tipo a. Las listas de enteros (e.g. [1,2,3]), de caracteres (['a','b','c']), e incluso las listas de listas de interos, etc., son miembros de esta familia. (Nótese que [2,'b'] no es un ejemplo válido, puesto que no existe un tipo que contenga tanto a 2 como a 'b'.)
[Los identificadores tales como el anterior a se llaman variables de tipo, y se escriben en minúscula para distinguirlas de tipos específicos, como Integer. Además, ya que Haskell solo permite el cuantificador universal, no es necesario escribir el símbolo correspondiente a la cuantificación universal, y simplemente escribimos [a] como en el ejemplo anterior. En otras palabras, todas las variables de tipos son cuantificadas universalmente de forma implícita.]
Las listas constituyen una estructura de datos comunmente utilizada en lenguajes funcionales, y constituyen una buena herramienta para mostrar los principios del polimorfismo. En Haskell, la lista [1,2,3] es realmente una abreviatura de la lista 1:(2:(3:[])), donde [] denota la lista vacía y : es el operador infijo que añade su primer argumento en la cabeza del segundo argumento (una lista). (: y [] son, respectivamente, los operadores cons y nil del lenguaje Lisp) Ya que : es asociativo a la derecha, también podemos escribir simplemente 1:2:3:[].
Como ejemplo de función definida por el usuario y que opera
sobre listas, consideremos el problema de contar el número de
elementos de una lista:
length :: [a] -> Integer
length [] = 0
length (x:xs) = 1 + length xs
Esta definición es auto-explicativa. Podemos leer las
ecuaciones como sigue: "La longitud de la lista vacía es 0,
y la longitud de una lista cuyo primer elemento es x y
su resto es xs viene dada por 1 más la longitud de xs."
(Nótese el convenio en el nombrado: xs es el plural de x,
y x:xs debe leerse: "una x seguida de
varias x).
Este ejemplo, además de intuitivo, enfatiza un aspecto importante de Haskell que debemos aclarar: la comparación de patrones (pattern matching). Los miembros izquierdos de las ecuaciones contienen patrones tales como [] y x:xs. En una aplicación o llamada a la función, estos patrones son comparados con los argumentos de la llamada de forma intuitiva ([] solo "concuerda" (matches) o puede emparejarse con la lista vacia, y x:xs se podrá emparejar con una lista de al menos un elemento, instanciándose x a este primer elemento y xs al resto de la lista). Si la comparación tiene éxito, el miembro izquierdo es evaluado y devuelto como resultado de la aplicación. Si falla, se intenta la siguiente ecuación, y si todas fallan, el resultado es un error.
La definición de funciones a través de comparación de patrones es usual en Haskell, y el usuario deberá familiarizarse con los distintos tipos de patrones que se permiten; volveremos a esta cuestión en la Sección 4.
La función length es también un ejemplo de función polimórfica. Puede aplicarse a listas con elementos de cualquier tipo, por ejemplo [Integer], [Char], o [[Integer]].
| length [1,2,3] | => | 3 |
| length ['a','b','c'] | => | 3 |
| length [[1],[2],[3]] | => | 3 |
He aquí dos funciones polimórficas muy útiles sobre listas,
que usaremos más tarde. La función head devuelve el
primer elemento de una lista, y la función tail
devuelve la lista salvo el primero:
head :: [a] -> a
head (x:xs) = x
tail :: [a] -> [a]
tail (x:xs) = xs
Al contrario que length, estas funciones no estan
definidas para todos los posibles valores de su argumento. Cuando
las funciones son aplicadas a la lista vacía se produce un error en tiempo de
ejecución.
Vemos que algunos tipos polimórficos son más generales que otros en el sentido de que el conjunto de valores que definen es más grande. Por ejemplo, el tipo [a] es más general que [Char]. En otras palabras: el tipo [Char] puede ser derivado del tipo [a] a través de una sustitución adecuada de a. Con respecto a este orden generalizado, el sistema de tipos de Haskell tiene dos propiedades importantes: en primer lugar, se garantiza que toda expresión bien tipificada tenga un único tipo principal (descrito después), y en segundo lugar, el tipo principal puede ser inferido automáticamente (§4.1.4). En comparación con un lenguaje con tipos monomórficos como C, el lector encontrará que el polimórfismo enriquece la expresividad, y que la inferencia de tipos reduce la cantidad de tipos usados por el programador.
El tipo principal de una expresión o función es el tipo más general que, intuitivamente, "contiene todos los ejemplares de la expresión." Por ejemplo, el tipo principal de head es [a]->a; los tipos [b]->a, a->a, o el propio a son demasiado generales, mientras que algo como [Integer]->Integer es demasiado concreto. La existencia de un único tipo principal es la característica esencial del sistema de tipos de Hindley-Milner, que es la base del sistema de tipos de Haskell, ML, Miranda, ("Miranda" es marca registrada de Research Software, Ltd.) y otros lenguajes (principalmente funcionales) .
Podemos definir nuestros propios tipos en Haskell a través de una declaración data, que introduciremos con una serie de ejemplos (§4.2.1).
Un dato predefinido importante en Haskell corresponde a los
valores de verdad:
data Bool = False | True
El tipo definido con tal declaración es Bool, y
tiene exactamente dos valores: True y False. Bool
es un ejemplo de constructor de tipo (sin argumentos),
mientras que True y False son constructores
de datos (o constructores, para abreviar).
En forma similar, podemos definir un tipo color:
data Color = Red | Green | Blue | Indigo | Violet
Tanto Bool como Color son ejemplos de
tipos enumerados, puesto que constan de un número finito de
constructores.
El siguiente es un ejemplo de tipo con un solo constructor de
dato:
data Point a = Pt a a
Al tener un solo constructor, un tipo como Point es
llamado a menudo un tipo tupla, ya que esencialmente es un
producto cartesiano (en este caso binario) de otros tipos. (La
tuplas son conocidas en otros lenguajes como registros.) Por el
contrario, un tipo multi-constructor, tal como Bool o Color,
se llama una "suma de tipos" o tipo unión (disjunta).
Sin embargo, lo más importante es que Point es un ejemplo de tipo polimórfico: para cualquier tipo t, define el tipo de los puntos cartesianos que usan t como eje de coordenadas. El tipo Point puede también verse como un constructor de tipos unario, ya que a partir de un tipo t podemos obtener un nuevo tipo Point t. (En el mismo sentido, usando el ejemplo de la listas, [] es también un constructor de tipos: podemos aplicar el constructor [] a un tipo t para obtener un nuevo tipo [t]. La sintaxis de Haskell permite escribir [t] en lugar de [] t. Similarmente, -> es otro constructor de tipos binario: dados dos tipos "t" y "u", t->u es el tipo de las funciones que aplican datos de tipo "t" a elementos de tipo "u".)
Nótese que el tipo del constructor de datos Pt es a -> a -> Point a,
y las siguientes asignaciones de tipos son válidas:
Pt 2.0 3.0 :: Point Float
Pt 'a' 'b' :: Point Char
Pt True False :: Point Bool
Por otro lado, una expresión tal como Pt 'a' 1
está erróneamente tipificada, ya que 'a' y 1 son
de tipos diferentes.
Es importante distinguir entre la aplicación de un constructor de datos para obtener un valor, y la aplicación de un constructor de tipos para obtener un tipo; el primero tiene lugar durante el tiempo de ejecución, que es cuando se computan cosas en Haskell, mientras que el último tiene lugar en tiempo de compilación y forma parte del proceso de tipificado que asegura un "tipo seguro".
[Constructores de tipo como Point y constructores de
datos como Pt aparecen en niveles distintos de la
declaración, lo que permite que el mismo nombre pueda usarse
como constructor de tipos y como constructor de datos, como vemos
en:
data Point a = Point a a
Esto puede llevar a una pequeña confusión al principio,
pero sirve para crear un enlace obvio entre el constructor de
datos y el de tipo.]
Los tipos pueden ser recursivos, como el siguiente tipo para
árboles binarios:
data Tree a = Leaf a | Branch (Tree a) (Tree a)
Con ello hemos definido un tipo polimórfico cuyos elementos
son o bien hojas conteniendo un valor de tipo a, o nodos
internos ("ramas") conteniendo (en forma recursiva) dos
subárboles.
En la lectura de declaraciones de datos como la anterior,
recordemos que Tree es un constructor de tipos, mientras
que Branch y Leaf son constructores de datos.
La declaración anterior, además de establecer una conexión
entre estos constructores, define esencialmente los tipos para
los constructores Branch y Leaf:
Branch :: Tree a -> Tree a -> Tree a
Leaf :: a -> Tree a
Con este ejemplo tenemos un tipo suficientemente rico que
permite definir algunas funciones (recursivas) interesantes que
hagan uso de éste. Por ejemplo, supongamos que queremos definir
una función fringe que devuelva todos los elementos de
las hojas de un árbol de izquierda a derecha. En primer lugar es
esencial escribir el tipo de la nueva función; en este caso
vemos que el tipo debe ser Tree a -> [a].
Es decir, fringe es una función polimórfica que, para
cualquier tipo a, aplica árboles de a sobre
listas de a. Una definición adecuada es la siguiente:
fringe :: Tree a -> [a]
fringe (Leaf x) = [x]
fringe (Branch left right) = fringe left ++ fringe right
donde ++ es el operador infijo que concatena dos
listas (su definición completa se verá en la Section 9.1). Al igual que
la función length vista anteriormente, la función fringe
está definida mediante comparación de patrones, salvo que los
patrones implicados son los constructores de la definición dada
por el usuario: Leaf y Branch. [Nótese que los
parámetros formales son fácilmente identificados ya que
comienzan con letras minúsculas.]
Por conveniencia, Haskell proporciona una forma para definir sinónimos
de tipos; es decir, nombres de tipos usados varias veces. Los
sinónimos de tipo son creados a través de una declaración type
(§4.2.2).
He aquí algunos ejemplos:
type String = [Char]
type Person = (Name,Address)
type Name = String
data Address = None | Addr String
Los sinónimos no definen tipos nuevos, sino simplemente
proporcionan nuevos nombres a tipos ya existentes. Por ejemplo,
el tipo Person -> Name es precisamente
equivalente al tipo (String,Address) -> String.
Los nombres nuevos son a menudo más cortos que los tipos
nombrados, pero éste no es el único propósito de los
sinónimos de tipos: éstos pueden mejorar la legibilidad de los
programas a través de nemotécnicos; en efecto, los ejemplos
anteriores enfatizan este hecho. Podemos dar nuevos nombres a
tipos polimórficos:
type AssocList a b = [(a,b)]
Este es el tipo de las "listas de asociaciones"
que asocian valores de tipo a con otros de tipo b.
Antes hemos introducido varios tipos "predefinidos" tales como listas, tuplas, enteros y caracteres. También mostramos como el programador puede definir nuevos tipos. Además de una sintaxis especial ¿los tipos predefinidos tienen algo más de especial? La respuesta es no. La sintaxis especial es por conveniencia y consistencia, junto a algunas razones históricas, pero no tiene ninguna consecuencia semántica.
Enfatizamos este punto diciendo que la apariencia de las
declaraciones de éstos tipos predefinidos es especial. Por
ejemplo, el tipo Char puede ser descrito en la forma:
data Char = 'a' | 'b' | 'c' | ... -- Esto
no es código Haskell
| 'A' | 'B' | 'C' | ... -- válido!
| '1' | '2' | '3' | ...
...
Los nombres de los constructores no son válidos
sintácticamente; ello lo podríamos arreglar escribiendo algo
como lo siguiente:
data Char = Ca | Cb | Cc | ...
| CA | CB | CC | ...
| C1 | C2 | C3 | ...
...
Tales constructores son más concisos, pero no son los
habituales para representar caracteres.
En cualquier caso, la escritura de código "pseudo-Haskell" tal como la anterior ayuda a aclarar la sintaxis especial. Vemos que Char es, en efecto, un tipo enumerado compuesto de un gran número de constructores (constantes). Por ejemplo, visto Char de esta forma aclaramos qué patrones pueden aparecer en las definiciones de funciones; es decir, qué constructores de este tipo podemos encontrarnos.
Este ejemplo también muestra el uso de los comentarios en Haskell; los caracteres -- y los sucesivos hasta el final de la línea son ignorados. Haskell también permite comentarios anidados que tienen las forma {-...-} y pueden aparecer en cualquier lugar (§2.2).]
Similarmente, podemos definir Int (enteros de precisión limitada) y Integer
en la forma:
data Int = -65532 | ... | -1 | 0 | 1 | ... | 65532 -- más
pseudo-código
data Integer = ... -2 | -1 | 0 | 1 | 2 ...
donde -65532 y 65532, representan el mayor
y el menor entero en precisión fija para una implementación concreta. Int es un tipo enumerado más largo que Char,
pero es finito! Por el contrario, el pseudo-código para Integer
(el tipo de los enteros con precisión arbitraria) debe verse
como un tipo enumerado infinito.
Las tuplas también son fáciles de definir en la misma forma:
data (a,b) = (a,b) -- más
peudo-código
data (a,b,c) = (a,b,c)
data (a,b,c,d) = (a,b,c,d)
. .
. .
. .
Cada una de las declaraciones anteriores define una tupla de
una longitud particular, donde (...) juega distintos
papeles: a la izquierda como constructor de tipo, y a la derecha
como constructor de dato. Los puntos verticales después de la
última declaración indican un número infinito de tales
declaraciones, reflejando el hecho de que en Haskell están
permitidas las tuplas de cualquier longitud.
La listas son manipulables fácilmente, y lo que es más
importante, son recursivas:
data [a] = [] | a : [a] -- más
peudo-código
Vemos que esto se ajusta a lo ya dicho sobre listas: []
es la lista vacía, y : es el constructor infijo de
listas; de esta forma [1,2,3] es equivalente a la lista 1:2:3:[].
(: es asociativo a la derecha.) El tipo de []
es [a], y el tipo de : es a->[a]->[a].
[De esta forma ":" está definido con una sintaxis legal---los constructores infijos se permiten en declaraciones data, y (para describir la comparación de patrones) son distinguidos de los operadores infijos ya que comienzan con el carácter ":" (una propiedad satisfecha trivialmente por ":").]
En este punto, el lector deberá notar con cuidado las diferencias entre tuplas y listas, ya que las definiciones anteriores lo aclaran suficientemente. En particular, nótese la naturaleza recursiva de las listas, con longitud arbitraria y cuyos elementos son homogéneos, y la naturaleza no recursiva de una tupla concreta, que tiene una longitud fija, en la cual los elementos son heterogéneos. Las reglas de tipificado para tuplas y listas deberían quedar claras ahora:
Para (e1,e2,...,en), n>=2, si ti es el tipo de ei, entonces el tipo de la tupla es (t1,t2,...,tn).
Para [e1,e2,...,en], n>=0, cada ei debe tener el mismo tipo t, y el tipo de la lista es [t].
Como en algunos dialectos de Lisp, las listas son muy útiles
en Haskell, y al igual que en otros lenguajes funcionales, existe
aún una sintaxis más adecuada para su descripción. Además de
los constructores de listas ya introducidos, Haskell proporciona
expresiones conocidas como listas por comprensión que
introducimos con un ejemplo:
[ f x | x <- xs ]
Intuitivamente, esta expresión puede leerse como "la
lista de todos los f x tales que x recorre
xs." La similitud con la notación de los conjuntos
no es una coincidencia. La frase x <- xs se
llama un generador, y pueden utilizarse varios, como en :
[ (x,y) | x <- xs, y <- ys ]
Tal lista por comprensión determina el producto cartesiano
de dos listas xs y ys. Los elementos son
seleccionados como si los generadores fueran anidados de
izquierda a derecha (con el de más a la derecha variando el
último); es decir, si xs es [1,2] e ys
es [3,4], el resultado es [(1,3),(1,4),(2,3),(2,4)].
Además de los generadores, se permiten expresiones booleanas
llamadas guardas que establecen restricciones sobre los
elementos generados. Por ejemplo, he aquí una definición
compacta del algoritmo de ordenación favorito de todo el mundo:
quicksort [] = []
quicksort (x:xs) = quicksort [y | y <- xs, y<x ]
++ [x]
++ quicksort [y | y <- xs, y>=x]
Como otra ayuda en la descripción de listas, Haskell admite una sintaxis especial para secuencias aritméticas, que mostramos con una serie de ejemplos:
| [1..10] | => | [1,2,3,4,5,6,7,8,9,10] |
| [1,3..10] | => | [1,3,5,7,9] |
| [1,3..] | => | [1,3,5,7,9, ... (secuencia infinita) |
Veremos algo más sobre secuencias aritméticas en la Sección 8.2, y sobre "listas infinitas" en la Sección 3.4.
Como otro ejemplo de sintaxis especial para tipos
predefinidos, hacemos notar que la cadena de caracteres "hello"
es una forma simplificada de la lista de caracteress ['h','e','l','l','o'].
Además, el tipo de "hello" es String,
donde String es un sinónimo de tipo predefinido:
type String = [Char]
Esto significa que podemos usar las funciones polimórficas
sobre listas para operar con cadenas (strings). Por ejemplo:
"hello" ++ " world" => "hello world"
Una Introducción agradable a Haskell
anterior siguiente inicio