Una Introducción agradable a Haskell
anterior siguiente
inicio
Idealmente, las tablas en un lenguaje funcional deberían ser vistas simplemente como funciones de índices a valores, pero pragmáticamente, para asegurar el acceso eficiente a los elementos de la tabla, necesitamos estar seguros de que podemos aprovecharnos de las características especiales de los dominios de estas funciones, que son isomorfas a los subconjuntos contiguos finitos de los números enteros. Haskell, por lo tanto, no trata las tablas como funciones generales con una operación de aplicación, sino como tipos abstractos de datos con una operación de indexación.
Podemos distinguir dos aproximaciones principales a las tablas funcionales: definición incremental y monolítica. En el caso incremental, tenemos una función que produce una tabla vacía de un tamaño dado y otra que tome una tabla, un índice, y un valor, produciendo una nueva tabla que se diferencie de la vieja solamente en el valor del índice. Obviamente, una implementación ingenua de tal semántica de la tabla sería intolerablemente ineficaz, requiriendo una nueva copia de la tabla para cada redefinición incremental; así, las implementaciones serias que usan esta aproximación emplean análisis estático sofisticado y mecanismos en tiempo de ejecución para evitar la copia excesiva. Por otro lado, la aproximación monolítica, construye una tabla de una vez, sin construcciones intermedias de la tabla. Aunque Haskell tiene un operador incremental para la actualización de la tabla, el uso principal de la tabla es monolítica.
Las tablas no son parte del Standard Prelude-- una librería estándar contiene las operaciones para tablas. Cualquier módulo que use tablas debe importar el módulo Array.
La librería Ix define una clase para los índices de
las tablas:
class (Ord a) => Ix a where
range :: (a,a) -> [a]
index :: (a,a) a -> Int
inRange :: (a,a) -> a -> Bool
Los declaraciones de instancias se proporcionan para Int,
Integer, Char, Bool, y tuplas de tipos
Ix; además, se pueden derivar instancias
automáticamente para los tipos enumerados y tuplas. Debemos ver
los tipos primitivos como índices vectoriales y las tuplas como
índices de matrices rectangulares multidimensionales. Observe
que el primer argumento de cada uno de las operaciones de la
clase Ix es un par de índices; éstos son típicamente los
límites (primero y último) de una tabla. Por ejemplo, los
límites de un vector de 10 elementos, con origen el cero de Int
serían (0,9), mientras que una matriz de 100 por
100 con origen-1 debe tener los límites ((1,1),(100,100)).
(En muchos otros lenguajes, tales límites serían escritos en
una forma como 1:100, 1:100, pero la forma actual
es mejor para el sistema de tipos, puesto que cada límite es del
mismo tipo que el índice general.)
La operación range toma un par de límites y produce la lista de los índices que caen entre esos límites, en el orden del índice. Por ejemplo,
range (0,4) => [0,1,2,3,4]
range ((0,0),(1,2)) => [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)]
El predicado inRange determina si un índice cae entre un par de límites dados. (Para un tipo tupla, este predicado es evaluado componente a componente.) Finalmente, la operación index es necesaria para acceder a un elemento determinado del array: dado el par de límites y un índice dentro del rango, la operación devuelve el ordinal del índice partiendo del origen dentro del rango; por ejemplo:
index (1,9) 2 => 1
index ((0,0),(1,2)) (1,1) => 4
La función de creación de una tabla monolítica Haskell construye una tabla a partir de un par de límites y una lista de
pares conteniendo índices y valores (una lista de
asociaciones):
array :: (Ix a) => (a,a) -> [(a,b)] -> Array a b
He aquí, por ejemplo, la definición de una tabla con los
cuadrados de los números del 1 al 100
squares = array (1,100) [(i, i*i) | i <- [1..100]]
El uso de listas por comprensión para la lista de
asociaciones es típico; además, estas expresiones se parecen a
las tablas por comprensión utilizados en el lenguaje Id [6].
El acceso a un elemento de la tabla se realiza a través del operador !, y los límites pueden ser extraidos con la función bounds:
squares!7 => 49
bounds squares => (1,100)
Podemos generalizar este ejemplo, parametrizando los límites
y la función a aplicar a cada índice en la creación:
mkArray :: (Ix a) => (a -> b) -> (a,a) -> Array a b
mkArray f bnds = array bnds [(i, f i) | i <- range bnds]
Así, podemos definir squares como mkArray (\i -> i * i) (1,100).
Muchas tablas se definen recursivamente, esto es, con los
valores de unos elementos dependiendo de los valores de otros.
Aquí, por ejemplo, tenemos una función que devuelve una tabla
con los números de Fibonacci:
fibs :: Int -> Array Int Int
fibs n = a where a = array (0,n) ([(0, 1), (1, 1)] ++
[(i, a!(i-2) + a!(i-1)) | i <- [2..n]])
Otro ejemplo de tal recurrencia es la matriz del
"frente de onda" n por n en la cual, los
elementos de la primera fila y la primera columna tienen todos el
valor 1 y cualquier otro elemento es la suma de sus vecinos del
oeste, noroeste y norte:
wavefront :: Int -> Array (Int,Int) Int
wavefront n = a where
a = array ((1,1),(n,n))
([((1,j), 1) | j <- [1..n]] ++
[((i,1), 1) | i <- [2..n]] ++
[((i,j), a!(i,j-1) + a!(i-1,j-1) + a!(i-1,j))
| i <- [2..n], j <- [2..n]])
La matriz del frente de onda es llamada así porque en una
implementación paralela, la repetición dicta que el cómputo
puede comenzar con la primera fila y columna en paralelo y
proceder en forma de cuña, viajando del noroeste al sureste. Es
importante observar, sin embargo, que no se especifica ningún
orden del cómputo en la lista de asociaciones.
En cada uno de nuestros ejemplos, hemos dado una única asociación a cada índice de la tabla y sólo para los índices que caen dentro de los límites del mismo, y ciertamente, debemos hacer esto en general para que una tabla quede perfectamente definida. Una lista de asociaciones con índices fuera de rango producen un error; si un índice no aparece o aparece más de una vez, no se produce un error de inmediato pero el valor de la tabla en ese índice queda indefinido, de tal manera que un acceso a ese índice en la tabla producirá un error.
Podemos relajar la restricción de que un índice aparezca
más de una vez en la lista de asociaciones especificando cómo
combinar múltiples valores asociados a un mismo índice. El
resultado es una tabla acumulativa:
accumArray :: (Ix a) => (b -> c -> b) -> b -> (a,a) -> [Assoc a c] -> Array a b
El primer argumento de un accumArray es la función
de acumulación, el segundo es el valor inicial (el mismo
para todos los elementos de la tabla), y el resto de argumentos
son los límites y la lista de asociaciones, como en la función array.
Típicamente, la función de acumulación es (+), y el
valor inicial es, cero; por ejemplo, esta función toma un par de
límites y una lista de valores (de tipo índice) y devuelve un
histograma; esto es, una tabla con el número de ocurrencias de
cada valor dentro de los límites:
hist :: (Ix a, Integral b) => (a,a) -> [a] -> Array a b
hist bnds is = accumArray (+) 0 bnds [(i, 1) | i <- is, inRange bnds i]
Supongamos que tenemos una colección de medidas en un
intervalo [a,b), y queremos dividir el intervalo en diez
partes y contar el número de medidas en cada una:
decades :: (RealFrac a) => a -> a -> [a] -> Array Int Int
decades a b = hist (0,9) . map decade
where decade x = floor ((x - a) * s)
s = 10 / (b - a)
Además de una función de creación monolítica de tablas,
Haskell tiene una función de actualización incremental, escrita
como un operador infijo //; el caso más simple
corresponde a una tabla a cuyo elemento de la posición i
se actualiza a v, se escribe como a // [(i, v)].
Los delimitadores usados se deben a que el argumento derecho es
una lista de asociaciones conteniendo un subconjunto propio de
índices de la tabla:
(//) :: (Ix a) => Array a b -> [(a,b)] -> Array a b
Como con la función array, los índices en la
lista de asociaciones deben ser únicos para los valores que
estén definidos. Por ejemplo, la función que intercambia dos
filas de una matriz sería:
swapRows :: (Ix a, Ix b, Enum b) => a -> a -> Array (a,b) c -> Array (a,b) c
swapRows i i' a = a // ([((i ,j), a!(i',j)) | j <- [jLo..jHi]] ++
[((i',j), a!(i ,j)) | j <- [jLo..jHi]])
where ((iLo,jLo),(iHi,jHi)) = bounds a
La concatenación aquí de dos listas por comprensión sobre
la misma lista de índice j es, sin embargo, levemente
ineficiente; es igual que escribir dos bucles en lugar de uno en
un lenguaje imperativo. No tema, ya que podemos realizar el
equivalente a una optimización por la fusión de bucles en
Haskell:
swapRows i i' a = a // [assoc | j <- [jLo..jHi],
assoc <- [((i ,j), a!(i',j)),
((i',j), a!(i, j))] ]
where ((iLo,jLo),(iHi,jHi)) = bounds a
Completamos nuestra introducción a las tablas en Haskell con
el ejemplo familiar de la multiplicación de matrices, utilizando
ventajosamente la sobrecarga para construir una función
suficientemente general. Estando involucradas la suma y
multiplicación de los elementos de las matrices, tomaremos una
función que multiplique cualquier tipo numérico, a no ser que
nos empeñemos en lo contrario. Adicionalmente, si tenemos
cuidado de aplicar sólo (!) y las operaciones de Ix
a los índices, tendremos genericidad sobre el tipo de los
índices, y en efecto, los tipos índices de las cuatro filas y
columnas no necesitan ser iguales. Sin embargo, por simplicidad,
supondremos que los índices de la columna de la izquierda y la
fila de la derecha tienen el mismo tipo, y además, sus límites
son iguales:
matMult :: (Ix a, Ix b, Ix c, Num d) =>
Array (a,b) d -> Array (b,c) d -> Array (a,c) d
matMult x y = array resultBounds
[((i,j), sum [x!(i,k) * y!(k,j) | k <- range (lj,uj)])
| i <- range (li,ui),
j <- range (lj',uj') ]
where ((li,lj),(ui,uj)) = bounds x
((li',lj'),(ui',uj')) = bounds y
resultBounds
| (lj,uj)==(li',ui') = ((li,lj'),(ui,uj'))
| otherwise = error "matMult: límites
incompatibles"
De otra forma, podemos definir matMult usando accumArray,
resultando una representación que recuerda a la formulación
usual en un lenguaje imperativo:
matMult x y = accumArray (+) 0 resultBounds
[((i,j), x!(i,k) * y!(k,j))
| i <- range (li,ui),
j <- range (lj',uj')
k <- range (lj,uj) ]
where ((li,lj),(ui,uj)) = bounds x
((li',lj'),(ui',uj')) = bounds y
resultBounds
| (lj,uj)==(li',ui') = ((li,lj'),(ui,uj'))
| otherwise = error "matMult: límites
incompatibles"
Podemos generalizar aún más haciendo la función de orden
superior, simplemente remplazando sum y (*) por
parámetros funcionales:
genMatMult :: (Ix a, Ix b, Ix c) =>
([f] -> g) -> (d -> e -> f) ->
Array (a,b) d -> Array (b,c) e -> Array (a,c) g
genMatMult f g x y = array resultBounds
[((i,j), f [x!(i,k) `g` y!(k,j) | k <- range (lj,uj)])
| i <- range (li,ui),
j <- range (lj',uj') ]
where ((li,lj),(ui,uj)) = bounds x
((li',lj'),(ui',uj')) = bounds y
resultBounds
| (lj,uj)==(li',ui') = ((li,lj'),(ui,uj'))
| otherwise = error "matMult: límites
incompatibles"
Los aficionados a APL reconocerán la utilidad de funciones
como las siguientes:
genMatMult maximum (-)
genMatMult and (==)
En la primera de ellas, los argumentos son matrices
numéricas, y el elemento (i,j) del resultado es la
máxima diferencia entre los correspondientes elementos de la
fila i-ésima y la columna j-ésima de las
entradas. En la segunda, los argumentos son matrices de cualquier
tipo con igualdad, y el resultado es una matriz booleana en la
que el elemento (i,j) es True sí y sólo sí la i-ésima
fila del primer argumento y la j-ésima columna del
segundo son iguales como vectores.
Obsérvese que los tipos de los elementos de genMatMult no necesitan ser iguales, sino apropiados para la función parámetro g. Podemos generalizar aún más eliminando el requerimiento de que los tipos índices de la primera columna y de la segunda fila sean los mismos, claramente, dos matrices son consideradas "multiplicables" si el número de columas de la primera y el número de filas de la segunda son iguales. El lector puede intentar derivar esta versión más general. (Indicación: Use la operación index para determinar las longitudes.)
Una Introducción agradable a Haskell
anterior siguiente
inicio