Una Introducción agradable a Haskell
anterior siguiente
inicio
En esta sección, introduciremos las clases estándar predefinidas de Haskell. Hemos simplificado algo las clases omitiendo algunos de los métodos menos interesantes; el informe de Haskell contiene una descripción más completa. Por último, algunas de las clases estándar son parte de las bibliotecas de Haskell; puede verse una descripción de éstas en el informe de bibliotecas de Haskell.
Las clases Eq y Ord han sido ya discutidas. La definición de Ord en el Prelude es más compleja que la versión simplificada presentada antes. En particular, observe el método compare:
data Ordering
= EQ | LT | GT
compare
:: Ord a => a -> a -> Ordering
El método compare es suficiente para que queden definidos todos los otros métodos (por defecto) en esta clase y es la mejor forma de crear instancias de Ord.
La clase Enum posee un conjunto de operaciones que subyacen bajo la sintaxis de las secuencias aritméticas; por ejemplo, la secuencia [1,3..] es simplemente una sintaxis más cómoda para la expresión enumFromThen 1 3 (véase §3.10 para la traducción formal). Podemos observar ahora que es posible usar las secuencias aritméticas para generar listas de cualquier tipo que sea una instancia de la clase Enum. Esto incluye no solo la mayoría de los tipos numéricos, sino que también al tipo Char, de modo que, por ejemplo, ['a'..'z'] denota la lista de todas las letras minúsculas en orden alfabético. Además, es fácil realizar la correspondiente instancia de la clase Enum para los tipos enumerados definidos por el programador, como Color. Si se ha realizado ésta, entonces tendremos:
[Red..Violet] => [Red, Green, Blue, Indigo, Violet]
Obsérvese que la secuencia es aritmética en el sentido de que el incremento entre valores es constante, aunque los valores no son números. La mayoría de los tipos instancias de Enum pueden ser transladados a enteros; para estos tipos, las funciones fromEnum y toEnum convierten entre Int y un tipo en la clase Enum.
Las instancias de la clase Show son aquellos tipos que pueden ser convertidos en cadenas de caracteres (habitualmente para realizar operaciones de E/S). La clase Read proporciona operaciones para analizar (parse) cadenas de caracteres y obtener los valores que éstas representan. La función más simple de la clase Show es show:
show :: (Show a) => a -> String
Como puede esperarse, show toma cualquier valor del tipo apropiado y devuelve su representación como una cadena de caracteres (una lista de caracteres); por ejemplo, show (2+2), produce como resultado "4". Sin embargo, habitualmente necesitaremos producir cadenas de caracteres más complejas partir de varios valores, como en el caso de
"The sum of " ++ show x ++ " and " ++ show y ++ " is " ++ show (x+y) ++ "."
pero todas estas concatenaciones resultan un poco ineficientes. Concretamente, consideremos una función para representar los árboles binarios de la sección 2.2.1 como cadenas de caracteres, con marcadores adecuados para reflejar el anidamiento de los subárboles y la distinción entre las ramas izquierda y derecha (supuesto que el tipo de los elementos almacenados en el árbol es representable como una cadena de caracteres):
showTree
:: (Show a) => Tree a -> String
showTree (Leaf x) =
show x
showTree (Branch l r) = "<" ++
showTree l ++ "|" ++ showTree r ++ ">"
Dado que (++) tiene complejidad lineal sobre la longitud de su argumento izquierdo, showTree tiene complejidad cuadrática sobre el tamaño del árbol.
El método shows puede ser usado para obtener una complejidad lineal:
shows :: (Show a) => a -> String -> String
shows toma un valor mostrable y una cadena, y devuelve la concatenación de la representación del valor con la cadena segundo argumento. El segundo argumento hace las veces de una cadena acumuladora, y show puede ser definido como shows con la cadena vacía como acumulador. Aquí aparece la definición por defecto de la función show en la clase Show:
show x = shows x ""
Podemos usar shows para definir una versión más eficiente de showTree, que también usa un argumento como cadena acumuladora:
showsTree
:: (Show a) => Tree a -> String -> String
showsTree (Leaf x) s = shows x s
showsTree (Branch l r) s= '<' : showsTree l ('|' :
showsTree r ('>' : s))
Esto resuelve el problema de eficiencia original (showsTree tiene complejidad lineal), aunque la representación de esta función (y de otras similares) puede ser mejorada. Comencemos por definir un sinónimo de tipo:
type ShowS = String -> String
Este es el tipo de una función que devuelve la representación como cadena de caracteres de algo seguida de una cadena acumuladora. En segundo lugar, podemos evitar trabajar explícitamente con acumuladores, y a la vez, evitar el apilamiento de paréntesis en la parte derecha de la definición, si usamos la composición de funciones:
showsTree
:: (Show a) => Tree a -> ShowS
showsTree (Leaf x) =
shows x
showsTree (Branch l r) = ('<':) . showsTree l
. ('|':) . showsTree r . ('>':)
Con esto hemos hecho algo más que ordenar un poco el código: hemos pasado de una representación a nivel de objetos (en este caso, cadenas de caracteres) a una representación a nivel de funciones. Podemos considerar que el tipo de la función indica que showsTree convierte un árbol en una función mostradora. Las funciones como ('<' :) o ("a string" ++) son funciones mostradoras primitivas, y podemos construir funciones más complejas usando la composición de funciones.
Ya que podemos transformar árboles en cadenas de caracteres, consideremos el problema inverso. La idea básica es construir un analizador (parser) para un tipo a, como una función que toma una cadena de caracteres y devuelve una lista de pares con tipo (a, String)[9]. El Prelude define un sinónimo de tipo para estas funciones:
type ReadS a = String -> [(a,String)]
Normalmente, un analizador devuelve una lista con un solo elemento, conteniendo el valor de tipo a que fue leído de la cadena de entrada y el resto de la cadena que queda por analizar. Si el análisis no fue posible, entonces, el resultado es la lista vacía, y si hay más de un análisis posible (ambiguedad), la lista resultante contendrá más de un par. La función reads se comporta como un analizador para cualquier tipo instancia de la clase Read:
reads :: (Read a) => ReadS a
Podemos usar esta función para definir una función analizadora para la representación mediante cadenas de caracteres de los árboles binarios producida por showsTree. Las listas por comprensión son un mecanismo adecuado para construir tales analizadores (Una aproximación aún más elegante es usar mónadas y combinadores de analizadores. Existe una biblioteca para esto que es distribuida con la mayoría de los sistemas Haskell):
readsTree
:: (Read a) => ReadS (Tree a)
readsTree ('<':s)
= [(Branch l r, u) | (l, '|':t) <- readsTree s,
(r, '>':u) <- readsTree t ]
readsTree
s
= [(Leaf x, t) |
(x,t) <- reads s]
Examinemos esta función en detalle por un momento. Los casos a considerar son dos: Si el primer carácter de la cadena a analizar es '<', deberíamos tener la representación de una rama; en otro caso, tenemos una hoja. En el primer caso, si denotamos al resto de la cadena de entrada a partir del caracter menor ('<') con el nombre s, cualquier análisis posible debe ser un árbol con la forma Branch l r donde el resto de la cadena por analizar puede ser llamado u, siempre y cuando:
Obsérvese la capacidad expresiva que se obtiene de la combinación del uso de patrones y las listas por comprensión: La forma del análisis resultante viene dado por la expresión principal de la lista por comprensión, las dos primeras condiciones anteriores vienen reflejadas por el hecho de que el primer generador ("(l, '|':t) usa la lista de análisis de s."), y las demás condiciones quedan reflejadas con el segundo generador.
La segunda ecuación de la definición anterior dice simplemente que para analizar la representación de una hoja, es necesario analizar un elemento del árbol y aplicar el constructor Leaf al valor obtenido.
Aceptaremos por el momento que existe una instancia de la clase Read (y Show) para el tipo Integer (y para otros más), que proporciona una función reads que se comporta como es de esperar, por ejemplo:
(reads "5 golden rings") :: [(Integer,String)] => [(5, " golden rings")]
A partir de esto, el lector debería verificar las siguientes
evaluaciones:
| readsTree "<1|<2|3>>" | => | [(Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)), "")] |
| readsTree "<1|2" | => | [] |
Hay un par de limitaciones en la definición dada de readsTree. Una es que el analizador es demasiado rígido, y no permite espacios en blanco antes o entre los elementos que forman parte de la representación del árbol; la otra es que el modo en el que se analizan los delimitadores es bastante distinto del modo en que se analizan los valores hoja y los subárboles, lo cual no es uniforme y hace que la definición sea más difícil de comprender. Podemos solucionar ambos problemas usando el analizador léxico que se define en el Prelude:
lex :: ReadS String
lex devuelve normalmente una lista con un solo elemento que es un par de cadenas de caracteres: el primer lexema en la cadena de entrada y el resto de la cadena de entrada. La reglas léxicas son las de Haskell, incluyendo el tratamiento de comentarios, que lex ignora, junto con los espacios en blanco. Si la cadena de entrada está vacía o contiene tan solo espacios en blanco y comentarios, lex devuelve [("","")]; si la entrada no está vacía, pero tampoco comienza con un lexema válido tras los espacios en blanco y comentarios iniciales, lex devuelve [].
Usando el analizador léxico, el analizador para el árbol puede ser definido del siguiente modo:
readsTree
:: (Read a) => ReadS (Tree a)
readsTree
s
= [(Branch l r, x) | ("<", t) <- lex s,
(l, u) <- readsTree t,
("|", v) <- lex u,
(r, w) <- readsTree v,
(">", x) <- lex
w ]
++
[(Leaf x, t) | (x, t) <-
reads s ]
Podemos usar readsTree y showsTree para hacer que el tipo(Read a) => Tree a sea una instancia de la clase Read y (Show a) => Tree a una instancia de Show. Esto nos permitirá usar las funciones sobrecargadas genéricas del Prelude para analizar y mostrar árboles. Además, será posible automáticamente analizar y mostrar otros tipos que contengan árboles como componentes, por ejemplo, [Tree Integer]. Tal como están definidos, readsTree y showsTree tienen prácticamente los tipos adecuados para ser métodos de las clases Show y Read. Los métodos showPrec y readPrec son versiones parametrizadas de shows y reads. EL parámetro extra es un nivel de precedencia, usado para colocar paréntesis de forma adecuada cuando se utilizan constructores infijos. Para tipos tales como Tree, la precedencia es ignorada. Las instancias de Show y Read para Tree son:
instance Show a => Show (Tree a) where
showPrec _ x = showsTree x
instance Read a => Read (Tree a) where
readsPrec _ s = readsTree s
Esto, sin embargo, es una versión muy ineficiente de Show. Observe que la clase Show define por defecto los métodos showsPrec y show, permitiendo al usuario definir uno de ellos en una declaración de instancia. Dado que cada uno se define en función del otro, una declaración de instancia que no defina ninguno entrará en un bucle indefinido cuando se llame a uno de ellos. Otras clases tales como Num también tienen estos "interbloqueos por defecto".
El lector interesado en profundizar sobre Read y Show puede consultar §D para más detalles.
Podemos probar las instancias de Read y Show aplicando la siguiente composición de funciones (read . show) (que debe comportarse como la función identidad) a algunos árboles, donde read es una especialización de reads:
read :: (Read a) => String -> a
Esta función produce un error si no hay un análisis único o si la entrada contiene algo más que la representación de un valor del tipo a y comentarios y espacios en blanco opcionales.
Recuerde la instancia Eq para árboles que presentamos en la Sección 5; tal declaración es simple---y laboriosa--- de construir: requerimos que el tipo de los elementos de las hojas dispongan de la igualdad; entonces, dos hojas son iguales si y sólo si contienen elementos iguales, y dos ramas son iguales si y sólo si sus subárboles izquierdo y derecho son iguales respectivamente. Cualesquiera otros dos árboles son distintos:
instance (Eq a) => Eq (Tree a) where
(Leaf x) == (Leaf
y) = x == y
(Branch l r) == (Branch l' r')
= l == l' && r == r'
_
==
_
= False
Afortunadamente, no necesitamos realizar esta tediosa tarea cada vez que necesitemos el operador de igualdad para un nuevo tipo; la instancia Eq puede ser derivada automáticamente desde la propia declaración:
data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Eq
La cláusula deriving produce de forma implícita una declaración de instancia Eq justo igual que la de la Sección 5. Las instancias de Ord, Enum, Ix, Read, y Show pueden ser generadas por la cláusula deriving. [Tras deriving, más de una clase puede ser especificada, en cuyo caso la lista de nombres deberá ir entre paréntesis y separados por comas.]
La instancia Tree para la clase Ord es ligeramente más complicada que la instancia Eq:
instance (Ord a) => Ord (Tree a) where
(Leaf _) <=
(Branch _) = True
(Leaf x) <=
(Leaf y) = x
<= y
(Branch _) <= (Leaf
_) = False
(Branch l r) <= (Branch l' r')
= l == l' && r <= r' || l <= l'
Esto especifica un orden lexicográfico: los constructores están ordenados según el orden en que aparecen en la declaración data, y los argumentos de un constructor son comparados de izquierda a derecha. Recuerde que el constructor de listas es semánticamente equivalente a un constructor ordinario de dos argumentos. En efecto, la siguiente es su declaración completa:
data [a] = [] | a : [a] deriving (Eq, Ord) -- pseudo-código
(Las listas son también instancias de Show y Read, pero estas no aparecen como derivadas.) Las instancias derivadas de Eq y Ord para las listas son las usuales; en particular, las cadenas, como listas de caracteres, están ordenadas según determina el tipo subyacente Char, donde una subcadena inicial de otra es considerada menor; por ejemplo, "cat" < "catalog".
En la práctica en la mayoría de las ocasiones, las instancias de Eq y Ord son derivadas en lugar de definidas por el usuario. Sólo deberíamos dar las definiciones de igualdad y ordenación cuando éstas sean especiales, siendo cuidadosos en mantener las propiedades algebraicas de relación de equivalencia y orden total respectivamente que se esperan de estas relaciones. Por ejemplo, un predicado (==) no transitivo, puede ser desastroso, confundiendo a los lectores del programa y confundiendo a cualquier transformación de programas, ya sea manual o automática que confía en que el predicado (==) sea una aproximación de la definición de igualdad. No obstante, a veces es necesario proveer instancias de Eq u Ord diferentes de aquellas que serían derivadas; probablemente el ejemplo más significativo sea el de un tipo abstracto de datos en el cual dos valores concretos diferentes puedan representar el mismo valor abstracto.
Un tipo enumerado puede tener una instancia derivada de Enum, y aquí de nuevo, el orden es el de los constructores en la declaración data. Por ejemplo:
data Day = Sunday | Monday | Tuesday | Wednesday
| Thursday |
Friday | Saturday
deriving (Enum)
Aquí hay algunos ejemplos simples del uso de la instancia derivada para este tipo:
| [Wednesday..Friday] | => | [Wednesday, Thursday, Friday] |
| [Monday, Wednesday ..] | => | [Monday, Wednesday, Friday] |
Es posible realizar instancias derivadas de Read (Show) para aquellos tipos cuyas componentes también sean derivadas de Read (Show). (Las instancias de Read y Show para la mayoría de los tipos estándar están disponibles en el Prelude. Algunos tipos, tales como el tipo función (->), tienen una instancia Show pero no su correspondiente Read.) La representación textual definida por una instancia derivada Show es consistente con la apariencia de las expresiones constantes en Haskell del tipo en cuestión. Por ejemplo, si añadimos Show y Read a la cláusula deriving para el tipo Day, anterior, obtenemos
show [Monday..Wednesday] => "[Monday,Tuesday,Wednesday]"
Una Introducción agradable a Haskell
anterior siguiente
inicio