I1M2011: El TAD (tipo abstracto de datos) de las tablas en Haskell

En la clase de hoy de Informática de 1º del Grado en Matemáticas se ha estudiado el TAD (tipo abstracto de datos) de las tablas y 3 implementaciones en Haskell: como funciones, como listas de asociación y como matrices.

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 de la clase ha sido 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 asociació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:

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

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

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

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

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

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

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)

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

{-# 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.

{-# 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.

Las transparencias usadas en la clase son las páginas 19-39 del tema 18:

La signatura del TAD de las tablas

Propiedades del TAD de las tablas

Implementación de las tablas mediante funciones

Implementación de las tablas mediante listas de asociación

Implementación de las tablas mediante matrices

Propiedades de las tablas

Se puede imprimir o compartir con