Tema 17: El TAD de los conjuntos

1 Especificación del TAD de los conjuntos

1.1 Signatura del TAD de los conjuntos

vacio,     :: Conj a                         
inserta    :: Eq a => a -> Conj a -> Conj a
elimina    :: Eq a => a -> Conj a -> Conj a
pertenece  :: Eq a => a -> Conj a -> Bool  
esVacio    :: Conj a -> Bool                

1.2 Propiedades del TAD de los conjuntos

2 Implementaciones del TAD de los conjuntos

2.1 Los conjuntos como listas no ordenadas con duplicados

module ConjuntoConListasNoOrdenadasConDuplicados 
    (Conj,
     vacio,     -- Conj a                         
     inserta,   -- Eq a => a -> Conj a -> Conj a
     elimina,   -- Eq a => a -> Conj a -> Conj a
     pertenece, -- Eq a => a -> Conj a -> Bool  
     esVacio,   -- Conj a -> Bool                
    ) where
newtype Conj a = Cj [a]
instance Show a => Show (Conj a) where
    showsPrec _ (Cj s) cad = showConj s cad

showConj []     cad = showString "{}" cad
showConj (x:xs) cad = 
  showChar '{' (shows x (showl xs cad))
  where 
   showl []     cad = showChar '}' cad
   showl (x:xs) cad = showChar ',' (shows x (showl xs cad))
ghci > c1
{2,5,1,3,7,5,3,2,1,9,0}
c1 :: Conj Int
c1 = foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0]
ghci> vacio
{}
vacio :: Conj a                         
vacio = Cj []
c1            ==  {2,5,1,3,7,5,3,2,1,9,0}
inserta 5 c1  ==  {5,2,5,1,3,7,5,3,2,1,9,0}
inserta :: Eq a => a -> Conj a -> Conj a
inserta x (Cj ys) = Cj (x:ys)
c1            ==  {2,5,1,3,7,5,3,2,1,9,0}
elimina 3 c1  ==  {2,5,1,7,5,2,1,9,0}
elimina :: Eq a => a -> Conj a -> Conj a
elimina x (Cj ys) = Cj (filter (/= x) ys)
c1              ==  {2,5,1,3,7,5,3,2,1,9,0}
pertenece 3 c1  ==  True
pertenece 4 c1  ==  False
pertenece :: Eq a => a -> Conj a -> Bool 
pertenece x (Cj xs) = elem x xs
esVacio c1     ==  False
esVacio vacio  ==  True
esVacio :: Conj a -> Bool                
esVacio (Cj xs) = null xs
subconjunto (Cj [1,3,2,1]) (Cj [3,1,3,2])  ==  True
subconjunto (Cj [1,3,4,1]) (Cj [3,1,3,2])  ==  False
subconjunto :: Eq a => Conj a -> Conj a -> Bool
subconjunto (Cj xs) (Cj ys) = sublista xs ys
    where sublista [] _      = True
          sublista (x:xs) ys = elem x ys && 
                               sublista xs ys
igualConjunto (Cj [1,3,2,1]) (Cj [3,1,3,2])  ==  True
igualConjunto (Cj [1,3,4,1]) (Cj [3,1,3,2])  ==  False
igualConjunto :: Eq a => Conj a -> Conj a -> Bool
igualConjunto c1 c2 = 
    subconjunto c1 c2 && subconjunto c2 c1
instance Eq a => Eq (Conj a) where
    (==) = igualConjunto

2.2 Los conjuntos como listas no ordenadas sin duplicados

module ConjuntoConListasNoOrdenadasSinDuplicados
    (Conj,
     vacio,     -- Conj a                       
     esVacio,   -- Conj a -> Bool               
     pertenece, -- Eq a => a -> Conj a -> Bool  
     inserta,   -- Eq a => a -> Conj a -> Conj a
     elimina    -- Eq a => a -> Conj a -> Conj a
    ) where
newtype Conj a = Cj [a]
instance (Show a) => Show (Conj a) where
    showsPrec _ (Cj s) cad = showConj s cad

showConj []     cad = showString "{}" cad
showConj (x:xs) cad = showChar '{' (shows x (showl xs cad)) 
  where 
  showl []     cad = showChar '}' cad
  showl (x:xs) cad = showChar ',' (shows x (showl xs cad))
ghci> c1
{7,5,3,2,1,9,0}
c1 :: Conj Int
c1 = foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0]
ghci> vacio
{}
vacio :: Conj a                         
vacio = Cj []
esVacio c1     ==  False
esVacio vacio  ==  True
esVacio :: Conj a -> Bool                
esVacio (Cj xs) = null xs
c1              ==  {2,5,1,3,7,5,3,2,1,9,0}
pertenece 3 c1  ==  True
pertenece 4 c1  ==  False
pertenece :: Eq a => a -> Conj a -> Bool 
pertenece x (Cj xs) = elem x xs
inserta 4 c1  ==  {4,7,5,3,2,1,9,0}
inserta 5 c1  ==  {7,5,3,2,1,9,0}
inserta :: Eq a => a -> Conj a -> Conj a
inserta x s@(Cj xs) | pertenece x s = s
                    | otherwise  = Cj (x:xs)
elimina 3 c1  ==  {7,5,2,1,9,0}
elimina :: Eq a => a -> Conj a -> Conj a
elimina x (Cj ys) = Cj [y | y <- ys, y /= x]
subconjunto (Cj [1,3,2]) (Cj [3,1,2])    ==  True
subconjunto (Cj [1,3,4,1]) (Cj [1,3,2])  ==  False
subconjunto :: Eq a => Conj a -> Conj a -> Bool
subconjunto (Cj xs) (Cj ys) = sublista xs ys
    where sublista [] _      = True
          sublista (x:xs) ys = elem x ys && 
                               sublista xs ys
igualConjunto (Cj [3,2,1]) (Cj [1,3,2])  ==  True
igualConjunto (Cj [1,3,4]) (Cj [1,3,2])  ==  False
igualConjunto :: Eq a => Conj a -> Conj a -> Bool
igualConjunto c1 c2 = 
    subconjunto c1 c2 && subconjunto c2 c1
instance Eq a => Eq (Conj a) where
    (==) = igualConjunto

2.3 Los conjuntos como listas ordenadas sin duplicados

module ConjuntoConListasOrdenadasSinDuplicados
    (Conj,
     vacio,     -- Conj a                       
     esVacio,   -- Conj a -> Bool               
     pertenece, -- Ord a => a -> Conj a -> Bool  
     inserta,   -- Ord a => a -> Conj a -> Conj a
     elimina    -- Ord a => a -> Conj a -> Conj a
    ) where
newtype Conj a = Cj [a]
    deriving Eq
instance (Show a) => Show (Conj a) where
    showsPrec _ (Cj s) cad = showConj s cad

showConj []     cad = showString "{}" cad
showConj (x:xs) cad = showChar '{' (shows x (showl xs cad))
     where showl []     cad = showChar '}' cad
           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))
ghci> c1
{0,1,2,3,5,7,9}
c1 :: Conj Int
c1 = foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0]
ghci> vacio
{}
vacio :: Conj a                         
vacio = Cj []
esVacio c1     ==  False
esVacio vacio  ==  True
esVacio :: Conj a -> Bool                
esVacio (Cj xs) = null xs
c1              ==  {0,1,2,3,5,7,9}
pertenece 3 c1  ==  True
pertenece 4 c1  ==  False
pertenece :: Ord a => a -> Conj a -> Bool 
pertenece x (Cj ys) = elem x (takeWhile (<= x) ys)
c1            ==  {0,1,2,3,5,7,9}
inserta 5 c1  ==  {0,1,2,3,5,7,9}
inserta 4 c1  ==  {0,1,2,3,4,5,7,9}
inserta :: Ord a => a -> Conj a -> Conj a
inserta x (Cj s) = Cj (agrega x s) where 
   agrega x []                   = [x]                
   agrega x s@(y:ys) | x > y     = y : (agrega x ys)
                     | x < y     = x : s
                     | otherwise = s
c1            ==  {0,1,2,3,5,7,9}
elimina 3 c1  ==  {0,1,2,5,7,9}
elimina :: Ord a => a -> Conj a -> Conj a
elimina x (Cj s) = Cj (elimina x s) where 
   elimina x []                   = []
   elimina x s@(y:ys) | x > y     = y : elimina x ys
                      | x < y     = s
                      | otherwise = ys

2.4 Los conjuntos de números enteros mediante números binarios

  {3,4}     en binario es 11000 y en decimal es 24 
  {1,2,3,4} en binario es 11110 y en decimal es 30 
  {1,2,4}   en binario es 10110 y en decimal es 22 
module ConjuntoConNumerosBinarios
    (Conj,
     vacio,     -- Conj                       
     esVacio,   -- Conj -> Bool               
     pertenece, -- Int -> Conj -> Bool  
     inserta,   -- Int -> Conj -> Conj
     elimina    -- Int -> Conj -> Conj
    ) where
newtype Conj = Cj Int deriving Eq
conj2Lista (Cj 24)  ==  [3,4]
conj2Lista (Cj 30)  ==  [1,2,3,4]
conj2Lista (Cj 22)  ==  [1,2,4]
conj2Lista (Cj s) = c2l s 0
    where 
      c2l 0 _             = []
      c2l n i | odd n     = i : c2l (n `div` 2) (i+1)
              | otherwise = c2l (n `div` 2) (i+1)
instance Show Conj where
    showsPrec _ s cad = showConj (conj2Lista s) cad

showConj []     cad = showString "{}" cad
showConj (x:xs) cad = 
   showChar '{' (shows x (showl xs cad))
   where 
     showl []     cad = showChar '}' cad
     showl (x:xs) cad = showChar ',' (shows x (showl xs cad))
maxConj  ==  29
maxConj :: Int
maxConj = 
   truncate (logBase 2 (fromIntegral maxInt)) - 1
   where maxInt = maxBound::Int
ghci> c1
{0,1,2,3,5,7,9}
c1 :: Conj
c1 = foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0]
ghci> vacio
{}
vacio :: Conj
vacio = Cj 0
esVacio c1     ==  False
esVacio vacio  ==  True
esVacio :: Conj -> Bool
esVacio (Cj n) = n == 0
c1              ==  {0,1,2,3,5,7,9}
pertenece 3 c1  ==  True
pertenece 4 c1  ==  False
pertenece :: Int -> Conj -> Bool
pertenece i (Cj s)
    | (i>=0) && (i<=maxConj) = odd (s `div` (2^i))
    | otherwise    
      = error ("pertenece: elemento ilegal =" ++ show i)
c1            ==  {0,1,2,3,5,7,9}
inserta 5 c1  ==  {0,1,2,3,5,7,9}
inserta 4 c1  ==  {0,1,2,3,4,5,7,9}
inserta i (Cj s)
    | (i>=0) && (i<=maxConj) = Cj (d'*e+m)
    | otherwise 
      = error ("inserta: elemento ilegal =" ++ show i)
    where (d,m) = divMod s e
          e     = 2^i
          d'    = if odd d then d else d+1
c1            ==  {0,1,2,3,5,7,9}
elimina 3 c1  ==  {0,1,2,5,7,9}
elimina i (Cj s)
    | (i>=0) && (i<=maxConj) = Cj (d'*e+m)
    | otherwise              
      = error ("elimina: elemento ilegal =" ++ show i)
    where (d,m) = divMod s e
          e     = 2^i
          d'    = if odd d then d-1 else d

3 Comprobación de las implementaciones con QuickCheck

3.1 Librerías auxiliares

import ConjuntoConListasNoOrdenadasConDuplicados
-- import ConjuntoConListasNoOrdenadasSinDuplicados
-- import ConjuntoConListasOrdenadasSinDuplicados
import Test.QuickCheck
import Test.Framework
import Test.Framework.Providers.QuickCheck2

3.2 Generador de conjuntos

ghci> sample genConjunto
{3,-2,-2,-3,-2,4}
{-8,0,4,6,-5,-2}
{}
genConjunto :: Gen (Conj Int)
genConjunto = do xs <- listOf arbitrary
                 return (foldr inserta vacio xs)

instance Arbitrary (Conj Int) where
    arbitrary = genConjunto

3.3 Especificación de las propiedades de los conjuntos

prop_independencia_repeticiones :: Int -> Conj Int 
                                   -> Bool
prop_independencia_repeticiones x c =
    inserta x (inserta x c) == inserta x c
prop_independencia_del_orden :: Int -> Int -> Conj Int 
                                -> Bool
prop_independencia_del_orden x y c =
    inserta x (inserta y c) == inserta y (inserta x c)
prop_vacio_no_elementos:: Int -> Bool
prop_vacio_no_elementos x = 
    not (pertenece x vacio)
prop_pertenece_inserta :: Int -> Int -> Conj Int -> Bool
prop_pertenece_inserta x y c =
    pertenece y (inserta x c) == (x==y) || pertenece y c
prop_elimina_vacio :: Int -> Bool
prop_elimina_vacio x =
    elimina x vacio == vacio
prop_elimina_inserta :: Int -> Int -> Conj Int -> Bool
prop_elimina_inserta x y c =
    elimina x (inserta y c) 
    == if x == y then elimina x c
       else inserta y (elimina x c)
prop_vacio_es_vacio :: Bool
prop_vacio_es_vacio = 
    esVacio (vacio :: Conj Int)
prop_inserta_es_no_vacio :: Int -> Conj Int -> Bool
prop_inserta_es_no_vacio x c =
    not (esVacio (inserta x c))

3.4 Comprobación de las propiedades

Definición del procedimiento de comprobación

compruebaPropiedades = 
    defaultMain 
        [testGroup "Propiedades del TAD conjunto:"
          [testProperty "P1" prop_vacio_es_vacio,
           testProperty "P2" prop_inserta_es_no_vacio,
           testProperty "P3" prop_independencia_repeticiones,
           testProperty "P4" prop_independencia_del_orden,
           testProperty "P5" prop_vacio_no_elementos,
           testProperty "P6" prop_pertenece_inserta,
           testProperty "P7" prop_elimina_vacio,
           testProperty "P8" prop_elimina_inserta]]

Comprobación de las propiedades de los conjuntos

ghci> compruebaPropiedades 
Propiedades del TAD conjunto:
  P1: [OK, passed 100 tests]
  P2: [OK, passed 100 tests]
  P3: [OK, passed 100 tests]
  P4: [OK, passed 100 tests]
  P5: [OK, passed 100 tests]
  P6: [OK, passed 100 tests]
  P7: [OK, passed 100 tests]
  P8: [OK, passed 100 tests]

         Properties  Total      
 Passed  8           8          
 Failed  0           0          
 Total   8           8    

4 Complejidades

LNOCD LNOSD LOSD
vacio O(1) O(1) O(1)
inserta O(1) O(n) O(n)
elimina O(n) O(n) O(n)
pertenece O(n) O(n) O(n)
esVacio O(1) O(1) O(1)
(==) O(n.m) O(n.m) O(min(n,m))


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