El tipo abstracto de datos de las tablas en Haskell
En este artículo continúo la serie dedicada a los tipos de datos abstractos (TAD) en Haskell presentando el TAD de las tablas.
Una tabla (array en inglés y tableau en francés) es una colección de elementos (valores) a los que se accede mediante sus índices.
El contenido del resto del artículo es el siguiente:
- la signatura del TAD de las tablas;
- las propiedades del TAD de las tablas;
- las implementaciones, en Haskell, de las tablas mediante funciones, listas de asociacón y matrices y
- la comprobación con QuickCheck de sus propiedades.
La signatura del TAD de las tablas
Las signatura de las operaciones del TAD de las tablas son las siguientes:
1 2 3 |
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 |
con el siguiente significado
- (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.
Propiedades del TAD de las tablas
Las propiedades son las siguientes:
- 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'
Implementación de las tablas mediante funciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
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 -- 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 -- Ejemplos de tablas: -- ghci> t1 -- <<Una tabla>> 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 t i) es el valor del índice i en la tabla t. Por ejemplo, -- 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 -- (modifica (i,v) t) es la tabla obtenida modificando en la tabla t el -- valor de i por v. Por ejemplo, -- valor t1 6 == -3 -- 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 -- (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, -- 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 |
Implementación de las tablas mediante listas de asociación
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
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 -- Las tablas como listas de asociación. newtype Tabla i v = Tbl [(i,v)] deriving Show -- Ejemplos de tabla: -- ghci> t1 -- Tbl [(1,1),(2,2),(3,0),(4,-1),(5,-2),(6,-3)] -- ghci> t2 -- Tbl [(4,89),(1,90),(2,67)] 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)] -- (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)] 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, -- 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 -- (modifica (i,x) t) es la tabla obtenida modificando en la tabla t el -- valor de i por x. Por ejemplo, -- 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) -- Nota sobre la eficiencia: -- * modifica y valor son de O(n) pasos en el peor caso, -- donde n es el número de entradas en la tabla. -- * modifica requiere O(n) celdas en el peor caso. -- --------------------------------------------------------------------- -- Igualdad -- -- --------------------------------------------------------------------- --- Las tablas son comparables por igualdad. 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)] |
Implementación de las tablas mediante matrices
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
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 (Array, Ix, array, (//), (!), bounds, inRange) -- Las tablas como matrices. newtype Tabla i v = Tbl (Array i v) deriving (Show, Eq) -- Ejemplos de tablas: -- 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)]) 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)] -- (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, -- 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 t i) es el valor del índice i en la tabla t. Por ejemplo, -- valor t1 6 == -3 -- valor t2 2 == 4 -- valor t2 5 == *** Exception: Index (5) out of range ((1,3)) 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, -- 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]) -- (cotas t) son las cotas de la tabla t. Por ejemplo, -- 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 t x) se verifica si x es una clave de la tabla t. Por ejemplo, -- tieneValor t2 3 == True -- tieneValor t2 4 == False tieneValor :: Ix i => Tabla i v -> i -> Bool tieneValor t = inRange (cotas t) |
Propiedades de las tablas
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
{-# LANGUAGE FlexibleInstances #-} -- Nota: Hay que elegir una implementación del TAD tabla: import TablaConListasDeAsociacion -- import TablaConMatrices (Pendiente de depurar) import Test.QuickCheck -- --------------------------------------------------------------------- -- Generadores de tablas -- -- --------------------------------------------------------------------- -- genTabla es un generador de tablas. Por ejemplo, -- ghci> sample genTabla -- Tbl [(1,0)] -- Tbl [(1,-1)] -- Tbl [(1,0),(2,-1),(3,1),(4,1),(5,0)] -- Tbl [(1,1),(2,-1),(3,-1),(4,3)] -- Tbl [(1,3),(2,-5),(3,-7),(4,-2),(5,-8)] -- Tbl [(1,16),(2,-6),(3,-13),(4,-7),(5,2),(6,11)] -- Tbl [(1,-4),(2,-1),(3,3),(4,5)] -- Tbl [(1,-8),(2,16),(3,32)] genTabla :: Gen (Tabla Int Int) genTabla = do x <- arbitrary xs <- listOf arbitrary return (tabla (zip [1..] (x:xs))) -- Las tablas son concreciones de los arbitrarios. instance Arbitrary (Tabla Int Int) where arbitrary = genTabla -- --------------------------------------------------------------------- -- Propiedades -- -- --------------------------------------------------------------------- -- Propiedades de modifica -- ----------------------- -- Propiedad. 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 -- Comprobación. -- ghci> quickCheck prop_modifica_modifica_1 -- +++ OK, passed 100 tests. -- Propiedad. 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) -- Comprobación. -- ghci> quickCheck prop_modifica_modifica_2 -- +++ OK, passed 100 tests. -- Propiedades de valor -- -------------------- -- Propiedad. 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 -- Comprobación. -- ghci> quickCheck prop_valor_modifica_1 -- +++ OK, passed 100 tests. -- Propiedad. Sean i y i' dos claves distintas. El valor de la clave i' -- en la tabla obtenida añadiéndole el par (i,v) a la tabla t' (que -- contiene la clave i') es el valor de i' en t'. prop_valor_modifica_2 :: Int -> Int -> Int -> Int -> Tabla Int Int -> Property prop_valor_modifica_2 i v i' v' t = i /= i' ==> valor (modifica (i,v) t') i' == valor t' i' where t' = modifica (i',v') t -- Comprobación. -- ghci> quickCheck prop_valor_modifica_2 -- +++ OK, passed 100 tests. |
El objetivo de la serie es la elaboración de los temas de TAD del curso de Informática del Grado en Matemáticas.