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

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

Una tabla es una colección de elementos (valores) a los que se accede mediante sus índice.

Se ha seguido el mismo patrón que en los anteriores tipos de datos:

elección de las operaciones básicas,
especificación de sus propiedades,
implementación en Haskell mediante funciones,
implementación en Haskell mediante listas de asociación,
implementación en Haskell mediante matrices,
análisis de la complejidad de las definiciones de las operaciones básicas en las tres implementaciones y
verificación con QuickCheck de sus propiedades características.

Las transparencias usadas en la clase son las del tema 18.

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 p1@(i,_) (Tbl (p@(j,_):r))
     | i == j     = Tbl (p1:r)
     | otherwise  = Tbl (p:r1)
     where Tbl r1 = modifica p1 (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 t1   = elem (i,v) t1 && 
                                  Tbl t == Tbl [p | p <- t1, 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 p1@(i,_) (Tbl (p@(j,_):r))

| i == j = Tbl (p1:r)

| otherwise = Tbl (p:r1)

where Tbl r1 = modifica p1 (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 t1 = elem (i,v) t1 &&

Tbl t == Tbl [p | p <- t1, 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 v1 t =
    modifica (i,v1) (modifica (i,v) t) 
    == modifica (i,v1) 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 i1 v v1 t =
    i /= i1 ==>
    modifica (i1,v1) (modifica (i,v) t) 
    == modifica (i,v) (modifica (i1,v1) 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 i1 dos claves distintas. El valor de la clave i1
-- en la tabla obtenida añadiéndole el par (i,v) a la tabla t1 (que
-- contiene la clave i1) es el valor de i1 en t1. 
prop_valor_modifica_2 :: Int -> Int -> Int -> Int -> Tabla Int Int 
                            -> Property
prop_valor_modifica_2 i v i1 v1 t =
    i /= i1 ==>
    valor (modifica (i,v) t1) i1 == valor t1 i1
    where t1 = modifica (i1,v1) 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 v1 t =

modifica (i,v1) (modifica (i,v) t)

== modifica (i,v1) 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 i1 v v1 t =

i /= i1 ==>

modifica (i1,v1) (modifica (i,v) t)

== modifica (i,v) (modifica (i1,v1) 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 i1 dos claves distintas. El valor de la clave i1

-- en la tabla obtenida añadiéndole el par (i,v) a la tabla t1 (que

-- contiene la clave i1) es el valor de i1 en t1.

prop_valor_modifica_2 :: Int -> Int -> Int -> Int -> Tabla Int Int

-> Property

prop_valor_modifica_2 i v i1 v1 t =

i /= i1 ==>

valor (modifica (i,v) t1) i1 == valor t1 i1

where t1 = modifica (i1,v1) t

-- Comprobación.

-- ghci> quickCheck prop_valor_modifica_2

-- +++ OK, passed 100 tests.

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