Tema 18: El TAD de las tablas

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

1.1 La clase de los índices de las tablas

ghci> :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 (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 (3,9) 5              ==  2
index ('b','f') 'e'        ==  3
index ((0,0),(1,2)) (1,1)  ==  4
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 (3,9)          ==  7
rangeSize ('b','f')      ==  5
rangeSize ((0,0),(1,2))  ==  6

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

import Data.Array

Creación de tablas

ghci> array (1,3) [(3,6),(1,2),(2,4)]
array (1,3) [(1,2),(2,4),(3,6)]
ghci> array (1,3) [(i,2*i) | i <- [1..3]]
array (1,3) [(1,2),(2,4),(3,6)]

Ejemplos de definiciones de tablas

ghci> 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 :: Array Integer Char
v = array (1,4) [(3,'c'),(2,'a'), (1,'f'), (4,'e')]
m :: Array (Int, Int) Int
m = array ((1,1),(2,3)) [((i,j),i*j)) | i<-[1..2],j<-[1..3]]
ghci> array (1,4) [(i , i*i) | i <- [1..4]]
array (1,4) [(1,1),(2,4),(3,9),(4,16)]
ghci> array (1,4) [(i , i*i) | i <- [1..5]]
array *** Exception: Error in array index
ghci> array (1,4) [(i , i*i) | i <- [1..3]]
array (1,4) [(1,1),(2,4),(3,9),(4,*** 
Exception: (Array.!): undefined array element

Descomposición de tablas

ghci> v
array (1,4) [(1,'f'),(2,'a'),(3,'c'),(4,'e')]
ghci> v!3
'c'
ghci> m
array ((1,1),(2,3)) [((1,1),1),((1,2),2),((1,3),3),
                     ((2,1),2),((2,2),4),((2,3),6)]
ghci> m!(2,3)
6
bounds m  ==  ((1,1),(2,3))
indices m  ==  [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)]
elems m  ==  [1,2,3,2,4,6]
ghci> assocs m
[((1,1),1),((1,2),2),((1,3),3),
 ((2,1),2),((2,2),4),((2,3),6)]

Modificación de tablas

ghci> 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)]
ghci> m
array ((1,1),(2,3)) 
      [((1,1),1),((1,2),2),((1,3),3),
       ((2,1),2),((2,2),4),((2,3),6)]

Definición de tabla por recursión

ghci> 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]])

Otras funciones de creación de tablas

ghci> listArray (2,5) "Roma"
array (2,5) [(2,'R'),(3,'o'),(4,'m'),(5,'a')]
ghci> 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)]

Construcción acumulativa de tablas

ghci> accumArray (+) 0 (1,3) [(1,4),(2,5),(1,2)]
array (1,3) [(1,6),(2,5),(3,0)]
ghci> accumArray (*) 1 (1,3) [(1,4),(2,5),(1,2)]
array (1,3) [(1,8),(2,5),(3,1)]
ghci> 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

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

2.2 Propiedades del TAD de las tablas

3 Implementaciones del TAD de las tablas

3.1 Las tablas como funciones

module 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
newtype Tabla i v = Tbl (i -> v)
instance Show (Tabla i v) where
    showsPrec _ _ cad = showString "<<Una tabla>>" cad
t1 = tabla [(i,f i) | i <- [1..6] ] 
     where f x | x < 3     = x
               | otherwise = 3-x

t2 = tabla [(4,89), (1,90), (2,67)]
valor t1 6  ==  -3
valor t2 2  ==  67
valor t2 5  ==  *** Exception: fuera de rango
valor :: Eq i => Tabla i v -> i -> v
valor (Tbl f) i = f i
valor (modifica (6,9) t1) 6  ==  9
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
ghci> tabla [(4,89), (1,90), (2,67)]
<<Una tabla>>
tabla :: Eq i => [(i,v)] -> Tabla i v
tabla ivs = 
    foldr modifica 
          (Tbl (\_ -> error "fuera de rango"))
          ivs

3.2 Las tablas como listas de asociación

module 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
newtype Tabla i v = Tbl [(i,v)]
    deriving Show
t1 = tabla [(i,f i) | i <- [1..6] ] 
     where f x | x < 3     = x
               | otherwise = 3-x

t2 = tabla [(4,89), (1,90), (2,67)]
ghci> t1
Tbl [(1,1),(2,2),(3,0),(4,-1),(5,-2),(6,-3)]

ghci> t2
Tbl [(4,89),(1,90),(2,67)]
ghci> tabla [(4,89),(1,90),(2,67)]
Tbl [(4,89),(1,90),(2,67)]
tabla :: Eq i => [(i,v)] -> Tabla i v
tabla ivs = Tbl ivs
valor t1 6  ==  -3
valor t2 2  ==  67
valor t2 5  ==  *** Exception: fuera de rango
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 
valor t1 6                   ==  -3
valor (modifica (6,9) t1) 6  ==  9
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)

3.3 Las tablas como matrices

module 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
import Data.Array
newtype Tabla i v = Tbl (Array i v) deriving (Show, Eq)
t1 = tabla [(i,f i) | i <- [1..6] ] 
     where f x | x < 3     = x
               | otherwise = 3-x

t2 = tabla [(1,5),(2,4),(3,7)]
ghci> t1
Tbl (array (1,6) [(1,1),(2,2),(3,0),
                  (4,-1),(5,-2),(6,-3)])

ghci> t2
Tbl (array (1,3) [(1,5),(2,4),(3,7)])
ghci> tabla [(1,5),(3,7),(2,4)]
Tbl (array (1,3) [(1,5),(2,4),(3,7)])
tabla :: Ix i => [(i,v)] -> Tabla i v
tabla ivs = Tbl (array (m,n) ivs)
    where indices = [i | (i,_) <- ivs]
          m       = minimum indices
          n       = maximum indices
valor t1 6  ==  -3
valor t2 2  ==  67
valor t2 5  ==  *** Exception: fuera de rango
valor :: Ix i => Tabla i v -> i -> v
valor (Tbl t) i = t ! i
valor t1 6                   ==  -3
valor (modifica (6,9) t1) 6  ==  9
modifica :: Ix i => (i,v) -> Tabla i v -> Tabla i v
modifica p (Tbl t) = Tbl (t // [p])
t2        ==  Tbl (array (1,3) [(1,5),(2,4),(3,7)])
cotas t2  ==  (1,3)
cotas :: Ix i => Tabla i v -> (i,i)
cotas (Tbl t) = bounds t
tieneValor t2 3  ==  True
tieneValor t2 4  ==  False
tieneValor :: Ix i => Tabla i v -> i -> Bool
tieneValor t = inRange (cotas t)

4 Comprobación de las implementaciones con QuickCheck

4.1 Librerías auxiliares

import TablaConListasDeAsociacion
import Test.QuickCheck
import Test.Framework
import Test.Framework.Providers.QuickCheck2

4.2 Generador de tablas

ghci> 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

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 
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) 
prop_valor_modifica_1 :: Int -> Int 
                         -> Tabla Int Int -> Bool
prop_valor_modifica_1 i v t =
    valor (modifica (i,v) t) i == v
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

Definición del procedimiento de comprobación

compruebaPropiedades = 
    defaultMain 
        [testGroup "Propiedades del TAD tabla"
          [testProperty "P1" prop_modifica_modifica_1,
           testProperty "P2" prop_modifica_modifica_2,
           testProperty "P3" prop_valor_modifica_1,
           testProperty "P4" prop_valor_modifica_2]]

Comprobación de las propiedades de las tablas

Propiedades del TAD tabla:
  P1: [OK, passed 100 tests]
  P2: [OK, passed 100 tests]
  P3: [OK, passed 100 tests]
  P4: [OK, passed 100 tests]

         Properties  Total      
 Passed  4           4          
 Failed  0           0          
 Total   4           4  


Universidad de Sevilla

José A. Alonso Jiménez
Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e I.A.
Universidad de Sevilla