Tema 18: El tipo abstracto de datos de las tablas

Índice

1. El tipo predefinido de las tablas ("arrays")
- 1.1. La clase de los índices de las tablas
- 1.2. El tipo predefinido de las tablas ("arrays")
2. Especificación del TAD de las tablas
- 2.1. Signatura del TAD de las tablas
- 2.2. Propiedades del TAD de las tablas
3. Implementaciones del TAD de las tablas
4. Comprobación de las implementaciones con QuickCheck
5. Material complementario
6. Bibliografía

1. El tipo predefinido de las tablas ("arrays")

1.1. La clase de los índices de las tablas

La clase de los índices de las tablas es Ix.
Ix se encuentra en la librería Data.Ix

Información de la clase Ix:

λ> :info Ix
class (Ord a) => Ix a where
  range :: (a, a) -> [a]
  index :: (a, a) -> a -> Int
  inRange :: (a, a) -> a -> Bool
  rangeSize :: (a, a) -> Int
instance Ix Ordering -- Defined in GHC.Arr
instance Ix Integer -- Defined in GHC.Arr
instance Ix Int -- Defined in GHC.Arr
instance Ix Char -- Defined in GHC.Arr
instance Ix Bool -- Defined in GHC.Arr
instance (Ix a, Ix b) => Ix (a, b)

(range (m,n)) es la lista de los índices desde m hasta n, en el orden del índice. Por ejemplo,

range (0,4)          ==  [0,1,2,3,4]
range (3,9)          ==  [3,4,5,6,7,8,9]
range ('b','f')      ==  "bcdef"
range ((0,0),(1,2))  ==  [(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)]

(index (m,n) i) es el ordinal del índice i dentro del rango (m,n). Por ejemplo,

index (3,9) 5              ==  2
index ('b','f') 'e'        ==  3
index ((0,0),(1,2)) (1,1)  ==  4

(inRange (m,n) i) se verifica si el índice i está dentro del rango limitado por m y n. Por ejemplo,

inRange (0,4) 3              ==  True
inRange (0,4) 7              ==  False
inRange ((0,0),(1,2)) (1,1)  ==  True
inRange ((0,0),(1,2)) (1,5)  ==  False

(rangeSize (m,n)) es el número de elementos en el rango limitado por m y n. Por ejemplo,

rangeSize (3,9)          ==  7
rangeSize ('b','f')      ==  5
rangeSize ((0,0),(1,2))  ==  6

1.2. El tipo predefinido de las tablas ("arrays")

La librería de las tablas es Data.Array.
Para usar las tablas hay que escribir al principio del fichero
```
import Data.Array
```
Al importar Data.Array también se importa Data.Ix.
(Array i v) es el tipo de las tablas con índice en i y valores en v.

1.2.1. Creación de tablas

(array (m,n) ivs) es la tabla de índices en el rango limitado por m y n definida por la lista de asociación ivs (cuyos elementos son pares de la forma (índice, valor)). Por ejemplo,
```
λ> array (1,3) [(3,6),(1,2),(2,4)]
array (1,3) [(1,2),(2,4),(3,6)]
λ> array (1,3) [(i,2*i) | i <- [1..3]]
array (1,3) [(1,2),(2,4),(3,6)]
```

1.2.2. Ejemplos de definiciones de tablas

(cuadrados n) es un vector de n+1 elementos tal que su elemento i-ésimo es i². Por ejemplo,

λ> cuadrados 5
array (0,5) [(0,0),(1,1),(2,4),(3,9),(4,16),(5,25)]

cuadrados :: Int -> Array Int Int
cuadrados n = array (0,n) [(i,i^2) | i <- [0..n]]

v es un vector con 4 elementos de tipo carácter. Por ejemplo,

v :: Array Integer Char
v = array (1,4) [(3,'c'),(2,'a'), (1,'f'), (4,'e')]

m es la matriz con 2 filas y 3 columnas tal que el elemento de la posición (i,j) es el producto de i por j.
```
m :: Array (Int, Int) Int
m = array ((1,1),(2,3)) [((i,j),i*j)) | i<-[1..2],j<-[1..3]]
```

Una tabla está indefinida si algún índice está fuera de rango.

λ> array (1,4) [(i , i*i) | i <- [1..4]]
array (1,4) [(1,1),(2,4),(3,9),(4,16)]
λ> array (1,4) [(i , i*i) | i <- [1..5]]
array *** Exception: Error in array index
λ> array (1,4) [(i , i*i) | i <- [1..3]]
array (1,4) [(1,1),(2,4),(3,9),(4,***
Exception: (Array.!): undefined array element

1.2.3. Descomposición de tablas

(t ! i) es el valor del índice i en la tabla t. Por ejemplo,

λ> v
array (1,4) [(1,'f'),(2,'a'),(3,'c'),(4,'e')]
λ> v!3
'c'
λ> m
array ((1,1),(2,3)) [((1,1),1),((1,2),2),((1,3),3),
                     ((2,1),2),((2,2),4),((2,3),6)]
λ> m!(2,3)
6

(bounds t) es el rango de la tabla t. Por ejemplo,
```
bounds m  ==  ((1,1),(2,3))
```
(indices t) es la lista de los índices de la tabla t. Por ejemplo,
```
indices m  ==  [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)]
```
(elems t) es la lista de los elementos de la tabla t. Por ejemplo,
```
elems m  ==  [1,2,3,2,4,6]
```

(assocs t) es la lista de asociaciones de la tabla t. Por ejemplo,

λ> assocs m
[((1,1),1),((1,2),2),((1,3),3),
 ((2,1),2),((2,2),4),((2,3),6)]

1.2.4. Modificación de tablas

(t // ivs) es la tabla t asignándole a los índices de la lista de asociación ivs sus correspondientes valores. Por ejemplo,

λ> m // [((1,1),4), ((2,2),8)]
array ((1,1),(2,3))
      [((1,1),4),((1,2),2),((1,3),3),
       ((2,1),2),((2,2),8),((2,3),6)]
λ> m
array ((1,1),(2,3))
      [((1,1),1),((1,2),2),((1,3),3),
       ((2,1),2),((2,2),4),((2,3),6)]

1.2.5. Definición de tabla por recursión

(fibs n) es el vector formado por los n primeros términos de la sucesión de Fibonacci. Por ejemplo,

λ> fibs 7
array (0,7) [(0,1),(1,1),(2,2),(3,3),
             (4,5),(5,8),(6,13),(7,21)]

fibs :: Int -> Array Int Int
fibs n = a where
  a = array (0,n)
            ([(0,1),(1,1)] ++
             [(i,a!(i-1)+a!(i-2)) | i <- [2..n]])

1.2.6. Otras funciones de creación de tablas

(listArray (m,n) vs) es la tabla cuyo rango es (m,n) y cuya lista de valores es vs. Por ejemplo,

λ> listArray (2,5) "Roma"
array (2,5) [(2,'R'),(3,'o'),(4,'m'),(5,'a')]
λ> listArray ((1,2),(2,4)) [5..12]
array ((1,2),(2,4)) [((1,2),5),((1,3),6),((1,4),7),
                     ((2,2),8),((2,3),9),((2,4),10)]

1.2.7. Construcción acumulativa de tablas

(accumArray f v (m,n) ivs) es la tabla de rango (m,n) tal que el valor del índice i se obtiene acumulando la aplicación de la función f al valor inicial v y a los valores de la lista de asociación ivs cuyo índice es i. Por ejemplo,
```
λ> accumArray (+) 0 (1,3) [(1,4),(2,5),(1,2)]
array (1,3) [(1,6),(2,5),(3,0)]
λ> accumArray (*) 1 (1,3) [(1,4),(2,5),(1,2)]
array (1,3) [(1,8),(2,5),(3,1)]
```

(histograma r is) es el vector formado contando cuantas veces aparecen los elementos del rango r en la lista de índices is. Por ejemplo,

λ> histograma (0,5) [3,1,4,1,5,4,2,7]
array (0,5) [(0,0),(1,2),(2,1),(3,1),(4,2),(5,1)]

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

2. Especificación del TAD de las tablas

2.1. Signatura del TAD de las tablas

Signatura:

tabla    :: Eq i => [(i,v)] -> Tabla i v
valor    :: Eq i => Tabla i v -> i -> v
modifica :: Eq i => (i,v) -> Tabla i v -> Tabla i v

Descripción de las operaciones:
- (tabla ivs) es la tabla correspondiente a la lista de asociación ivs (que es una lista de pares formados por los índices y los valores).
- (valor t i) es el valor del índice i en la tabla t.
- (modifica (i,v) t) es la tabla obtenida modificando en la tabla t el valor de i por v.

2.2. Propiedades del TAD de las tablas

modifica (i,v') (modifica (i,v) t) = modifica (i,v') t
Si i /= i', entonces ~modifica (i',v') (modifica (i,v) t) = modifica (i,v) (modifica (i',v') t) ~
valor (modifica (i,v) t) i = v
Si i /= i', entonces valor (modifica (i,v) (modifica (k',v') t)) i' = valor (modifica (k',v') t) i'

3. Implementaciones del TAD de las tablas

3.1. Las tablas como funciones

Cabecera del módulo:

module Tema_18.TablaConFunciones
  (Tabla,
   tabla,   -- Eq i => [(i,v)] -> Tabla i v
   valor,   -- Eq i => Tabla i v -> i -> v
   modifica -- Eq i => (i,v) -> Tabla i v -> Tabla i v
  ) where

Las tablas como funciones.
```
newtype Tabla i v = Tbl (i -> v)
```

Procedimiento de escritura.

instance Show (Tabla i v) where
  showsPrec _ _ cad = showString "<<Una tabla>>" cad

Ejemplo de tabla:

λ> f x = if x < 3 then x else 3-x
λ> t1 = tabla [(i,f i) | i <- [1..6] ]
λ> t1
<<Una tabla>>

(valor t i) es el valor del índice i en la tabla t. Por ejemplo,

λ> f x = if x < 3 then x else 3-x
λ> t1 = tabla [(i,f i) | i <- [1..6] ]
λ> valor t1 6
-3
λ> t2 = tabla [(4,89), (1,90), (2,67)]
λ> valor t2 2
67
λ> valor t2 5
*** Exception: fuera de rango

Su definición es

valor :: Eq i => Tabla i v -> i -> v
valor (Tbl f) i = f i

(modifica (i,v) t) es la tabla obtenida modificando en la tabla t el valor de i por v. Por ejemplo,

λ> f x = if x < 3 then x else 3-x
λ> t1 = tabla [(i,f i) | i <- [1..6] ]
λ> valor t1 6
-3
λ> valor (modifica (6,9) t1) 6
9

Su definición es

modifica :: Eq i => (i,v) -> Tabla i v -> Tabla i v
modifica (i,v) (Tbl f) = Tbl g
  where g j | j == i    = v
            | otherwise = f j

(tabla ivs) es la tabla correspondiente a la lista de asociación ivs (que es una lista de pares formados por los índices y los valores). Por ejemplo,

λ> tabla [(4,89), (1,90), (2,67)]
<<Una tabla>>

Su definición es

tabla :: Eq i => [(i,v)] -> Tabla i v
tabla = foldr modifica (Tbl (\_ -> error "fuera de rango"))

3.2. Las tablas como listas de asociación

Cabecera del módulo

module Tema_18.TablaConListasDeAsociacion
  (Tabla,
   tabla,   -- Eq i => [(i,v)] -> Tabla i v
   valor,   -- Eq i => Tabla i v -> i -> v
   modifica -- Eq i => (i,v) -> Tabla i v -> Tabla i v
  ) where

Las tablas como listas de asociación.

newtype Tabla i v = Tbl [(i,v)]
  deriving Show

Ejemplos definición de tablas:

λ> f x = if x < 3 then x else 3-x
λ> t1 = tabla [(i,f i) | i <- [1..6]]
λ> t1
Tbl [(1,1),(2,2),(3,0),(4,-1),(5,-2),(6,-3)]
λ> t2 = tabla [(4,89), (1,90), (2,67)]
λ> t2
Tbl [(4,89),(1,90),(2,67)]

(tabla ivs) es la tabla correspondiente a la lista de asociación ivs (que es una lista de pares formados por los índices y los valores). Por ejemplo,
```
λ> tabla [(4,89),(1,90),(2,67)]
Tbl [(4,89),(1,90),(2,67)]
```
Su definición es
```
tabla :: Eq i => [(i,v)] -> Tabla i v
tabla ivs = Tbl ivs
```

(valor t i) es el valor del índice i en la tabla t. Por ejemplo,

λ> f x = if x < 3 then x else 3-x
λ> t1 = tabla [(i,f i) | i <- [1..6]]
λ> valor t1 6
-3
λ> t2 = tabla [(4,89), (1,90), (2,67)]
λ> valor t2 2
67
λ> valor t2 5
*** Exception: fuera de rango

Su definición es

valor :: Eq i => Tabla i v -> i -> v
valor (Tbl []) i        = error "fuera de rango"
valor (Tbl ((j,v):r)) i | i == j    = v
                        | otherwise = valor (Tbl r) i

(modifica (i,x) t) es la tabla obtenida modificando en la tabla t el valor de i por x. Por ejemplo,

λ> f x = if x < 3 then x else 3-x
λ> t1 = tabla [(i,f i) | i <- [1..6]]
λ> valor t1 6
-3
λ> valor (modifica (6,9) t1) 6
9

Su definición es

modifica :: Eq i => (i,v) -> Tabla i v -> Tabla i v
modifica p (Tbl [])                 = (Tbl [p])
modifica p'@(i,_) (Tbl (p@(j,_):r)) | i == j     = Tbl (p':r)
                                    | otherwise  = Tbl (p:r')
  where Tbl r' = modifica p' (Tbl r)

Las tablas son comparables por igualdad. Por ejemplo,

λ> f x = if x < 3 then x else 3-x
λ> t1 = tabla [(i,f i) | i <- [1..6]]
λ> t2 = tabla [(4,89), (1,90), (2,67)]
λ> t1 == t2
False
λ> t3 = tabla [(1,1),(3,0),(2,2),(4,-1),(5,-2),(6,-3)]
λ> t1 == t3
True

Su definición es

instance (Eq i, Eq v) => Eq (Tabla i v) where
  (Tbl [])        == (Tbl []) = True
  (Tbl ((i,v):t)) == Tbl t'   = elem (i,v) t' &&
                                Tbl t == Tbl [p | p <- t', p /= (i,v)]
  _               == _        = False

3.3. Las tablas como matrices

Cabecera del módulo:

module Tema_18.TablaConMatrices
  (Tabla,
   tabla,     -- Eq i => [(i,v)] -> Tabla i v
   valor,     -- Eq i => Tabla i v -> i -> v
   modifica,  -- Eq i => (i,v) -> Tabla i v -> Tabla i v
   tieneValor -- Ix i => Tabla i v -> i -> Bool
  ) where

Importación de la librería auxiliar:

import Data.Array (Array, Ix, array, (//), (!), indices, bounds, inRange)

Las tablas como matrices.

newtype Tabla i v = Tbl (Array i v)
  deriving (Show, Eq)

Ejemplos de definición de tablas:

λ> f x = if x < 3 then x else 3-x
λ> t1 = tabla [(i,f i) | i <- [1..6]]
λ> t1
Tbl (array (1,6) [(1,1),(2,2),(3,0),(4,-1),(5,-2),(6,-3)])
λ> t2 = tabla [(1,5),(2,4),(3,7)]
λ> t2

(tabla ivs) es la tabla correspondiente a la lista de asociación ivs (que es una lista de pares formados por los índices y los valores). Por ejemplo,

λ> tabla [(1,5),(3,7),(2,4)]
Tbl (array (1,3) [(1,5),(2,4),(3,7)])

Su definición es

tabla :: Ix i => [(i,v)] -> Tabla i v
tabla ivs = Tbl (array (m,n) ivs)
  where is = [i | (i,_) <- ivs]
        m  = minimum is
        n  = maximum is

(valor t i) es el valor del índice i en la tabla t. Por ejemplo,

λ> f x = if x < 3 then x else 3-x
λ> t1 = tabla [(i,f i) | i <- [1..6]]
λ> valor t1 6
-3
λ> valor t2 2
4
λ> valor t2 5
*** Exception: Ix{Integer}.index: Index (5) out of range ((1,3))

Su definición es

valor :: Ix i => Tabla i v -> i -> v
valor (Tbl t) i = t ! i

(modifica (i,x) t) es la tabla obtenida modificando en la tabla t el valor de i por x. Por ejemplo,

λ> f x = if x < 3 then x else 3-x
λ> t1 = tabla [(i,f i) | i <- [1..6]]
λ> valor t1 6
-3
λ> valor (modifica (6,9) t1) 6
9

Su definición es

modifica :: Ix i => (i,v) -> Tabla i v -> Tabla i v
modifica (i,v) (Tbl t) | i `elem` indices t = Tbl (t // [(i,v)])
                       | otherwise          = Tbl t

(cotas t) son las cotas de la tabla t. Por ejemplo,

λ> t2 = tabla [(4,89), (1,90), (2,67)]
λ> cotas t2
(1,3)

Su definición es

cotas :: Ix i => Tabla i v -> (i,i)
cotas (Tbl t) = bounds t

(tieneValor t x) se verifica si x es una clave de la tabla t. Por ejemplo,

λ> t2 = tabla [(4,89), (1,90), (2,67)]
λ> tieneValor t2 3
True
λ> tieneValor t2 4
False

Su definición es

tieneValor :: Ix i => Tabla i v -> i -> Bool
tieneValor t = inRange (cotas t)

4. Comprobación de las implementaciones con QuickCheck

4.1. Pragma y librerías auxiliares

Al principio del fichero se añade

{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE FlexibleInstances #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

Importación de la implementación de tablas que se desea verificar.

import Tema_18.TablaConListasDeAsociacion
-- import Tema_18.TablaConMatrices
-- import I1M.Tabla

Importación de la librería de comprobación
```
import Test.QuickCheck
```

4.2. Generador de tablas

genTabla es un generador de tablas. Por ejemplo,

λ> sample genTabla
Tbl [(1,0)]
Tbl [(1,-1)]
Tbl [(1,0),(2,-1),(3,1),(4,1),(5,0)]

genTabla :: Gen (Tabla Int Int)
genTabla = do
  x <- arbitrary
  xs <- listOf arbitrary
  return (tabla (zip [1..] (x:xs)))

instance Arbitrary (Tabla Int Int) where
  arbitrary = genTabla

4.3. Especificación de las propiedades de las tablas

Al modificar una tabla dos veces con la misma clave se obtiene el mismos resultado que modificarla una vez con el último valor.

prop_modifica_modifica_1 :: Int -> Int -> Int -> Tabla Int Int -> Bool
prop_modifica_modifica_1 i v v' t =
  modifica (i,v') (modifica (i,v) t)
  == modifica (i,v') t

Al modificar una tabla con dos pares con claves distintas no importa el orden en que se añadan los pares.

prop_modifica_modifica_2 :: Int -> Int -> Int -> Int -> Tabla Int Int -> Property
prop_modifica_modifica_2 i i' v v' t =
  i /= i' ==>
  modifica (i',v') (modifica (i,v) t)
  == modifica (i,v) (modifica (i',v') t)

El valor de la clave i en la tabla obtenida añadiéndole el par (i,v) a la tabla t es v.

prop_valor_modifica_1 :: Int -> Int -> Tabla Int Int -> Bool
prop_valor_modifica_1 i v t =
  valor (modifica (i,v) t) i == v

Sean i e j dos claves distintas. El valor de la clave j en la tabla obtenida añadiéndole el par (i,v) a la tabla t' (que contiene la clave j) es el valor de j en t'.

prop_valor_modifica_2 :: Int -> Int -> Int -> Int -> Tabla Int Int -> Property
prop_valor_modifica_2 i v j v' t =
  i /= j ==>
  valor (modifica (i,v) t') j == valor t' j
  where t' = modifica (j,v') t

4.4. Comprobación de las propiedades

Para verificar todas las propiedades se escribe

return []

verificaTablas :: IO Bool
verificaTablas = $quickCheckAll

Comprobación de las propiedades de las tablas

λ> verificaTablas
=== prop_modifica_modifica_1 from TablaPropiedades.hs:54 ===
+++ OK, passed 100 tests.

=== prop_modifica_modifica_2 from TablaPropiedades.hs:65 ===
+++ OK, passed 100 tests; 14 discarded.

=== prop_valor_modifica_1 from TablaPropiedades.hs:80 ===
+++ OK, passed 100 tests; 1 discarded.

=== prop_valor_modifica_2 from TablaPropiedades.hs:92 ===
+++ OK, passed 100 tests; 14 discarded.

True

5. Material complementario

El código del tema se encuentra en los siguientes enlaces

Este tema también se encuentra en los siguientes formatos:

Como transparencias en PDF.
Como libro interactivo en IHaskell sobre Jupyter.

6. Bibliografía

F. Rabhi y G. Lapalme. Algorithms: A functional programming approach.
- Cap. 5.6: Tables