Tema 17: El tipo abstracto de datos de los conjuntos

Índice

1. Especificación del TAD de los conjuntos
- 1.1. Signatura del TAD de los conjuntos
- 1.2. Propiedades del TAD de los conjuntos
2. Implementaciones del TAD de los conjuntos
3. Comprobación de las implementaciones con QuickCheck
4. Complejidades
5. Material complementario
6. Bibliografía

1. Especificación del TAD de los conjuntos

1.1. Signatura del TAD de los conjuntos

Signatura:

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

Descripción de las operaciones:
- vacio es el conjunto vacío.
- (inserta x c) es el conjunto obtenido añadiendo el elemento x al conjunto c.
- (elimina x c) es el conjunto obtenido eliminando el elemento x del conjunto c.
- (pertenece x c) se verifica si x pertenece al conjunto c.
- (esVacio c) se verifica si c es el conjunto vacío.

1.2. Propiedades del TAD de los conjuntos

inserta x (inserta x c) == inserta x c
inserta x (inserta y c) == inserta y (inserta x c)
not (pertenece x vacio)
pertenece y (inserta x c) == (x==y) || pertenece y c
elimina x vacio == vacio
Si x == y, entonces elimina x (inserta y c) == elimina x c
Si x /= y, entonces elimina x (inserta y c) == inserta y (elimina x c)
esVacio vacio
not (esVacio (inserta x c))

2. Implementaciones del TAD de los conjuntos

2.1. Los conjuntos como listas no ordenadas con duplicados

Nota: El código está en ConjuntoConListasNoOrdenadasConDuplicados.hs.

Cabecera del módulo:

module Tema_17.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
   escribeConjunto -- Show a => Conj a -> String
  ) where

El tipo de los conjuntos.
```
newtype Conj a = Cj [a]
```

(escribeConjunto c) es la cadena correspondiente al conjunto c. Por ejemplo,

λ> escribeConjunto (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
"{2,5,1,3,7,5,3,2,1,9,0}"

escribeConjunto :: Show a => Conj a -> String
escribeConjunto (Cj [])     = "{}"
escribeConjunto (Cj [x])    = "{" ++ show x ++ "}"
escribeConjunto (Cj (x:xs)) = "{" ++ show x ++ aux xs
  where aux [] = "}"
        aux (y:ys) = "," ++ show y ++ aux ys

Procedimiento de escritura de los conjuntos.

instance Show a => Show (Conj a) where
  show = escribeConjunto

Ejemplo de conjunto: El conjunto obtenido añadiéndole al conjunto vacío los elementos 2, 5, 1, 3, 7, 5, 3, 2, 1, 9 y 0 es
```
λ> foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0]
{2,5,1,3,7,5,3,2,1,9,0}
```
vacio es el conjunto vacío. Por ejemplo,
```
λ> vacio
{}
```
Su definición es
```
vacio :: Conj a
vacio = Cj []
```

(inserta x c) es el conjunto obtenido añadiendo el elemento x al conjunto c. Por ejemplo,

λ> inserta 5 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
{5,2,5,1,3,7,5,3,2,1,9,0}

Su definición es

inserta :: Eq a => a -> Conj a -> Conj a
inserta x (Cj ys) = Cj (x:ys)

(elimina x c) es el conjunto obtenido eliminando el elemento x del conjunto c. Por ejemplo,

λ> elimina 3 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
{2,5,1,7,5,2,1,9,0}

Su definición es

elimina :: Eq a => a -> Conj a -> Conj a
elimina x (Cj ys) = Cj (filter (/= x) ys)

(pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,

pertenece 3 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])  ==  True
pertenece 4 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])  ==  False

Su definición es

pertenece :: Eq a => a -> Conj a -> Bool
pertenece x (Cj xs) = elem x xs

(esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,

esVacio (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0]) ==  False
esVacio vacio == True

Su definición es

esVacio :: Conj a -> Bool
esVacio (Cj xs) = null xs

(subconjunto c1 c2) se verifica si c1 es un subconjunto de c2. Por ejemplo,

subconjunto (Cj [1,3,2,1]) (Cj [3,1,3,2])  ==  True
subconjunto (Cj [1,3,4,1]) (Cj [3,1,3,2])  ==  False

Su definición es

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 c1 c2) se verifica si los conjuntos c1 y c2 son iguales. Por ejemplo,

igualConjunto (Cj [1,3,2,1]) (Cj [3,1,3,2])  ==  True
igualConjunto (Cj [1,3,4,1]) (Cj [3,1,3,2])  ==  False

Su definición es

igualConjunto :: Eq a => Conj a -> Conj a -> Bool
igualConjunto c1 c2 =
    subconjunto c1 c2 && subconjunto c2 c1

Los conjuntos son comparables por igualdad.

instance Eq a => Eq (Conj a) where
  (==) = igualConjunto

2.2. Los conjuntos como listas no ordenadas sin duplicados

Nota: El código está en ConjuntoConListasNoOrdenadasSinDuplicados.hs.

Cabecera del módulo.

module Tema_17.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
   escribeConjunto -- Show a => Conj a -> String
  ) where

Los conjuntos como listas no ordenadas sin repeticiones.
```
newtype Conj a = Cj [a]
```

(escribeConjunto c) es la cadena correspondiente al conjunto c. Por ejemplo,

λ> escribeConjunto (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
"{7,5,3,2,1,9,0}"

escribeConjunto :: Show a => Conj a -> String
escribeConjunto (Cj [])     = "{}"
escribeConjunto (Cj [x])    = "{" ++ show x ++ "}"
escribeConjunto (Cj (x:xs)) = "{" ++ show x ++ aux xs
  where aux [] = "}"
        aux (y:ys) = "," ++ show y ++ aux ys

Procedimiento de escritura de los conjuntos.

instance Show a => Show (Conj a) where
  show = escribeConjunto

Ejemplo de conjunto: El conjunto obtenido añadiéndole al conjunto vacío los elementos 2, 5, 1, 3, 7, 5, 3, 2, 1, 9 y 0 es
```
λ> foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0]
{7,5,3,2,1,9,0}
```

vacio es el conjunto vacío. Por ejemplo,

λ> vacio
{}

vacio :: Conj a
vacio = Cj []

(esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,

esVacio (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0]) == False
esVacio vacio == True

Su definición es

esVacio :: Conj a -> Bool
esVacio (Cj xs) = null xs

(pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,

pertenece 3 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])  ==  True
pertenece 4 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])  ==  False

Su definición es

pertenece :: Eq a => a -> Conj a -> Bool
pertenece x (Cj xs) = elem x xs

(inserta x c) es el conjunto obtenido añadiendo el elemento x al conjunto c. Por ejemplo,

λ> inserta 5 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
{7,5,3,2,1,9,0}
λ> inserta 4 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
{4,7,5,3,2,1,9,0}

Su definición es

inserta :: Eq a => a -> Conj a -> Conj a
inserta x s@(Cj xs) | pertenece x s = s
                    | otherwise  = Cj (x:xs)

(elimina x c) es el conjunto obtenido eliminando el elemento x del conjunto c. Por ejemplo,

λ> elimina 3 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
{7,5,2,1,9,0}
λ> elimina 12 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
{7,5,3,2,1,9,0}

Su definición es

elimina :: Eq a => a -> Conj a -> Conj a
elimina x (Cj ys) = Cj [y | y <- ys, y /= x]

(subconjunto c1 c2) se verifica si c1 es un subconjunto de c2. Por ejemplo,

subconjunto (Cj [1,3,2]) (Cj [3,1,2])    ==  True
subconjunto (Cj [1,3,4,1]) (Cj [1,3,2])  ==  False

Su definición es

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 c1 c2) se verifica si los conjuntos c1 y c2 son iguales. Por ejemplo,

igualConjunto (Cj [3,2,1]) (Cj [1,3,2])  ==  True
igualConjunto (Cj [1,3,4]) (Cj [1,3,2])  ==  False

Su definición es

igualConjunto :: Eq a => Conj a -> Conj a -> Bool
igualConjunto c1 c2 = subconjunto c1 c2 && subconjunto c2 c1

Los conjuntos son comparables por igualdad.

instance Eq a => Eq (Conj a) where
  (==) = igualConjunto

2.3. Los conjuntos como listas ordenadas sin duplicados

Nota: El código está en ConjuntoConListasOrdenadasSinDuplicados.

Cabecera del módulo

module Tema_17.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
   escribeConjunto -- Show a => Conj a -> String
  ) where

Los conjuntos como listas ordenadas sin repeticiones.
```
newtype Conj a = Cj [a]
  deriving Eq
```

(escribeConjunto c) es la cadena correspondiente al conjunto c. Por ejemplo,

λ> escribeConjunto (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
"{0,1,2,3,5,7,9}"

escribeConjunto :: Show a => Conj a -> String
escribeConjunto (Cj [])     = "{}"
escribeConjunto (Cj [x])    = "{" ++ show x ++ "}"
escribeConjunto (Cj (x:xs)) = "{" ++ show x ++ aux xs
  where aux []     = "}"
        aux (y:ys) = "," ++ show y ++ aux ys

Procedimiento de escritura de los conjuntos.

instance Show a => Show (Conj a) where
  show = escribeConjunto

Ejemplo de conjunto: El conjunto obtenido añadiéndole al conjunto vacío los elementos 2, 5, 1, 3, 7, 5, 3, 2, 1, 9 y 0 es
```
λ> foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0]
{0,1,2,3,5,7,9}
```
vacio es el conjunto vacío. Por ejemplo,
```
λ> vacio
{}
```
Su definición es
```
vacio :: Conj a
vacio = Cj []
```

(esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,

esVacio (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0]) ==  False
esVacio vacio == True

Su definición es

esVacio :: Conj a -> Bool
esVacio (Cj xs) = null xs

(pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,

pertenece 3 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])  ==  True
pertenece 4 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])  ==  False

Su definición es

pertenece :: Ord a => a -> Conj a -> Bool
pertenece x (Cj ys) = elem x (takeWhile (<= x) ys)

(inserta x c) es el conjunto obtenido añadiendo el elemento x al conjunto c. Por ejemplo,

λ> inserta 5 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
{0,1,2,3,5,7,9}
λ> inserta 4 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
{0,1,2,3,4,5,7,9}

Su definición es

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

(elimina x c) es el conjunto obtenido eliminando el elemento x del conjunto c. Por ejemplo,

λ> elimina 3 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
{0,1,2,5,7,9}
λ> elimina 4 (foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0])
{0,1,2,3,5,7,9}

Su definición es

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

3. Comprobación de las implementaciones con QuickCheck

3.1. Pragma y librerías auxiliares

Nota: El código se encuentra en ConjuntoPropiedades.hs.

Al principio del fichero se añade

{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE FlexibleInstances #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

Importación de la implementación de conjuntos que se desea verificar.

import Tema_17.ConjuntoConListasNoOrdenadasConDuplicados
-- import Tema_17.ConjuntoConListasNoOrdenadasSinDuplicados
-- import Tema_17.ConjuntoConListasOrdenadasSinDuplicados
-- import I1M.Conjunto

Importación de la librería de comprobación
```
import Test.QuickCheck
```

3.2. Generador de conjuntos

genConjunto es un generador de conjuntos. Por ejemplo,

λ> sample genConjunto
{3,-2,-2,-3,-2,4}
{-8,0,4,6,-5,-2}
{}
...

Su definición es

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

El número de veces que se añada un elemento a un conjunto no importa.

prop_independencia_repeticiones :: Int -> Conj Int -> Bool
prop_independencia_repeticiones x c =
  inserta x (inserta x c) == inserta x c

El orden en que se añadan los elementos a un conjunto no importa.

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)

El conjunto vacío no tiene elementos.

prop_vacio_no_elementos:: Int -> Bool
prop_vacio_no_elementos x =
  not (pertenece x vacio)

Un elemento pertenece al conjunto obtenido añadiendo x al conjunto c syss es igual a x o pertenece a c.

prop_pertenece_inserta :: Int -> Int -> Conj Int -> Bool
prop_pertenece_inserta x y c =
  pertenece y (inserta x c) == (x==y) || pertenece y c

Al eliminar cualquier elemento del conjunto vacío se obtiene el conjunto vacío.

prop_elimina_vacio :: Int -> Bool
prop_elimina_vacio x =
  elimina x vacio == vacio

El resultado de eliminar x en el conjunto obtenido añadiéndole y al conjunto c es c menos x, si x e y~son iguales y es el conjunto obtenido añadiéndole ~y a c menos x, en caso contrario.

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)

vacio es vacío.

prop_vacio_es_vacio :: Bool
prop_vacio_es_vacio =
  esVacio (vacio :: Conj Int)

Los conjuntos construidos con inserta no son vacío.

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

Para verificar todas las propiedades se escribe

return []

verificaConjunto :: IO Bool
verificaConjunto = $quickCheckAll

Comprobación de las propiedades de los conjuntos

λ> verificaConjunto
=== prop_independencia_repeticiones from ConjuntoPropiedades.hs:55 ===
+++ OK, passed 100 tests.

=== prop_independencia_del_orden from ConjuntoPropiedades.hs:65 ===
+++ OK, passed 100 tests.

=== prop_vacio_no_elementos from ConjuntoPropiedades.hs:77 ===
+++ OK, passed 100 tests.

=== prop_pertenece_inserta from ConjuntoPropiedades.hs:87 ===
+++ OK, passed 100 tests.

=== prop_elimina_vacio from ConjuntoPropiedades.hs:100 ===
+++ OK, passed 100 tests.

=== prop_elimina_inserta from ConjuntoPropiedades.hs:111 ===
+++ OK, passed 100 tests.

=== prop_vacio_es_vacio from ConjuntoPropiedades.hs:126 ===
+++ OK, passed 1 test.

=== prop_inserta_es_no_vacio from ConjuntoPropiedades.hs:135 ===
+++ OK, passed 100 tests.

True

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

donde

LNOCD usa listas no ordenadas con duplicados
LNOSD usa listas no ordenadas sin duplicados
LOSD usa listas ordenadas sin duplicados

5. Material complementario

El código del tema se encuentra en los siguientes enlaces

Este tema también se encuentra en los siguientes formatos:

Como transparencias en PDF.
Como libro interactivo en IHaskell sobre Jupyter.
Como vídeo de clase.

6. Bibliografía

F. Rabhi y G. Lapalme. Algorithms: A functional programming approach.
- Cap. 5.5: Sets.