PFH: Ejercicios sobre tablas y diccionarios en Haskell

He añadido a la colección de Ejercicios de programación funcional con Haskell dos nuevas relaciones:

En la primera, se define el tipo abstracto de dato (TAD) de las tablas como lista de asociación de claves y valores. Los procedimientos del TAD son

   vacia         :: Tabla k v
   inserta       :: k -> v -> Tabla k v -> Tabla k v
   borra         :: Eq k => k -> Tabla k v -> Tabla k v
   busca         :: Eq k => k -> Tabla k v -> Maybe v
   aplicaValores :: (v1 -> v2) -> Tabla k v1 -> Tabla k v2
   aplicaClaves  :: (k1 -> k2) -> Tabla k1 v -> Tabla k2 v
   ajusta        :: Eq k => (Maybe v -> Maybe v) -> k -> Tabla k v -> Tabla k v

vacia :: Tabla k v

inserta :: k -> v -> Tabla k v -> Tabla k v

borra :: Eq k => k -> Tabla k v -> Tabla k v

busca :: Eq k => k -> Tabla k v -> Maybe v

aplicaValores :: (v1 -> v2) -> Tabla k v1 -> Tabla k v2

aplicaClaves :: (k1 -> k2) -> Tabla k1 v -> Tabla k2 v

ajusta :: Eq k => (Maybe v -> Maybe v) -> k -> Tabla k v -> Tabla k v

En la segunda, se comprueba con QuickCheck cómo las anteriores funciones de la tablas se corresponden con funciones de diccionarios de la libreria Data.Map.

El contenido de las relaciones es el siguiente

El tipo abstracto de las tablas

module Tablas
  ( Tabla (..)
  , vacia, inserta, borra, busca, aplicaValores, aplicaClaves, ajusta
  )
where

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir el tipo (Tabla k v) de las tablas con claves de
-- tipo k y valores de tipo v.
-- ---------------------------------------------------------------------

newtype Tabla k v = Tabla [(k, v)]
  deriving (Eq, Show)

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función
--    vacia :: Tabla k v
-- tal que vacia es la tabla vacía.
-- ---------------------------------------------------------------------

vacia :: Tabla k v
vacia = Tabla []

-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir la función
--    inserta :: k -> v -> Tabla k v -> Tabla k v
-- tal que
--    inserta 2 'a' vacia                 == Tabla [(2,'a')]
--    inserta 4 'd' (inserta 2 'a' vacia) == Tabla [(4,'d'),(2,'a')]
-- ---------------------------------------------------------------------

inserta :: k -> v -> Tabla k v -> Tabla k v
inserta k v (Tabla kvs) = Tabla ((k, v) : kvs)

-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la función
--    borra :: Eq k => k -> Tabla k v -> Tabla k v
-- tal que (borra k t) es la tabla obtenida borrando los pares de t
-- cuya clave es k. Por ejemplo,
--    λ> borra 2 (Tabla [(2,'a'),(3,'b'),(2,'a')])
--    Tabla [(3,'b')]
-- ---------------------------------------------------------------------

borra :: Eq k => k -> Tabla k v -> Tabla k v
borra k (Tabla kvs) = Tabla $ filter (\(k', _) -> k' /= k) kvs

-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir la función
--    busca :: Eq k => k -> Tabla k v -> Maybe v
-- tal que (busca k t) es el valor de la clave k en la tabla t. Por ejemplo,
--    busca 2 (Tabla [(2,'a'),(3,'b'),(2,'d')])  ==  Just 'a'
--    busca 4 (Tabla [(2,'a'),(3,'b'),(2,'d')])  ==  Nothing
-- ---------------------------------------------------------------------

busca :: Eq k => k -> Tabla k v -> Maybe v
busca _ (Tabla [])              = Nothing
busca k (Tabla ((k', v) : kvs))
  | k == k'                      = Just v
  | otherwise                    = busca k (Tabla kvs)

-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir la función
--    aplicaValores :: (v1 -> v2) -> Tabla k v1 -> Tabla k v2
-- tal que (aplicaValores f t) es la tabla obtenida aplicando la función f a
-- los valores de t. Por ejemplo,
--    λ> aplicaValores (+2) (Tabla [('a',5),('b',7),('c',4)])
--    Tabla [('a',7),('b',9),('c',6)]
-- ---------------------------------------------------------------------

aplicaValores :: (v1 -> v2) -> Tabla k v1 -> Tabla k v2
aplicaValores _ (Tabla [])             = vacia
aplicaValores f (Tabla ((k, v) : kvs)) = inserta k (f v) (aplicaValores f (Tabla kvs))

-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir la función
--    aplicaClaves :: (k1 -> k2) -> Tabla k1 v -> Tabla k2 v
-- tal que (aplicaClaves f t) es la tabla obtenida aplicando la función f a
-- las claves de t. Por ejemplo,
--    λ> aplicaClaves (+2) (Tabla [(2,'a'),(3,'b'),(2,'d')])
--    Tabla [(4,'a'),(5,'b'),(4,'d')]
-- ---------------------------------------------------------------------

aplicaClaves :: (k1 -> k2) -> Tabla k1 v -> Tabla k2 v
aplicaClaves _ (Tabla [])             = vacia
aplicaClaves f (Tabla ((k, v) : kvs)) = inserta (f k) v (aplicaClaves f (Tabla kvs))

-- ---------------------------------------------------------------------
-- Ejercicio 8. Definir la función
--    ajusta :: Eq k => (Maybe v -> Maybe v) -> k -> Tabla k v -> Tabla k v
-- tal que (ajusta f k t) es el ajuste de la tabla t de acuerdo a las
-- siguientes reglas:
-- + Si `f k` es `Nothing` y `k` es una clave de t, borra el par con
--   clave `k`.
-- + Si `f k` es `Nothing` y `k` no es una clave de t, no hace nada.
-- + Si `f k` es `Just v` y `k` es una clave de t, cambia el valor de
--   `k` a `v`.
-- + Si `f k` es `Just v` y `k` no es una clave de t, añade el par `(h, v)`.
-- Por ejemplo,
--    λ> ajusta (\_ -> Nothing) 4 (Tabla [(3,2),(4,5)])
--    Tabla [(3,2)]
--    λ> ajusta (\_ -> Nothing) 7 (Tabla [(3,2),(4,5)])
--    Tabla [(3,2),(4,5)]
--    λ> ajusta (\_ -> Just 9) 4 (Tabla [(3,2),(4,5)])
--    Tabla [(3,2),(4,9)]
--    λ> ajusta (\_ -> Just 9) 7 (Tabla [(3,2),(4,5)])
--    Tabla [(3,2),(4,5),(7,9)]
--    λ> ajusta ((+ 2) <$>) 4 (Tabla [(3,2),(4,5)])
--    Tabla [(3,2),(4,7)]
--    λ> ajusta ((+ 2) <$>) 7 (Tabla [(3,2),(4,5)])
--    Tabla [(3,2),(4,5)]
--    λ> ajusta (\_ -> Nothing) 3 (Tabla [])
--    Tabla []
--    λ> ajusta (\_ -> Just 7) 3 (Tabla [])
--    Tabla [(3,7)]
--    λ> ajusta (\_ -> Nothing) 3 (Tabla [(3,1),(2,5),(3,7),(4,3)])
--    Tabla [(2,5),(4,3)]
--    λ> ajusta ((+ 2) <$>) 3 (Tabla [(3,1),(2,5),(3,7),(4,3)])
--    Tabla [(3,3),(2,5),(3,7),(4,3)]
--    λ> ajusta (\_ -> Nothing) 3 (Tabla [(2,5),(3,7),(4,3)])
--    Tabla [(2,5),(4,3)]
--    λ> ajusta ((+ 2) <$>) 3 (Tabla [(2,5),(3,7),(4,3)])
--    Tabla [(2,5),(3,9),(4,3)]
-- ---------------------------------------------------------------------

ajusta :: Eq k => (Maybe v -> Maybe v) -> k -> Tabla k v -> Tabla k v
ajusta f k (Tabla []) =
  case f Nothing of
    Nothing -> Tabla []
    Just v  -> Tabla [(k, v)]
ajusta f k (Tabla ((k', v) : kvs))
  | k == k' =
      case f (Just v) of
        Nothing -> Tabla $ filter (\(k'', _) -> k'' /= k) kvs
        Just v' -> Tabla $ (k, v') : kvs
  | otherwise =
      case ajusta f k (Tabla kvs) of
        Tabla kvs' -> Tabla $ (k', v) : kvs'

-- ---------------------------------------------------------------------
-- § Referencias                                                      --
-- ---------------------------------------------------------------------

-- Esta relación de ejercicio es una adaptación de
-- "Tables.hs" https://bit.ly/3Cli8vV de Lars Brünjes.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

module Tablas

( Tabla (..)

, vacia, inserta, borra, busca, aplicaValores, aplicaClaves, ajusta

)

where

-- ---------------------------------------------------------------------

-- Ejercicio 1. Definir el tipo (Tabla k v) de las tablas con claves de

-- tipo k y valores de tipo v.

-- ---------------------------------------------------------------------

newtype Tabla k v = Tabla [(k, v)]

deriving (Eq, Show)

-- ---------------------------------------------------------------------

-- Ejercicio 2. Definir la función

-- vacia :: Tabla k v

-- tal que vacia es la tabla vacía.

-- ---------------------------------------------------------------------

vacia :: Tabla k v

vacia = Tabla []

-- ---------------------------------------------------------------------

-- Ejercicio 3. Definir la función

-- inserta :: k -> v -> Tabla k v -> Tabla k v

-- tal que

-- inserta 2 'a' vacia == Tabla [(2,'a')]

-- inserta 4 'd' (inserta 2 'a' vacia) == Tabla [(4,'d'),(2,'a')]

-- ---------------------------------------------------------------------

inserta :: k -> v -> Tabla k v -> Tabla k v

inserta k v (Tabla kvs) = Tabla ((k, v) : kvs)

-- ---------------------------------------------------------------------

-- Ejercicio 4. Definir la función

-- borra :: Eq k => k -> Tabla k v -> Tabla k v

-- tal que (borra k t) es la tabla obtenida borrando los pares de t

-- cuya clave es k. Por ejemplo,

-- λ> borra 2 (Tabla [(2,'a'),(3,'b'),(2,'a')])

-- Tabla [(3,'b')]

-- ---------------------------------------------------------------------

borra :: Eq k => k -> Tabla k v -> Tabla k v

borra k (Tabla kvs) = Tabla $ filter (\(k', _) -> k' /= k) kvs

-- ---------------------------------------------------------------------

-- Ejercicio 5. Definir la función

-- busca :: Eq k => k -> Tabla k v -> Maybe v

-- tal que (busca k t) es el valor de la clave k en la tabla t. Por ejemplo,

-- busca 2 (Tabla [(2,'a'),(3,'b'),(2,'d')]) == Just 'a'

-- busca 4 (Tabla [(2,'a'),(3,'b'),(2,'d')]) == Nothing

-- ---------------------------------------------------------------------

busca :: Eq k => k -> Tabla k v -> Maybe v

busca _ (Tabla []) = Nothing

busca k (Tabla ((k', v) : kvs))

| k == k' = Just v

| otherwise = busca k (Tabla kvs)

-- ---------------------------------------------------------------------

-- Ejercicio 6. Definir la función

-- aplicaValores :: (v1 -> v2) -> Tabla k v1 -> Tabla k v2

-- tal que (aplicaValores f t) es la tabla obtenida aplicando la función f a

-- los valores de t. Por ejemplo,

-- λ> aplicaValores (+2) (Tabla [('a',5),('b',7),('c',4)])

-- Tabla [('a',7),('b',9),('c',6)]

-- ---------------------------------------------------------------------

aplicaValores :: (v1 -> v2) -> Tabla k v1 -> Tabla k v2

aplicaValores _ (Tabla []) = vacia

aplicaValores f (Tabla ((k, v) : kvs)) = inserta k (f v) (aplicaValores f (Tabla kvs))

-- ---------------------------------------------------------------------

-- Ejercicio 7. Definir la función

-- aplicaClaves :: (k1 -> k2) -> Tabla k1 v -> Tabla k2 v

-- tal que (aplicaClaves f t) es la tabla obtenida aplicando la función f a

-- las claves de t. Por ejemplo,

-- λ> aplicaClaves (+2) (Tabla [(2,'a'),(3,'b'),(2,'d')])

-- Tabla [(4,'a'),(5,'b'),(4,'d')]

-- ---------------------------------------------------------------------

aplicaClaves :: (k1 -> k2) -> Tabla k1 v -> Tabla k2 v

aplicaClaves _ (Tabla []) = vacia

aplicaClaves f (Tabla ((k, v) : kvs)) = inserta (f k) v (aplicaClaves f (Tabla kvs))

-- ---------------------------------------------------------------------

-- Ejercicio 8. Definir la función

-- ajusta :: Eq k => (Maybe v -> Maybe v) -> k -> Tabla k v -> Tabla k v

-- tal que (ajusta f k t) es el ajuste de la tabla t de acuerdo a las

-- siguientes reglas:

-- + Si `f k` es `Nothing` y `k` es una clave de t, borra el par con

-- clave `k`.

-- + Si `f k` es `Nothing` y `k` no es una clave de t, no hace nada.

-- + Si `f k` es `Just v` y `k` es una clave de t, cambia el valor de

-- `k` a `v`.

-- + Si `f k` es `Just v` y `k` no es una clave de t, añade el par `(h, v)`.

-- Por ejemplo,

-- λ> ajusta (\_ -> Nothing) 4 (Tabla [(3,2),(4,5)])

-- Tabla [(3,2)]

-- λ> ajusta (\_ -> Nothing) 7 (Tabla [(3,2),(4,5)])

-- Tabla [(3,2),(4,5)]

-- λ> ajusta (\_ -> Just 9) 4 (Tabla [(3,2),(4,5)])

-- Tabla [(3,2),(4,9)]

-- λ> ajusta (\_ -> Just 9) 7 (Tabla [(3,2),(4,5)])

-- Tabla [(3,2),(4,5),(7,9)]

-- λ> ajusta ((+ 2) <$>) 4 (Tabla [(3,2),(4,5)])

-- Tabla [(3,2),(4,7)]

-- λ> ajusta ((+ 2) <$>) 7 (Tabla [(3,2),(4,5)])

-- Tabla [(3,2),(4,5)]

-- λ> ajusta (\_ -> Nothing) 3 (Tabla [])

-- Tabla []

-- λ> ajusta (\_ -> Just 7) 3 (Tabla [])

-- Tabla [(3,7)]

-- λ> ajusta (\_ -> Nothing) 3 (Tabla [(3,1),(2,5),(3,7),(4,3)])

-- Tabla [(2,5),(4,3)]

-- λ> ajusta ((+ 2) <$>) 3 (Tabla [(3,1),(2,5),(3,7),(4,3)])

-- Tabla [(3,3),(2,5),(3,7),(4,3)]

-- λ> ajusta (\_ -> Nothing) 3 (Tabla [(2,5),(3,7),(4,3)])

-- Tabla [(2,5),(4,3)]

-- λ> ajusta ((+ 2) <$>) 3 (Tabla [(2,5),(3,7),(4,3)])

-- Tabla [(2,5),(3,9),(4,3)]

-- ---------------------------------------------------------------------

ajusta :: Eq k => (Maybe v -> Maybe v) -> k -> Tabla k v -> Tabla k v

ajusta f k (Tabla []) =

case f Nothing of

Nothing -> Tabla []

Just v -> Tabla [(k, v)]

ajusta f k (Tabla ((k', v) : kvs))

| k == k' =

case f (Just v) of

Nothing -> Tabla $ filter (\(k'', _) -> k'' /= k) kvs

Just v' -> Tabla $ (k, v') : kvs

| otherwise =

case ajusta f k (Tabla kvs) of

Tabla kvs' -> Tabla $ (k', v) : kvs'

-- ---------------------------------------------------------------------

-- § Referencias --

-- ---------------------------------------------------------------------

-- Esta relación de ejercicio es una adaptación de

-- "Tables.hs" https://bit.ly/3Cli8vV de Lars Brünjes.

Correspondencia entre tablas y diccionarios

module Tablas_y_diccionarios where

import Prelude hiding (lookup)
import Tablas
import Data.Map.Strict (Map, empty, insert, delete, lookup, mapKeys, alter)
import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir la función
--    tablaAdiccionario :: Ord k => Tabla k v -> Map k v
-- tal que (tablaAdiccionario t) es el diccionario correspondiente a la
-- tabla t. Por ejemplo,
--    λ> tablaAdiccionario (inserta 4 'd' (inserta 2 'a' vacia))
--    fromList [(2,'a'),(4,'d')]
-- ---------------------------------------------------------------------

tablaAdiccionario :: Ord k => Tabla k v -> Map k v
tablaAdiccionario (Tabla xs) =
  foldr (uncurry insert) empty xs

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir el procedimiento
--    tablaArbitraria :: (Arbitrary k, Arbitrary v) => Gen (Tabla k v)
-- tal que tablaArbitraria es una tabla aleatoria. Por ejemplo,
--    λ> sample (tablaArbitraria :: Gen (Tabla Int Int))
--    Tabla []
--    Tabla [(-3,3),(-2,-4)]
--    Tabla [(5,-2),(3,-9),(6,10),(-2,-1),(10,0),(3,8),(-10,-1),(5,-10),(-7,-1)]
--    Tabla [(-11,-4),(2,2),(6,-2),(11,-3),(-1,-3)]
--    Tabla [(16,7),(15,8),(-6,2),(13,14),(15,2),(4,-10),(17,15),(12,4),(-17,-2)]
--    ...
-- ---------------------------------------------------------------------

tablaArbitraria :: (Arbitrary k, Arbitrary v) => Gen (Tabla k v)
tablaArbitraria = Tabla <$> arbitrary

-- ---------------------------------------------------------------------
-- Ejercicio 3. Declarar Tabla como subclase de Arbitraria usando el
-- generador tablaArbitraria.
-- ---------------------------------------------------------------------

instance (Arbitrary k, Arbitrary v) => Arbitrary (Tabla k v) where
  arbitrary = tablaArbitraria

-- ---------------------------------------------------------------------
-- Ejercicio 4. Comprobar con QuickCheck que la función `inserta` es
-- equivalente a la función `insert` de Data.Map.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_inserta :: Int -> Int -> Tabla Int Int -> Property
prop_inserta n c t =
  tablaAdiccionario (inserta n c t) === insert n c (tablaAdiccionario t)

-- la comprobación es
--    λ> quickCheck prop_inserta
--    +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 5. Comprobar con QuickCheck que la función `borra`es
-- equivalente a la función `delete` de Data.Map.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_borra :: Int -> Tabla Int Char -> Property
prop_borra n t =
  tablaAdiccionario (borra n t) === delete n (tablaAdiccionario t)

-- La comprobación es
--    λ> quickCheck prop_borra
--    +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 6. Comprobar con QuickCheck que la función `busca`es
-- equivalente a la función `lookup` de Data.Map.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_busca :: Int -> Tabla Int Bool -> Property
prop_busca n t =
  busca n t === lookup n (tablaAdiccionario t)

-- La comprobación es
--    λ> quickCheck prop_busca
--    +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 7. Comprobar con QuickCheck que la función `aplicaValores`
-- es compatible con la `fmap` de Data.Map.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_aplicaValores :: Fun Char Bool -> Tabla Int Char -> Property
prop_aplicaValores f t =
  tablaAdiccionario (aplicaValores (applyFun f) t)
  === (applyFun f <$> tablaAdiccionario t)

-- La comprobación es
--    λ> quickCheck prop_aplicaValores
--    +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 8. Comprobar con QuickCheck que la función `aplicaClaves`
-- es compatible con la `mapKeys` de Data.Map.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_aplicaClaves :: Tabla Int Char -> Property
prop_aplicaClaves t =
  tablaAdiccionario (aplicaClaves succ t)
  === mapKeys succ (tablaAdiccionario t)

-- La comprobación es
--    λ> quickCheck prop_aplicaClaves
--    +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 9. Comprobar con QuickCheck que la función `ajusta`
-- es equivalente a la `alter` de Data.Map.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_ajusta :: Fun (Maybe Char) (Maybe Char) -> Int -> Tabla Int Char -> Property
prop_ajusta f n t =
  tablaAdiccionario (ajusta (applyFun f) n t)
  === alter (applyFun f) n (tablaAdiccionario t)

-- La comprobación es
--    λ> quickCheck prop_ajusta
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

module Tablas_y_diccionarios where

import Prelude hiding (lookup)

import Tablas

import Data.Map.Strict (Map, empty, insert, delete, lookup, mapKeys, alter)

import Test.QuickCheck

-- ---------------------------------------------------------------------

-- Ejercicio 1. Definir la función

-- tablaAdiccionario :: Ord k => Tabla k v -> Map k v

-- tal que (tablaAdiccionario t) es el diccionario correspondiente a la

-- tabla t. Por ejemplo,

-- λ> tablaAdiccionario (inserta 4 'd' (inserta 2 'a' vacia))

-- fromList [(2,'a'),(4,'d')]

-- ---------------------------------------------------------------------

tablaAdiccionario :: Ord k => Tabla k v -> Map k v

tablaAdiccionario (Tabla xs) =

foldr (uncurry insert) empty xs

-- ---------------------------------------------------------------------

-- Ejercicio 2. Definir el procedimiento

-- tablaArbitraria :: (Arbitrary k, Arbitrary v) => Gen (Tabla k v)

-- tal que tablaArbitraria es una tabla aleatoria. Por ejemplo,

-- λ> sample (tablaArbitraria :: Gen (Tabla Int Int))

-- Tabla []

-- Tabla [(-3,3),(-2,-4)]

-- Tabla [(5,-2),(3,-9),(6,10),(-2,-1),(10,0),(3,8),(-10,-1),(5,-10),(-7,-1)]

-- Tabla [(-11,-4),(2,2),(6,-2),(11,-3),(-1,-3)]

-- Tabla [(16,7),(15,8),(-6,2),(13,14),(15,2),(4,-10),(17,15),(12,4),(-17,-2)]

-- ...

-- ---------------------------------------------------------------------

tablaArbitraria :: (Arbitrary k, Arbitrary v) => Gen (Tabla k v)

tablaArbitraria = Tabla <$> arbitrary

-- ---------------------------------------------------------------------

-- Ejercicio 3. Declarar Tabla como subclase de Arbitraria usando el

-- generador tablaArbitraria.

-- ---------------------------------------------------------------------

instance (Arbitrary k, Arbitrary v) => Arbitrary (Tabla k v) where

arbitrary = tablaArbitraria

-- ---------------------------------------------------------------------

-- Ejercicio 4. Comprobar con QuickCheck que la función `inserta` es

-- equivalente a la función `insert` de Data.Map.

-- ---------------------------------------------------------------------

-- La propiedad es

prop_inserta :: Int -> Int -> Tabla Int Int -> Property

prop_inserta n c t =

tablaAdiccionario (inserta n c t) === insert n c (tablaAdiccionario t)

-- la comprobación es

-- λ> quickCheck prop_inserta

-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------

-- Ejercicio 5. Comprobar con QuickCheck que la función `borra`es

-- equivalente a la función `delete` de Data.Map.

-- ---------------------------------------------------------------------

-- La propiedad es

prop_borra :: Int -> Tabla Int Char -> Property

prop_borra n t =

tablaAdiccionario (borra n t) === delete n (tablaAdiccionario t)

-- La comprobación es

-- λ> quickCheck prop_borra

-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------

-- Ejercicio 6. Comprobar con QuickCheck que la función `busca`es

-- equivalente a la función `lookup` de Data.Map.

-- ---------------------------------------------------------------------

-- La propiedad es

prop_busca :: Int -> Tabla Int Bool -> Property

prop_busca n t =

busca n t === lookup n (tablaAdiccionario t)

-- La comprobación es

-- λ> quickCheck prop_busca

-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------

-- Ejercicio 7. Comprobar con QuickCheck que la función `aplicaValores`

-- es compatible con la `fmap` de Data.Map.

-- ---------------------------------------------------------------------

-- La propiedad es

prop_aplicaValores :: Fun Char Bool -> Tabla Int Char -> Property

prop_aplicaValores f t =

tablaAdiccionario (aplicaValores (applyFun f) t)

=== (applyFun f <$> tablaAdiccionario t)

-- La comprobación es

-- λ> quickCheck prop_aplicaValores

-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------

-- Ejercicio 8. Comprobar con QuickCheck que la función `aplicaClaves`

-- es compatible con la `mapKeys` de Data.Map.

-- ---------------------------------------------------------------------

-- La propiedad es

prop_aplicaClaves :: Tabla Int Char -> Property

prop_aplicaClaves t =

tablaAdiccionario (aplicaClaves succ t)

=== mapKeys succ (tablaAdiccionario t)

-- La comprobación es

-- λ> quickCheck prop_aplicaClaves

-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------

-- Ejercicio 9. Comprobar con QuickCheck que la función `ajusta`

-- es equivalente a la `alter` de Data.Map.

-- ---------------------------------------------------------------------

-- La propiedad es

prop_ajusta :: Fun (Maybe Char) (Maybe Char) -> Int -> Tabla Int Char -> Property

prop_ajusta f n t =

tablaAdiccionario (ajusta (applyFun f) n t)

=== alter (applyFun f) n (tablaAdiccionario t)

-- La comprobación es

-- λ> quickCheck prop_ajusta

-- +++ OK, passed 100 tests.

El tipo abstracto de las tablas

Correspondencia entre tablas y diccionarios

Se puede imprimir o compartir con