Data.Array

De Wikihaskell
Saltar a: navegación, buscar
Data.Array
Data.Array
Lenguaje Haskell
Biblioteca Data.Array
Autores Jacinto Calderón Collado
Miguel Ángel Utrillas Ramírez
Ricardo Vidal Ortiz

Contenido

Introducción

Haskell'98 soportan tan sólo un tipo de constructor para la clase Array, llamada a su vez Array y que proporciona arrays "en cajas" que son inmutables.

El concepto de estar "en cajas" significa que los elementos del array son tan sólo los valores habituales con los que trabaja Haskell, los cuales son evaluados bajo demanda y pueden incluso contener valores inferiores que no estén definidos.Por inmutables,nos referimos a que estos arrays, como cualquier otra estructura de datos funcional pura, tienen contenidos que se establecen en el momento de construirlos. Por lo tanto,los arrays de las operaciones no puedes modificarlos, tan sólo realizar consultas a estas, aunque bien es cierto que existen operaciones de modificación, pero estas devuelven arrays nuevos y nunca modifican el original. Esto permite utilizar arrays en código funcional puro a partir de listas.

Actualmente, los principales compiladores de Haskell, como son GHC y Hugs, proveen el mismo conjunto de librerías jerárquicas y estas contienen una nueva implementación de arrays, la cual es compatible con Haskell'98 y a su vez tiene muchas más características.

A lo largo de esta página veremos las distintas funciones que contiene la librería Data.Array, así como diversos ejemplos de utilización de estas que consideramos pueden resultar interesantes conocer.

Instalación

Instalación de Cabal

Utilizaremos el gestor de paquetes [Cabal] para instalar la librería Data.Array.

  • Instalación de Cabal en Windows

La versión de Cabal para Windows se desgarga puede descargar desde sitio oficial. Cuando lo instalamos debemos añadirlo al PATH de Windows.

  • Instalación para Linux

En distribuciones de tipo Debian, instalamos Cabal usando el gestor de paquetes:

sudo apt-get install cabal-install cpphs

Instalación de Data.Array

Es conveniente asegurarnos que tenemos todas las actualizaciones de Cabal:

sudo cabal update

Después instalamos la librería con este comando:

sudo cabal --hugs --prefix=/usr install array

Carga de la librería

Una vez instalada la librería, comprobaremos que está alojada en nuestro sistema intentando importarla en Hugs. El prompt de Hugs nos indica que hemos cargado la librería de forma correcta.

$ hugs -98
Hugs> :l Data.Array
Data.Array>

Arrays inmutables

La primera interfaz que nos proporciona esta librería es aquella que está definida por la clase tipada IArray (Data.Array.IArray), la cual está implementada para los arrays inmutables.

Clase Array Inmutable

Un tipo array inmutable tiene la forma ( a i e) donde a es el constructor de tipo array, i es el tipo indexado (un miembro de la clase Ix) y e es el tipo de elemento. La clase IArray está parametrizada a partir de a y e,d e modo que las instancias especializadas para ciertos tipos de elementos se pueden definir.

Un método de esta clase es por ejemplo bounds, el cual extrae los límites de un array innmutable.

bounds :: Ix i => a i e -> (i, i) 

Arrays inmutables no estrictos

El tipo de arrays inmutables no estrictos (en cajas) tiene sus indices en i y los elementos en e.

data Array i e :: * -> * -> *

Construcción de Array

Se construye un array inmutable a partir de un par de límites y una lista de asociaciones iniciales. Los límites son especificados como un par con el menor y el mayor de los límites en el array respectivamente. Por ejemplo, un vector originado de longitud 10 tiene por límites (1,10) y uno originado como una matriz de 10 por 10 tiene los límites ((1,1),(10,10)).

Una asociación es un par de la forma (i, x) , el cual define el valor del array desde el índice i hasta el x. Un array no está definido si cualquier índice de la lista está fuera de los límites. Si cualquiera de dos asociaciones en la lista tienen el mismo índice, el valor en ese índice es dependiente de la implementación.

Por ejemplo si definimos:

miArray = array (1, 3) [(1, "a"), (2, "b"), (3, "c")]

,estamos asociando a los tres índices del array unos valores "a", "b" y "c" respectivamente, fijando como límites , como es lógico, de uno a tres.Una vez construido nuestro array, podemos utilizar la función bounds nombrada con anterioridad:

Main> bounds miArray
(1,3)

No todos los índices que no están dentro de los límites del array necesitan aparecer en la lista de asociación, pero los valores asociados a cada índices que no aparezcan estarán indefinidos.

También podemos construir un array inmutable a partir de una lista inicial de elementos. La lista proporciona los elementos del array ordenados de forma ascendente comenzando con el índice más pequeño.

listArray :: (IArray a e, Ix i) => (i, i) -> [e] -> a i e 

Por ejemplo:

miArray2 = listArray (1,3) ["d","e","f"]

Por último, el tercer constructor del módulo de arrays inmutables es accumArray, el cual construye un array inmutable a partir de una lista de asociaciones. A diferencia de los arrays anteriores un mismo índice tiene permitido aparecer varias veces en la lista de asociaciones. Una función de acumulación se utiliza para combinar los valores de los elementos con el mismo índice.

miArray3 = accumArray (++) "" (1,3) [(1,"H"),(2," "),(1,"o"),(1,"l"),(3," "),(1,"a")]

Main> miArray3
array (1,3) [(1,"Hola"),(2," "),(3," ")]

Por lo tanto, dada una lista de valores de un tipo de índice, la función hist expuesta a continuación produciría un histograma del número de ocurrencias de cada índice sin necesidad de especificar un rango.

hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
hist bnds is = accumArray (+) 0 bnds [(i, 1) | i\<-is, inRange bnds i]

Accediendo a arrays

Utilizando (!) conseguimos obtener el elemento de un índice especificado dentro del array inmutable

(!) :: (IArray a e, Ix i) => a i e -> i -> e 

Main> miArray ! 2
"b"

indices devuelve una lista de todos los índices que son válidos dentro del array.

indices :: (IArray a e, Ix i) => a i e -> [i] 

Main> indices miArray
[1,2,3]

La función elems devuelve una lista con todos los elementos del array, en el mismo orden que sus índices.

elems :: (IArray a e, Ix i) => a i e -> [e] 

Main> elems miArray
["a","b","c"]

Y por último assocs que devuelve los contenidos de un arrat como una lista de asociaciones.

assocs :: (IArray a e, Ix i) => a i e -> [(i, e)] 

Main> assocs miArray
[(1,"a"),(2,"b"),(3,"c")]

Actualización incremental

La operación (//) utiliza un array y una lista de pares y devuelve un array idéntico al que ponemos en el argumento de la izquierda actualizado con las asociaciones en el argumento de la derecha. Hay que tener en cuenta que debemos ampliar los límites definidos para que funcione correctamente la inclusión de nuevos pares, por lo que si ampliásemos los límites de miArray a (1,4) podríamos añadir un par adicional.

(//) :: (IArray a e, Ix i) => a i e -> [(i, e)] -> a i e 

Main> (//) miArray [(4,"d")]
array (1,4) [(1,"a"),(2,"b"),(3,"c"),(4,"d")]

Para la mayor parte de los tipos array, esta operación es O(n), siendo n el tamaño del array.

Por otro lado está accum , que toma un array y una lista de asociaciones y acumula pares de la lista dentro del array con la función de acumulación f.

accum :: (IArray a e, Ix i) => (e -> e' -> e) -> a i e -> [(i, e')] -> a i e 

La siguiente operación accumArray la hemos definido usando accum.

accumArray f z b = accum f (array b [(i, z) | i \<- range b])

Arrays derivados

La función amap devuelve un array derivado del original aplicandole a este una función para cada uno de sus elementos.

amap :: (IArray a e', IArray a e, Ix i) => (e' -> e) -> a i e' -> a i e 

La función ixmap devuelve un array derivado del original aplicandole a este una función para cada uno de sus índices.

ixmap :: (IArray a e, Ix i, Ix j) => (i, i) -> (i -> j) -> a j e -> a i e Source

Main> ixmap (0,2) (\i -> i+2) (array (1,5) [(1,'A'),(2,'B'),(3,'C'),(4,'D'),(5,'E')]) 
array (0,2) [(0,'B'),(1,'C'),(2,'D')] 

Arrays IO mutables

La segunda interfaz está definida por la clase del tipo MArray, que es una abreviatura de "arrays mutables" y que está definida en el módulo Data.Array.IO y contiene operaciones para actualizar los elementos de un array en su posición. Los tipos de constructores para arays mutables están en IOArray y en IOUArray y tienen operaciones para crear, actualizar y consultar estos arrays que se construyen, todos pertenecientes a la mónada IO.

Veamos un ejemplo de código:

import Data.Array.IO
main = do arr <- newArray (1,10) 37 :: IO (IOArray Int Int)
          a <- readArray arr 1
          writeArray arr 1 64
          b <- readArray arr 1 
          print (a,b)

Este programa crea un array de 10 elementos con todos sus valores inicializados a 37 y lee el primer elemento del array. Después, el programa modifica el primer elemento y lo vuelve a leer. La declaración de tipo en la segunda línea es necesaria porque nuestro programa no proporciona el contexto suficiente para permitir al compilador determinar el tipo concreto de array.


Arrays mutables en la mónada ST

IOArray tiene una versión más general en STArray( y de la misma forma IOUArrays está reflejada por STUArray, ambas definidas en Data.Array.ST). Estos tipos de array permiten trabajar con arrays mutables en la mónada ST.


import Control.Monad.ST
import Data.Array.ST

buildPair = do arr <- newArray (1,10) 37 :: ST s (STArray s Int Int)
               a <- readArray arr 1
               writeArray arr 1 64
               b <- readArray arr 1
               return (a,b)

main = print $ runST buildPair

Con todo lo que hemos visto hasta ahora tenemos suficiente para usar cualquier tipo de array, y a menos que estemos interesados en temas de rendimiento, se determina como apropiado el uso de todas estas librerías. Las siguientes secciones sirven en general para seleccionar el array adecuado o para hacer que los programas ejecuten de forma más rápida.

Congelando y descongelando

Haskell permite conversión entre arrays mutables e inmutables mediante las funciones "freeze" (congelar) y "thaw" (descongelar).

freeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
thaw   :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e)


Por ejemplo, el siguiente código se encarga de convertir un Array en un STArray, modificandolo y después convirtiéndolo.

import Data.Array
import Control.Monad.ST
import Data.Array.ST

buildPair :: (Int, Int)
buildPair = let arr  = listArray (1,10) (repeat 37) :: Array Int Int
                arr' = modifyAsST arr
            in (arr ! 1, arr' ! 1)

modifyAsST :: Array Int Int -> Array Int Int
modifyAsST arr = runST $ do starr <- thaw arr
                            compute starr
                            newarr <- freeze starr
                            return newarr

compute :: STArray s Int Int -> ST s ()
compute arr = do writeArray arr 1 64

main = print buildPair

Las operaciones de congelación y descongelación copian el Array en su totalidad. Si queremos, podemos usar las mismas localizaciones de memoria antes y después de la congelación o descongelación pero eso puede conllevar a algunas restricciones de acceso.

Arrays diferenciales

Como ya hemos establecido, la operación de actualización de los arrays inmutables (IArray) tan sólo crea una copia nueva del array, lo cual es algo ineficiente pero es una operación pura, que se puede utilizar en funciones puras. Por otro lado, la actualización en arrays mutables (MArray) es eficiente pero tan sólo puede hacerse en código monádico.

La librería DiffArray (Data.Array.Diff) combina lo mejor de ambos módulos, pues soporta la interfaz IArray y además puede utilizarse de forma funcional pura aunque internamente se esté utilizando la actualización eficiente de los arrays mutables.

¿Donde está el truco?. DiffArray tiene una interfaz externa pura, pero internamente está representada como una referencia a IOArray.

Cuando el operador '//' se aplica a un diffarray, su contenido es físicamente actualizado en el mismo sitio. El array antiguo cambia de forma silenciosa su representación sin necesidad de cambiar el comportamiento visible, pues almacena un enlace a lo largo del nuevo array actual con la diferencia de estar siendo aplicado a los contenidos antiguos.

La librería proporciona dos constructores para arrays "diferenciales": DiffArray, que internamente está construida con IOArray, y DiffUArray, basada en IOUArray. Si realmente es necesario, puedes construir el nuevo tipo de array "diferencial" a partir de cualquier tipo MArray conviviendo con la mónada IO.

EL uso de DiffArray no difiere del de Array, la única diferencia radica en el consumo de memoria y en la velocidad.


import Data.Array.Diff

main = do
       let arr = listArray (1,1000) [1..1000] :: DiffArray Int Int
           a = arr ! 1
           arr2 = arr // [(1,37)]
           b = arr2 ! 1
       print (a,b)


Podemos usar 'seq' para forzar la evaluación de los elementos del array antes de que estos se actualicen:

import Data.Array.Diff

main = do
       let arr = listArray (1,1000) [1..1000] :: DiffArray Int Int
           a = arr ! 1
           b = arr ! 2
           arr2 = a `seq` b `seq` (arr // [(1,37),(2,64)])
           c = arr2 ! 1
       print (a,b,c)

Arrays desencajados

En la mayoría de implementaciones de evaluación perezosa, los valores están representados como punteros que apuntan a sus valores o a código para calcular su valor. Este nivel adicional de indirección que no necesita etiquetas es conocido como una caja. Por defecto,los arrays "en cajas" están compuestos por muchas de estas cajas, de las cuales cada una de ellas puede calcular su valor de forma independiente. Esto permite muchos trucos, como por ejemplo definir los elementos de un array a partir de otro ó tan sólo calcular los elementos especificos de un array únicamente cuando de estos se necesite. Sin embargo, para grandes arrays el coste es muy grande, y si se necesita de todo el array puede resultar un caos en cuestiones de rendimiento.

Los arrays desencajados(Data.Array.Unboxed), son muy parecidos a los arrays en el lenguaje C. Tan sólo contienen los valores ya planeados sin ese nivel adicional de indirección. Por ejemplo un array de 1024 elementos del tipo Int32 tan sólo utiliza 4kb de memoria.


Por supuesto, los arrays desencajados tienen sus desventajas. En primer lugar, estos arrays pueden ser contruidos unicamente con un tamaño previamente definido (Int, Word, Char, Bool, Ptr, Double y otros que están listados en la definición de clases de UArray). Podemos incluso implementar arrays desencajados por nuestra cuenta para otros tipos de array, incluyendo enumerados, pro Integer, String y otros tipos definidos con tamaño de variable no pueden ser elementos de arrays desencajados. En segundo lugar, sin ese nivel adicional de indirección, todos los elementos de un array desencajado deben ser evaluados cuando el array es evaluado, por lo que se pierden los beneficios de la evaluación perezosa. Indexar el array para leer tan sólo un elemento hará que se construya el array entero. Esto no supondrá demasiada pérdida si eventualmente necesitamos el array entero, pero previene de forma recursiva definir los elementos del array a partir de otro y eso puede ser muy costoso si tan sólo vamos a necesitar valores específicos.

De cualquier manera, los arrays desencajados son muy útiles como instrumentos de optimización y se recomienda que se usen lo más posible.

En todos los tipos de array de la librería hay partes de estos arrays.

Array - UArray          (module Data.Array.Unboxed)
IOArray - IOUArray      (module Data.Array.IO)
STArray - STUArray      (module Data.Array.ST)
DiffArray - DiffUArray  (module Data.Array.Diff)

Por lo tanto, reemplazar los arrays "en cajas" en tu programa por los desencajados es muy sencillo, tan sólo tienes que añadir la 'U' a la definición de tipos y estaría hecho. Por supuesto, si cambias de Array a UArray, no te olvides que debes añadir a la lista de imports "Data.Array.Unboxed".

Arrays almacenables

Un array almacenable (Data.Array.Storable) es un array mutable de entrada/salida que almacena su contenido en bloques de memoria contiguos.

Los elementos se almacenan de acuerdo a la clase 'Storable'.Se puede obtener el puntero a los contenidos del array para manipular sus elementos al igual que en lenguajes como C, de forma similar a IOUArray. La ventaja es que esta es compatible con C a través de la interfaz de funciones foráneas. Las direcciones de memoria de los arrays almacenables están manipuladas para podérselas pasar a las rutinas de C.

El puntero a los contenidos del array se obtiene mediante 'withStorableArray'. La idea es similar a 'ForeignPtr' , la cual es utilizada internamente aquí. El puntero debe ser usado sólo durante la ejecución de la acción de entrada/salida y devuelto por la función que se le pasa como argumento a 'withStorableArray'.

{-# OPTIONS_GHC -fglasgow-exts #-}
import Data.Array.Storable
import Foreign.Ptr
import Foreign.C.Types

main = do arr <- newArray (1,10) 37 :: IO (StorableArray Int Int)
          a <- readArray arr 1
          withStorableArray arr 
              (\ptr -> memset ptr 0 40)
          b <- readArray arr 1
          print (a,b)

foreign import ccall unsafe "string.h" 
    memset  :: Ptr a -> CInt -> CSize -> IO ()

Si queremos utilizar este puntero después, debemos asegurarnos de llamar a 'touchStorableArray' después del último uso del puntero, por lo que el array no se liberará tan pronto.

GHC 6.6 también añade la operación 'unsafeForeignPtrToStorableArray' que permite usar cualquier Ptr como dirección de 'StorableArray' y en particular trabaja con arrays que son devueltos por rutinas de C.

Un ejemplo del uso de este operación sería:

import Data.Array.Storable
import Foreign.Marshal.Alloc
import Foreign.Marshal.Array
import Foreign.ForeignPtr

main = do ptr <- mallocArray 10
          fptr <- newForeignPtr_ ptr
          arr <- unsafeForeignPtrToStorableArray (1,10) fptr :: IO (StorableArray Int Int)
          writeArray arr 1 64
          a <- readArray arr 1
          print a
          free ptr

Este ejemplo reserva memoria para 10 enteros y convierte 'Ptr Int' a 'ForeignPtr Int' y 'ForeignPtr Int' a 'StorableArray Int Int'. Tras esto, escribe y lee el primer elemento del array. Por último, la memoria usada por el array se deja libre con 'free' la cual emula la liberación de memoria de las rutinas de C. Podemos incluso activar la liberación automática de los bloques reservados reemplazando "newForeignPtr_ ptr" por "newForeignPtr finalizerFree ptr". En este caso la memoria se liberará de forma automática después del último uso del array, tal y como cualquier otro objeto Haskell.

Referencias

Herramientas personales