{"id":7919,"date":"2023-02-28T06:00:07","date_gmt":"2023-02-28T04:00:07","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7919"},"modified":"2023-02-22T19:54:46","modified_gmt":"2023-02-22T17:54:46","slug":"28-feb-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/28-feb-23\/","title":{"rendered":"El tipo abstracto de datos de los conjuntos"},"content":{"rendered":"<h3>1. El tipo abstracto de datos de los conjuntos<\/h3>\n<p>Un conjunto es una estructura de datos, caracterizada por ser una colecci\u00f3n de elementos en la que no importe ni el orden ni la repetici\u00f3n de elementos.<\/p>\n<p>Las operaciones que definen al tipo abstracto de datos (TAD) de los conjuntos (cuyos elementos son del tipo a) son las siguientes:<\/p>\n<pre lang=\"text\">\n   vacio      :: Conj a\n   inserta    :: Ord a => a -> Conj a -> Conj a\n   menor      :: Ord a => Conj a -> a\n   elimina    :: Ord a => a -> Conj a -> Conj a\n   pertenece  :: Ord a => a -> Conj a -> Bool\n   esVacio    :: Conj a -> Bool\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>vacio es el conjunto vac\u00edo.<\/li>\n<li>(inserta x c) es el conjunto obtenido a\u00f1adiendo el elemento x al<br \/>\nconjunto c.<\/li>\n<li>(menor c) es el menor elemento del conjunto c.<\/li>\n<li>(elimina x c) es el conjunto obtenido eliminando el elemento x del conjunto c.<\/li>\n<li>(pertenece x c) se verifica si x pertenece al conjunto c.<\/li>\n<li>(esVacio c) se verifica si c es el conjunto vac\u00edo.<\/li>\n<\/ul>\n<p>Las operaciones tienen que verificar las siguientes propiedades:<\/p>\n<ul>\n<li>inserta x (inserta x c) == inserta x c<\/li>\n<li>inserta x (inserta y c) == inserta y (inserta x c)<\/li>\n<li>not (pertenece x vacio)<\/li>\n<li>pertenece y (inserta x c) == (x==y) || pertenece y c<\/li>\n<li>elimina x vacio == vacio<\/li>\n<li>Si x == y, entonces elimina x (inserta y c) == elimina x c<\/li>\n<li>Si x \/= y, entonces elimina x (inserta y c) == inserta y (elimina x c)<\/li>\n<li>esVacio vacio<\/li>\n<li>not (esVacio (inserta x c))<\/li>\n<\/ul>\n<h3>2. Los conjuntos en Haskell<\/h3>\n<h4>2.1. El tipo abstracto de datos de los conjuntos en Haskell<\/h4>\n<p>El TAD de los conjuntos se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3kM3HfP\">Conjunto.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.Conjunto\n  (Conj,\n   vacio,     -- Conj a\n   inserta,   -- Ord a => a -> Conj a -> Conj a\n   menor,     -- Ord a => Conj a -> a\n   elimina,   -- Ord a => a -> Conj a -> Conj a\n   pertenece, -- Ord a => a -> Conj a -> Bool\n   esVacio    -- Conj a -> Bool\n  ) where\n\nimport TAD.ConjuntoConListasNoOrdenadasConDuplicados\n-- import TAD.ConjuntoConListasNoOrdenadasSinDuplicados\n-- import TAD.ConjuntoConListasOrdenadasSinDuplicados\n-- import TAD.ConjuntosConLibreria\n<\/pre>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos las siguientes:<\/p>\n<ul>\n<li>mediante listas no ordenadas con duplicados,<\/li>\n<li>mediante listas no ordenadas sin duplicados,<\/li>\n<li>mediante listas ordenadas sin duplicados y<\/li>\n<li>mediante la librer\u00eda de conjuntos.<\/li>\n<\/ul>\n<h4>2.2. Implementaci\u00f3n de los conjuntos mediante listas no ordenadas con duplicados<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3Dodqzf\">ConjuntoConListasNoOrdenadasConDuplicados.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.ConjuntoConListasNoOrdenadasConDuplicados\n  (Conj,\n   vacio,     -- Conj a\n   inserta,   -- Ord a => a -> Conj a -> Conj a\n   menor,     -- Ord a => Conj a -> a\n   elimina,   -- Ord a => a -> Conj a -> Conj a\n   pertenece, -- Ord a => a -> Conj a -> Bool\n   esVacio    -- Conj a -> Bool\n  ) where\n\nimport Data.List (intercalate, nub, sort)\nimport Test.QuickCheck\n\n-- Conjuntos como listas no ordenadas con repeticiones:\nnewtype Conj a = Cj [a]\n\n-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por\n-- ejemplo,\n--    \u03bb> escribeConjunto (Cj [])\n--    \"{}\"\n--    \u03bb> escribeConjunto (Cj [5])\n--    \"{5}\"\n--    \u03bb> escribeConjunto (Cj [2, 5])\n--    \"{2, 5}\"\n--    \u03bb> escribeConjunto (Cj [5, 2, 5])\n--    \"{2, 5}\"\nescribeConjunto :: (Show a, Ord a) => Conj a -> String\nescribeConjunto (Cj xs) =\n  \"{\" ++ intercalate \", \" (map show (sort (nub xs))) ++ \"}\"\n\n-- Procedimiento de escritura de conjuntos.\ninstance (Show a, Ord a) => Show (Conj a) where\n  show = escribeConjunto\n\n-- Nota: Aunque el conjunto no est\u00e1 ordenado y tenga repeticiones, al\n-- escribirlo se har\u00e1 sin repeticiones y ordenando sus elementos.\n\n-- vacio es el conjunto vac\u00edo. Por ejemplo,\n--    \u03bb> vacio\n--    {}\nvacio :: Conj a\nvacio = Cj []\n\n-- (inserta x c) es el conjunto obtenido a\u00f1adiendo el elemento x al\n-- conjunto c. Por ejemplo,\n--    \u03bb> inserta 5 vacio\n--    {5}\n--    \u03bb> inserta 2 (inserta 5 vacio)\n--    {2, 5}\n--    \u03bb> inserta 5 (inserta 2 vacio)\n--    {2, 5}\ninserta :: Eq a => a -> Conj a -> Conj a\ninserta x (Cj ys) = Cj (x:ys)\n\n-- (menor c) es el menor elemento del conjunto c. Por ejemplo,\n--    \u03bb> menor (inserta 5 (inserta 2 vacio))\n--    2\nmenor :: Ord a => Conj a -> a\nmenor (Cj []) = error \"conjunto vac\u00edo\"\nmenor (Cj xs) = minimum xs\n\n-- (elimina x c) es el conjunto obtenido eliminando el elemento x\n-- del conjunto c. Por ejemplo,\n--    \u03bb> elimina 2 (inserta 5 (inserta 2 vacio))\n--    {5}\nelimina :: Eq a => a -> Conj a -> Conj a\nelimina x (Cj ys) = Cj (filter (\/= x) ys)\n\n-- (esVacio c) se verifica si c es el conjunto vac\u00edo. Por ejemplo,\n--    \u03bb> esVacio (inserta 5 (inserta 2 vacio))\n--    False\n--    \u03bb> esVacio vacio\n--    True\nesVacio :: Conj a -> Bool\nesVacio (Cj xs) = null xs\n\n-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,\n--    \u03bb> pertenece 2 (inserta 5 (inserta 2 vacio))\n--    True\n--    \u03bb> pertenece 4 (inserta 5 (inserta 2 vacio))\n--    False\npertenece :: Eq a => a -> Conj a -> Bool\npertenece x (Cj xs) = x `elem` xs\n\n-- (subconjunto c1 c2) se verifica si c1 es un subconjunto de c2. Por\n-- ejemplo,\n--    subconjunto (Cj [1,3,2,1]) (Cj [3,1,3,2])  ==  True\n--    subconjunto (Cj [1,3,4,1]) (Cj [3,1,3,2])  ==  False\nsubconjunto :: Ord a => Conj a -> Conj a -> Bool\nsubconjunto (Cj xs) (Cj ys) = sublista xs ys\n  where sublista [] _      = True\n        sublista (z:zs) vs = elem z vs && sublista zs vs\n\n-- (igualConjunto c1 c2) se verifica si los conjuntos c1 y c2 son\n-- iguales. Por ejemplo,\n--    igualConjunto (Cj [1,3,2,1]) (Cj [3,1,3,2])  ==  True\n--    igualConjunto (Cj [1,3,4,1]) (Cj [3,1,3,2])  ==  False\nigualConjunto :: Ord a => Conj a -> Conj a -> Bool\nigualConjunto c c' =\n  subconjunto c c' && subconjunto c' c\n\n--- Los conjuntos son comparables por igualdad.\ninstance Ord a => Eq (Conj a) where\n  (==) = igualConjunto\n\n-- Generador de conjuntos                                          --\n-- ======================\n\n-- genConjunto es un generador de conjuntos. Por ejemplo,\n--    \u03bb> sample (genConjunto :: Gen (Conj Int))\n--    {}\n--    {1}\n--    {0, 2, 3}\n--    {-6, 5}\n--    {2, 5}\n--    {-9, -6, 4, 8}\n--    {0, 1}\n--    {-13, -11, -5, -2, -1, 0, 4, 6, 7, 8, 9, 14}\n--    {-7, -5, -2, -1, 1, 2, 10, 13, 15}\n--    {-18, -17, -16, -10, -9, 0, 1, 3, 4, 13, 16}\n--    {-20, -15, -7, -1, 2, 8, 10, 15, 20}\ngenConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)\ngenConjunto = do\n  xs <- listOf arbitrary\n  return (foldr inserta vacio xs)\n\n-- Los conjuntos son concreciones de los arbitrarios.\ninstance (Arbitrary a, Ord a) => Arbitrary (Conj a) where\n  arbitrary = genConjunto\n\n-- Propiedades de los conjuntos                                        --\n-- ============================\n\nprop_conjuntos :: Int -> Int -> Conj Int -> Bool\nprop_conjuntos x y c =\n  inserta x (inserta x c) == inserta x c &&\n  inserta x (inserta y c) == inserta y (inserta x c) &&\n  not (pertenece x vacio) &&\n  pertenece y (inserta x c) == (x == y) || pertenece y c &&\n  elimina x vacio == vacio &&\n  elimina x (inserta y c) == (if x == y\n                              then elimina x c\n                              else inserta y (elimina x c)) &&\n  esVacio (vacio :: Conj Int) &&\n  not (esVacio (inserta x c))\n\n-- Comprobaci\u00f3n\n--    \u03bb> quickCheck prop_conjuntos\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>2.3. Implementaci\u00f3n de los conjuntos mediante listas no ordenadas sin duplicados<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3HeojVD\">ConjuntoConListasNoOrdenadasSinDuplicados.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.ConjuntoConListasNoOrdenadasSinDuplicados\n  (Conj,\n   vacio,     -- Conj a\n   inserta,   -- Ord a => a -> Conj a -> Conj a\n   menor,     -- Ord a => Conj a -> a\n   elimina,   -- Ord a => a -> Conj a -> Conj a\n   pertenece, -- Ord a => a -> Conj a -> Bool\n   esVacio    -- Conj a -> Bool\n  ) where\n\nimport Data.List (intercalate, sort)\nimport Test.QuickCheck\n\n-- Los conjuntos como listas no ordenadas sin repeticiones.\nnewtype Conj a = Cj [a]\n\n-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por\n-- ejemplo,\n--    \u03bb> escribeConjunto (Cj [])\n--    \"{}\"\n--    \u03bb> escribeConjunto (Cj [5])\n--    \"{5}\"\n--    \u03bb> escribeConjunto (Cj [2, 5])\n--    \"{2, 5}\"\n--    \u03bb> escribeConjunto (Cj [5, 2])\n--    \"{2, 5}\"\nescribeConjunto :: (Show a, Ord a) => Conj a -> String\nescribeConjunto (Cj xs) =\n  \"{\" ++ intercalate \", \" (map show (sort xs)) ++ \"}\"\n\n-- Procedimiento de escritura de conjuntos.\ninstance (Show a, Ord a) => Show (Conj a) where\n  show = escribeConjunto\n\n-- vacio es el conjunto vac\u00edo. Por ejemplo,\n--    \u03bb> vacio\n--    {}\nvacio :: Conj a\nvacio = Cj []\n\n-- (inserta x c) es el conjunto obtenido a\u00f1adiendo el elemento x al\n-- conjunto c. Por ejemplo,\n--    \u03bb> inserta 5 vacio\n--    {5}\n--    \u03bb> inserta 2 (inserta 5 vacio)\n--    {2, 5}\n--    \u03bb> inserta 5 (inserta 2 vacio)\n--    {2, 5}\ninserta :: Eq a => a -> Conj a -> Conj a\ninserta x s@(Cj xs) | pertenece x s = s\n                    | otherwise     = Cj (x:xs)\n\n-- (menor c) es el menor elemento del conjunto c. Por ejemplo,\n--    \u03bb> menor (inserta 5 (inserta 2 vacio))\n--    2\nmenor :: Ord a => Conj a -> a\nmenor (Cj []) = error \"conjunto vac\u00edo\"\nmenor (Cj xs) = minimum xs\n\n-- (elimina x c) es el conjunto obtenido eliminando el elemento x\n-- del conjunto c. Por ejemplo,\n--    \u03bb> elimina 2 (inserta 5 (inserta 2 vacio))\n--    {5}\nelimina :: Eq a => a -> Conj a -> Conj a\nelimina x (Cj s) = Cj [y | y <- s, y \/= x]\n\n-- (esVacio c) se verifica si c es el conjunto vac\u00edo. Por ejemplo,\n--    \u03bb> esVacio (inserta 5 (inserta 2 vacio))\n--    False\n--    \u03bb> esVacio vacio\n--    True\nesVacio :: Conj a -> Bool\nesVacio (Cj xs) = null xs\n\n-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,\n--    \u03bb> pertenece 2 (inserta 5 (inserta 2 vacio))\n--    True\n--    \u03bb> pertenece 4 (inserta 5 (inserta 2 vacio))\n--    False\npertenece :: Eq a => a -> Conj a -> Bool\npertenece x (Cj xs) = x `elem` xs\n\n-- (subconjunto c1 c2) se verifica si c1 es un subconjunto de c2. Por\n-- ejemplo,\n--    subconjunto (Cj [1,3,2]) (Cj [3,1,2])    ==  True\n--    subconjunto (Cj [1,3,4,1]) (Cj [1,3,2])  ==  False\nsubconjunto :: Ord a => Conj a -> Conj a -> Bool\nsubconjunto (Cj xs) (Cj ys) = sublista xs ys\n  where sublista [] _      = True\n        sublista (z:zs) vs = elem z vs && sublista zs vs\n\n-- (igualConjunto c1 c2) se verifica si los conjuntos c1 y c2 son\n-- iguales. Por ejemplo,\n--    igualConjunto (Cj [3,2,1]) (Cj [1,3,2])  ==  True\n--    igualConjunto (Cj [1,3,4]) (Cj [1,3,2])  ==  False\nigualConjunto :: Ord a => Conj a -> Conj a -> Bool\nigualConjunto c c' =\n  subconjunto c c' && subconjunto c' c\n\n--- Los conjuntos son comparables por igualdad.\ninstance Ord a => Eq (Conj a) where\n  (==) = igualConjunto\n\n-- Generador de conjuntos                                          --\n-- ======================\n\n-- genConjunto es un generador de conjuntos. Por ejemplo,\n--    \u03bb> sample (genConjunto :: Gen (Conj Int))\n--    {}\n--    {-1, 0}\n--    {-4, 1, 2}\n--    {-3, 0, 2, 3, 4}\n--    {-7}\n--    {-10, -7, -5, -2, -1, 2, 5, 8}\n--    {5, 7, 8, 10}\n--    {-9, -6, -3, 8}\n--    {-8, -6, -5, -1, 7, 9, 14}\n--    {-18, -15, -14, -13, -3, -2, 1, 2, 4, 8, 12, 17}\n--    {-17, -16, -13, -12, -11, -9, -6, -3, 0, 1, 3, 5, 6, 7, 16, 18}\ngenConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)\ngenConjunto = do\n  xs <- listOf arbitrary\n  return (foldr inserta vacio xs)\n\n-- Los conjuntos son concreciones de los arbitrarios.\ninstance (Arbitrary a, Ord a) => Arbitrary (Conj a) where\n  arbitrary = genConjunto\n\n-- Propiedades de los conjuntos                                        --\n-- ============================\n\nprop_conjuntos :: Int -> Int -> Conj Int -> Bool\nprop_conjuntos x y c =\n  inserta x (inserta x c) == inserta x c &&\n  inserta x (inserta y c) == inserta y (inserta x c) &&\n  not (pertenece x vacio) &&\n  pertenece y (inserta x c) == (x == y) || pertenece y c &&\n  elimina x vacio == vacio &&\n  elimina x (inserta y c) == (if x == y\n                              then elimina x c\n                              else inserta y (elimina x c)) &&\n  esVacio (vacio :: Conj Int) &&\n  not (esVacio (inserta x c))\n\n-- Comprobaci\u00f3n\n--    \u03bb> quickCheck prop_conjuntos\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>2.4. Implementaci\u00f3n de los conjuntos mediante listas ordenadas sin repeticiones<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3HFEtbZ\">ConjuntoConListasOrdenadasSinDuplicados.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.ConjuntoConListasOrdenadasSinDuplicados\n  (Conj,\n   vacio,     -- Conj a\n   inserta,   -- Ord a => a -> Conj a -> Conj a\n   menor,     -- Ord a => Conj a -> a\n   elimina,   -- Ord a => a -> Conj a -> Conj a\n   pertenece, -- Ord a => a -> Conj a -> Bool\n   esVacio    -- Conj a -> Bool\n  ) where\n\nimport Data.List (intercalate)\nimport Test.QuickCheck\n\n-- Los conjuntos como listas ordenadas sin repeticiones.\nnewtype Conj a = Cj [a]\n  deriving Eq\n\n-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por\n-- ejemplo,\n--    \u03bb> escribeConjunto (Cj [])\n--    \"{}\"\n--    \u03bb> escribeConjunto (Cj [5])\n--    \"{5}\"\n--    \u03bb> escribeConjunto (Cj [2, 5])\n--    \"{2, 5}\"\n--    \u03bb> escribeConjunto (Cj [5, 2])\n--    \"{2, 5}\"\nescribeConjunto :: Show a => Conj a -> String\nescribeConjunto (Cj xs) =\n  \"{\" ++ intercalate \", \" (map show xs) ++ \"}\"\n\n-- Procedimiento de escritura de conjuntos.\ninstance Show a => Show (Conj a) where\n  show = escribeConjunto\n\n-- vacio es el conjunto vac\u00edo. Por ejemplo,\n--    \u03bb> vacio\n--    {}\nvacio :: Conj a\nvacio = Cj []\n\n-- (inserta x c) es el conjunto obtenido a\u00f1adiendo el elemento x al\n-- conjunto c. Por ejemplo,\n--    \u03bb> inserta 5 vacio\n--    {5}\n--    \u03bb> inserta 2 (inserta 5 vacio)\n--    {2, 5}\n--    \u03bb> inserta 5 (inserta 2 vacio)\n--    {2, 5}\ninserta :: Ord a => a -> Conj a -> Conj a\ninserta x (Cj s) = Cj (agrega x s)\n  where agrega z []                     = [z]\n        agrega z s'@(y:ys) | z > y      = y : agrega z ys\n                           | z < y      = z : s'\n                           | otherwise  = s'\n\n-- (menor c) es el menor elemento del conjunto c. Por ejemplo,\n--    \u03bb> menor (inserta 5 (inserta 2 vacio))\n--    2\nmenor :: Ord a => Conj a -> a\nmenor (Cj [])    = error \"conjunto vac\u00edo\"\nmenor (Cj (x:_)) = x\n\n-- (elimina x c) es el conjunto obtenido eliminando el elemento x\n-- del conjunto c. Por ejemplo,\n--    \u03bb> elimina 2 (inserta 5 (inserta 2 vacio))\n--    {5}\nelimina :: Ord a => a -> Conj a -> Conj a\nelimina x (Cj s) = Cj (elimina' x s)\n  where elimina' _ []                    = []\n        elimina' z s'@(y:ys) | z > y     = y : elimina' z ys\n                             | z < y     = s'\n                             | otherwise = ys\n\n-- (esVacio c) se verifica si c es el conjunto vac\u00edo. Por ejemplo,\n--    \u03bb> esVacio (inserta 5 (inserta 2 vacio))\n--    False\n--    \u03bb> esVacio vacio\n--    True\nesVacio :: Conj a -> Bool\nesVacio (Cj xs) = null xs\n\n-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,\n--    \u03bb> pertenece 2 (inserta 5 (inserta 2 vacio))\n--    True\n--    \u03bb> pertenece 4 (inserta 5 (inserta 2 vacio))\n--    False\npertenece :: Ord a => a -> Conj a -> Bool\npertenece x (Cj s) = x `elem` takeWhile (<= x) s\n\n-- Generador de conjuntos                                          --\n-- ======================\n\n-- genConjunto es un generador de conjuntos. Por ejemplo,\n--    \u03bb> sample (genConjunto :: Gen (Conj Int))\n--    {}\n--    {1}\n--    {2}\n--    {}\n--    {-5, -1}\n--    {-9, -8, 2, 3, 10}\n--    {4}\n--    {-13, -7, 1, 14}\n--    {-12, -10, -9, -4, 1, 2, 5, 14, 16}\n--    {-18, -15, -14, -13, -10, -7, -6, -4, -1, 1, 10, 11, 12, 16}\n--    {-16, -9, -6, -5, -4, -2, 3, 6, 9, 13, 17}\ngenConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)\ngenConjunto = do\n  xs <- listOf arbitrary\n  return (foldr inserta vacio xs)\n\n-- Los conjuntos son concreciones de los arbitrarios.\ninstance (Arbitrary a, Ord a) => Arbitrary (Conj a) where\n  arbitrary = genConjunto\n\n-- Propiedades de los conjuntos                                        --\n-- ============================\n\nprop_conjuntos :: Int -> Int -> Conj Int -> Bool\nprop_conjuntos x y c =\n  inserta x (inserta x c) == inserta x c &&\n  inserta x (inserta y c) == inserta y (inserta x c) &&\n  not (pertenece x vacio) &&\n  pertenece y (inserta x c) == (x == y) || pertenece y c &&\n  elimina x vacio == vacio &&\n  elimina x (inserta y c) == (if x == y\n                              then elimina x c\n                              else inserta y (elimina x c)) &&\n  esVacio (vacio :: Conj Int) &&\n  not (esVacio (inserta x c))\n\n-- Comprobaci\u00f3n\n--    \u03bb> quickCheck prop_conjuntos\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>2.5. Implementaci\u00f3n de los conjuntos mediante librer\u00eda<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3HeBCFr\">ConjuntoConLibreria.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.ConjuntoConLibreria\n  (Conj,\n   vacio,     -- Conj a\n   inserta,   -- Ord a => a -> Conj a -> Conj a\n   menor,     -- Ord a => Conj a -> a\n   elimina,   -- Ord a => a -> Conj a -> Conj a\n   pertenece, -- Ord a => a -> Conj a -> Bool\n   esVacio    -- Conj a -> Bool\n  ) where\n\nimport Data.Set as S (Set, empty, insert, findMin, delete, member, null,\n                      fromList, toList)\nimport Data.List (intercalate)\nimport Test.QuickCheck\n\n-- Los conjuntos como conjuntos de la librer\u00eda Data.Set\nnewtype Conj a = Cj (Set a)\n  deriving (Eq, Ord)\n\n-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por\n-- ejemplo,\n--    \u03bb> escribeConjunto (Cj (fromList []))\n--    \"{}\"\n--    \u03bb> escribeConjunto (Cj (fromList [5]))\n--    \"{5}\"\n--    \u03bb> escribeConjunto (Cj (fromList [2, 5]))\n--    \"{2, 5}\"\n--    \u03bb> escribeConjunto (Cj (fromList [5, 2]))\n--    \"{2, 5}\"\nescribeConjunto :: Show a => Conj a -> String\nescribeConjunto (Cj s) =\n  \"{\" ++ intercalate \", \" (map show (toList s)) ++ \"}\"\n\n-- Procedimiento de escritura de conjuntos.\ninstance Show a => Show (Conj a) where\n  show = escribeConjunto\n\n-- vacio es el conjunto vac\u00edo. Por ejemplo,\n--    \u03bb> vacio\n--    {}\nvacio :: Conj a\nvacio = Cj empty\n\n-- (inserta x c) es el conjunto obtenido a\u00f1adiendo el elemento x al\n-- conjunto c. Por ejemplo,\n--    \u03bb> inserta 5 vacio\n--    {5}\n--    \u03bb> inserta 2 (inserta 5 vacio)\n--    {2, 5}\n--    \u03bb> inserta 5 (inserta 2 vacio)\n--    {2, 5}\ninserta :: Ord a => a -> Conj a -> Conj a\ninserta x (Cj s) = Cj (insert x s)\n\n-- (menor c) es el menor elemento del conjunto c. Por ejemplo,\n--    \u03bb> menor (inserta 5 (inserta 2 vacio))\n--    2\nmenor :: Ord a => Conj a -> a\nmenor (Cj s) = findMin s\n\n-- (elimina x c) es el conjunto obtenido eliminando el elemento x\n-- del conjunto c. Por ejemplo,\n--    \u03bb> elimina 2 (inserta 5 (inserta 2 vacio))\n--    {5}\nelimina :: Ord a => a -> Conj a -> Conj a\nelimina x (Cj s) = Cj (delete x s)\n\n-- (esVacio c) se verifica si c es el conjunto vac\u00edo. Por ejemplo,\n--    \u03bb> esVacio (inserta 5 (inserta 2 vacio))\n--    False\n--    \u03bb> esVacio vacio\n--    True\nesVacio :: Conj a -> Bool\nesVacio (Cj s) = S.null s\n\n-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,\n--    \u03bb> pertenece 2 (inserta 5 (inserta 2 vacio))\n--    True\n--    \u03bb> pertenece 4 (inserta 5 (inserta 2 vacio))\n--    False\npertenece :: Ord a => a -> Conj a -> Bool\npertenece x (Cj s) = member x s\n\n-- Generador de conjuntos                                          --\n-- ======================\n\n-- genConjunto es un generador de conjuntos. Por ejemplo,\n--    \u03bb> sample (genConjunto :: Gen (Conj Int))\n--    {}\n--    {-2, 0}\n--    {-1, 3}\n--    {-3, 2}\n--    {-5, -4, -3, 2, 4, 6, 7}\n--    {-4, 4}\n--    {-9, -6, -3, 1, 5, 11, 12}\n--    {-10, -8, -7, -3, 1, 2, 8, 9, 10, 13}\n--    {-13, -8, -7, -6, -1, 0, 1, 6, 7, 9, 11, 14, 16}\n--    {-15, -12, -9, 1, 2, 9, 13, 15, 16, 18}\n--    {-16}\ngenConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)\ngenConjunto = do\n  xs <- listOf arbitrary\n  return (Cj (fromList xs))\n\n-- Los conjuntos son concreciones de los arbitrarios.\ninstance (Arbitrary a, Ord a) => Arbitrary (Conj a) where\n  arbitrary = genConjunto\n\n-- Propiedades de los conjuntos                                        --\n-- ============================\n\nprop_conjuntos :: Int -> Int -> Conj Int -> Bool\nprop_conjuntos x y c =\n  inserta x (inserta x c) == inserta x c &&\n  inserta x (inserta y c) == inserta y (inserta x c) &&\n  not (pertenece x vacio) &&\n  pertenece y (inserta x c) == (x == y) || pertenece y c &&\n  elimina x vacio == vacio &&\n  elimina x (inserta y c) == (if x == y\n                              then elimina x c\n                              else inserta y (elimina x c)) &&\n  esVacio (vacio :: Conj Int) &&\n  not (esVacio (inserta x c))\n\n-- Comprobaci\u00f3n\n--    \u03bb> quickCheck prop_conjuntos\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h3>3. Los conjuntos en Python<\/h3>\n<h4>3.1. El tipo abstracto de los conjuntos en Python<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/40aLTv6\">conjunto.py<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"python\">\n__all__ = [\n    'Conj',\n    'vacio',\n    'inserta',\n    'menor',\n    'elimina',\n    'pertenece',\n    'esVacio',\n    'conjuntoAleatorio'\n]\n\n# from src.TAD.conjuntoConListasNoOrdenadasConDuplicados import (\n#     Conj, conjuntoAleatorio, elimina, esVacio, inserta,\n#     menor, pertenece, vacio)\n\n# from src.TAD.conjuntoConListasNoOrdenadasSinDuplicados import (\n#     Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,\n#     vacio)\n\nfrom src.TAD.conjuntoConListasOrdenadasSinDuplicados import (\n    Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,\n    vacio)\n\n# from src.TAD.conjuntoConLibreria import (\n#     Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,\n#     vacio)\n<\/pre>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos las siguientes:<\/p>\n<ul>\n<li>mediante listas no ordenadas con duplicados,<\/li>\n<li>mediante listas no ordenadas sin duplicados,<\/li>\n<li>mediante listas ordenadas sin duplicados y<\/li>\n<li>mediante la librer\u00eda de conjuntos.<\/li>\n<\/ul>\n<h4>3.2. Implementaci\u00f3n de los conjuntos mediante listas no ordenadas con duplicados<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3kxW4JT\">conjuntoConListasNoOrdenadasConDuplicados.py<\/a> en el que se define la clase Conj con los siguientes m\u00e9todos:<\/p>\n<ul>\n<li>inserta(x) a\u00f1ade x al conjunto.<\/li>\n<li>menor() es el menor elemento del conjunto.<\/li>\n<li>elimina(x) elimina las ocurrencias de x en el conjunto.<\/li>\n<li>pertenece(x) se verifica si x pertenece al conjunto.<\/li>\n<li>esVacia() se verifica si la cola es vac\u00eda.<\/li>\n<\/ul>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\">\n   >>> c = Conj()\n   >>> c\n   {}\n   >>> c.inserta(5)\n   >>> c.inserta(2)\n   >>> c.inserta(3)\n   >>> c.inserta(4)\n   >>> c.inserta(5)\n   >>> c\n   {2, 3, 4, 5}\n   >>> c.menor()\n   2\n   >>> c.elimina(3)\n   >>> c\n   {2, 4, 5}\n   >>> c.pertenece(4)\n   True\n   >>> c.pertenece(3)\n   False\n   >>> c.esVacio()\n   False\n   >>> c = Conj()\n   >>> c.esVacio()\n   True\n   >>> c = Conj()\n   >>> c.inserta(2)\n   >>> c.inserta(5)\n   >>> d = Conj()\n   >>> d.inserta(5)\n   >>> d.inserta(2)\n   >>> d.inserta(5)\n   >>> c == d\n   True\n<\/pre>\n<p>Adem\u00e1s se definen las correspondientes funciones. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   >>> vacio()\n   {}\n   >>> inserta(5, inserta(3, inserta(2, inserta(5, vacio()))))\n   {2, 3, 5}\n   >>> menor(inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))\n   2\n   >>> elimina(5, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))\n   {2, 3}\n   >>> pertenece(5, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))\n   True\n   >>> pertenece(1, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))\n   False\n   >>> esVacio(inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))\n   False\n   >>> esVacio(vacio())\n   True\n   >>> inserta(5, inserta(2, vacio())) == inserta(2, inserta(5, (inserta(2, vacio()))))\n   True\n<\/pre>\n<p>Finalmente, se define un generador aleatorio de conjuntos y se comprueba que los conjuntos cumplen las propiedades de su especificaci\u00f3n.<\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\n__all__ = [\n    'Conj',\n    'vacio',\n    'inserta',\n    'menor',\n    'elimina',\n    'pertenece',\n    'esVacio',\n    'conjuntoAleatorio'\n]\n\nfrom abc import abstractmethod\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Any, Generic, Protocol, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nclass Comparable(Protocol):\n    @abstractmethod\n    def __lt__(self: A, otro: A) -> bool:\n        pass\n\nA = TypeVar('A', bound=Comparable)\n\n# Clase de los conjuntos mediante listas no ordenadas con duplicados\n# ==================================================================\n\n@dataclass\nclass Conj(Generic[A]):\n    _elementos: list[A] = field(default_factory=list)\n\n    def __repr__(self) -> str:\n        \"\"\"\n        Devuelve una cadena con los elementos del conjunto entre llaves\n        y separados por \", \".\n        \"\"\"\n        return '{' + ', '.join(str(x) for x in sorted(list(set(self._elementos)))) + '}'\n\n    def __eq__(self, c: Any) -> bool:\n        \"\"\"\n        Se verifica si el conjunto es igual a c; es decir, tienen los\n        mismos elementos sin importar el orden ni las repeticiones.\n        \"\"\"\n        return sorted(list(set(self._elementos))) == sorted(list(set(c._elementos)))\n\n    def inserta(self, x: A) -> None:\n        \"\"\"\n        A\u00f1ade el elemento x al conjunto.\n        \"\"\"\n        self._elementos.append(x)\n\n    def menor(self) -> A:\n        \"\"\"\n        Devuelve el menor elemento del conjunto\n        \"\"\"\n        return min(self._elementos)\n\n    def elimina(self, x: A) -> None:\n        \"\"\"\n        Elimina el elemento x del conjunto.\n        \"\"\"\n        while x in self._elementos:\n            self._elementos.remove(x)\n\n    def esVacio(self) -> bool:\n        \"\"\"\n        Se verifica si el conjunto est\u00e1 vac\u00edo.\n        \"\"\"\n        return not self._elementos\n\n    def pertenece(self, x: A) -> bool:\n        \"\"\"\n        Se verifica si x pertenece al conjunto.\n        \"\"\"\n        return x in self._elementos\n\n# Funciones del tipo conjunto\n# ===========================\n\ndef vacio() -> Conj[A]:\n    \"\"\"\n    Crea y devuelve un conjunto vac\u00edo de tipo A.\n    \"\"\"\n    c: Conj[A] = Conj()\n    return c\n\ndef inserta(x: A, c: Conj[A]) -> Conj[A]:\n    \"\"\"\n    Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto\n    con el elemento insertado.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.inserta(x)\n    return _aux\n\ndef menor(c: Conj[A]) -> A:\n    \"\"\"\n    Devuelve el menor elemento del conjunto c.\n    \"\"\"\n    return c.menor()\n\ndef elimina(x: A, c: Conj[A]) -> Conj[A]:\n    \"\"\"\n    Elimina las ocurrencias de c en c y devuelve una copia del conjunto\n    resultante.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.elimina(x)\n    return _aux\n\ndef pertenece(x: A, c: Conj[A]) -> bool:\n    \"\"\"\n    Se verifica si x pertenece a c.\n    \"\"\"\n    return c.pertenece(x)\n\ndef esVacio(c: Conj[A]) -> bool:\n    \"\"\"\n    Se verifica si el conjunto est\u00e1 vac\u00edo.\n    \"\"\"\n    return c.esVacio()\n\n# Generador de conjuntos\n# ======================\n\ndef conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:\n    \"\"\"\n    Genera una estrategia de b\u00fasqueda para generar conjuntos de enteros\n    de forma aleatoria.\n\n    Utiliza la librer\u00eda Hypothesis para generar una lista de enteros y\n    luego se convierte en una instancia de la clase cola.\n    \"\"\"\n    return st.lists(st.integers()).map(Conj)\n\n# Comprobaci\u00f3n de las propiedades de los conjuntos\n# ================================================\n\n# Las propiedades son\n@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())\ndef test_conjuntos(c: Conj[int], x: int, y: int) -> None:\n    v: Conj[int] = vacio()\n    assert inserta(x, inserta(x, c)) == inserta(x, c)\n    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))\n    assert not pertenece(x, v)\n    assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)\n    assert elimina(x, v) == v\n\n    def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:\n        if x == y:\n            return elimina(x, c)\n        return inserta(y, elimina(x, c))\n\n    assert elimina(x, inserta(y, c)) == relacion(x, y, c)\n    assert esVacio(vacio())\n    assert not esVacio(inserta(x, c))\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q conjuntoConListasNoOrdenadasConDuplicados.py\n#    1 passed in 0.33s\n<\/pre>\n<h4>3.3. Implementaci\u00f3n de los conjuntos mediante listas no ordenadas sin duplicados<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3WN4AlH\">conjuntoConListasNoOrdenadasSinDuplicados.py<\/a> cuyo contenido es<\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\n__all__ = [\n    'Conj',\n    'vacio',\n    'inserta',\n    'menor',\n    'elimina',\n    'pertenece',\n    'esVacio',\n    'conjuntoAleatorio'\n]\n\nfrom abc import abstractmethod\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Any, Generic, Protocol, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nclass Comparable(Protocol):\n    @abstractmethod\n    def __lt__(self: A, otro: A) -> bool:\n        pass\n\nA = TypeVar('A', bound=Comparable)\n\n# Clase de los conjuntos mediante listas no ordenadas sin duplicados\n# ==================================================================\n\n@dataclass\nclass Conj(Generic[A]):\n    _elementos: list[A] = field(default_factory=list)\n\n    def __repr__(self) -> str:\n        \"\"\"\n        Devuelve una cadena con los elementos del conjunto entre llaves\n        y separados por \", \".\n        \"\"\"\n        return '{' + ', '.join(str(x) for x in sorted(self._elementos)) + '}'\n\n    def __eq__(self, c: Any) -> bool:\n        \"\"\"\n        Se verifica si el conjunto es igual a c; es decir, tienen los\n        mismos elementos sin importar el orden ni las repeticiones.\n        \"\"\"\n        return sorted(self._elementos) == sorted(c._elementos)\n\n    def inserta(self, x: A) -> None:\n        \"\"\"\n        A\u00f1ade el elemento x al conjunto.\n        \"\"\"\n        if x not in self._elementos:\n            self._elementos.append(x)\n\n    def menor(self) -> A:\n        \"\"\"\n        Devuelve el menor elemento del conjunto\n        \"\"\"\n        return min(self._elementos)\n\n    def elimina(self, x: A) -> None:\n        \"\"\"\n        Elimina el elemento x del conjunto.\n        \"\"\"\n        if x in self._elementos:\n            self._elementos.remove(x)\n\n    def esVacio(self) -> bool:\n        \"\"\"\n        Se verifica si el conjunto est\u00e1 vac\u00edo.\n        \"\"\"\n        return not self._elementos\n\n    def pertenece(self, x: A) -> bool:\n        \"\"\"\n        Se verifica si x pertenece al conjunto.\n        \"\"\"\n        return x in self._elementos\n\n# Funciones del tipo conjunto\n# ===========================\n\ndef vacio() -> Conj[A]:\n    \"\"\"\n    Crea y devuelve un conjunto vac\u00edo de tipo A.\n    \"\"\"\n    c: Conj[A] = Conj()\n    return c\n\ndef inserta(x: A, c: Conj[A]) -> Conj[A]:\n    \"\"\"\n    Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto\n    con el elemento insertado.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.inserta(x)\n    return _aux\n\ndef menor(c: Conj[A]) -> A:\n    \"\"\"\n    Devuelve el menor elemento del conjunto c.\n    \"\"\"\n    return c.menor()\n\ndef elimina(x: A, c: Conj[A]) -> Conj[A]:\n    \"\"\"\n    Elimina las ocurrencias de c en c y devuelve una copia del conjunto\n    resultante.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.elimina(x)\n    return _aux\n\ndef pertenece(x: A, c: Conj[A]) -> bool:\n    \"\"\"\n    Se verifica si x pertenece a c.\n    \"\"\"\n    return c.pertenece(x)\n\ndef esVacio(c: Conj[A]) -> bool:\n    \"\"\"\n    Se verifica si el conjunto est\u00e1 vac\u00edo.\n    \"\"\"\n    return c.esVacio()\n\n# Generador de conjuntos\n# ======================\n\ndef sin_duplicados(xs: list[int]) -> list[int]:\n    return list(set(xs))\n\ndef conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:\n    \"\"\"\n    Estrategia de b\u00fasqueda para generar conjuntos de enteros de forma\n    aleatoria.\n    \"\"\"\n    xs = st.lists(st.integers()).map(sin_duplicados)\n    return xs.map(Conj)\n\n# Comprobaci\u00f3n de las propiedades de los conjuntos\n# ================================================\n\n# Las propiedades son\n@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())\ndef test_conjuntos(c: Conj[int], x: int, y: int) -> None:\n    assert inserta(x, inserta(x, c)) == inserta(x, c)\n    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))\n    assert not pertenece(x, vacio())\n    assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)\n    assert elimina(x, vacio()) == vacio()\n\n    def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:\n        if x == y:\n            return elimina(x, c)\n        return inserta(y, elimina(x, c))\n\n    assert elimina(x, inserta(y, c)) == relacion(x, y, c)\n    assert esVacio(vacio())\n    assert not esVacio(inserta(x, c))\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q conjuntoConListasNoOrdenadasSinDuplicados.py\n#    1 passed in 0.26s\n<\/pre>\n<h4>3.4. Implementaci\u00f3n de los conjuntos mediante listas ordenadas sin duplicados<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3XNETT9\">conjuntoConListasOrdenadasSinDuplicados.py<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\n__all__ = [\n    'Conj',\n    'vacio',\n    'inserta',\n    'menor',\n    'elimina',\n    'pertenece',\n    'esVacio',\n    'conjuntoAleatorio'\n]\n\nfrom abc import abstractmethod\nfrom bisect import bisect_left, insort_left\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom itertools import takewhile\nfrom typing import Generic, Protocol, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nclass Comparable(Protocol):\n    @abstractmethod\n    def __lt__(self: A, otro: A) -> bool:\n        pass\n\nA = TypeVar('A', bound=Comparable)\n\n# Clase de los conjuntos mediante listas ordenadas sin duplicados\n# ===============================================================\n\n@dataclass\nclass Conj(Generic[A]):\n    _elementos: list[A] = field(default_factory=list)\n\n    def __repr__(self) -> str:\n        \"\"\"\n        Devuelve una cadena con los elementos del conjunto entre llaves\n        y separados por \", \".\n        \"\"\"\n        return '{' + ', '.join(str(x) for x in self._elementos) + '}'\n\n    def inserta(self, x: A) -> None:\n        \"\"\"\n        A\u00f1ade el elemento x al conjunto.\n        \"\"\"\n        if x not in self._elementos:\n            insort_left(self._elementos, x)\n\n    def menor(self) -> A:\n        \"\"\"\n        Devuelve el menor elemento del conjunto\n        \"\"\"\n        return self._elementos[0]\n\n    def elimina(self, x: A) -> None:\n        \"\"\"\n        Elimina el elemento x del conjunto.\n        \"\"\"\n        pos = bisect_left(self._elementos, x)\n        if pos < len(self._elementos) and self._elementos[pos] == x:\n            self._elementos.pop(pos)\n\n    def esVacio(self) -> bool:\n        \"\"\"\n        Se verifica si el conjunto est\u00e1 vac\u00edo.\n        \"\"\"\n        return not self._elementos\n\n    def pertenece(self, x: A) -> bool:\n        \"\"\"\n        Se verifica si x pertenece al conjunto.\n        \"\"\"\n        return x in takewhile(lambda y: y <= x, self._elementos)\n\n# Funciones del tipo conjunto\n# ===========================\n\ndef vacio() -> Conj[A]:\n    \"\"\"\n    Crea y devuelve un conjunto vac\u00edo de tipo A.\n    \"\"\"\n    c: Conj[A] = Conj()\n    return c\n\ndef inserta(x: A, c: Conj[A]) -> Conj[A]:\n    \"\"\"\n    Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto\n    con el elemento insertado.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.inserta(x)\n    return _aux\n\ndef menor(c: Conj[A]) -> A:\n    \"\"\"\n    Devuelve el menor elemento del conjunto c.\n    \"\"\"\n    return c.menor()\n\ndef elimina(x: A, c: Conj[A]) -> Conj[A]:\n    \"\"\"\n    Elimina las ocurrencias de c en c y devuelve una copia del conjunto\n    resultante.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.elimina(x)\n    return _aux\n\ndef pertenece(x: A, c: Conj[A]) -> bool:\n    \"\"\"\n    Se verifica si x pertenece a c.\n    \"\"\"\n    return c.pertenece(x)\n\ndef esVacio(c: Conj[A]) -> bool:\n    \"\"\"\n    Se verifica si el conjunto est\u00e1 vac\u00edo.\n    \"\"\"\n    return c.esVacio()\n\n# Generador de conjuntos\n# ======================\n\ndef sin_duplicados_y_ordenado(xs: list[int]) -> list[int]:\n    xs = list(set(xs))\n    xs.sort()\n    return xs\n\ndef conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:\n    \"\"\"\n    Estrategia de b\u00fasqueda para generar conjuntos de enteros de forma\n    aleatoria.\n    \"\"\"\n    xs = st.lists(st.integers()).map(sin_duplicados_y_ordenado)\n    return xs.map(Conj)\n\n# Comprobaci\u00f3n de las propiedades de los conjuntos\n# ================================================\n\n# Las propiedades son\n@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())\ndef test_conjuntos(c: Conj[int], x: int, y: int) -> None:\n    assert inserta(x, inserta(x, c)) == inserta(x, c)\n    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))\n    assert not pertenece(x, vacio())\n    assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)\n    assert elimina(x, vacio()) == vacio()\n\n    def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:\n        if x == y:\n            return elimina(x, c)\n        return inserta(y, elimina(x, c))\n\n    assert elimina(x, inserta(y, c)) == relacion(x, y, c)\n    assert esVacio(vacio())\n    assert not esVacio(inserta(x, c))\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q conjuntoConListasOrdenadasSinDuplicados.py\n#    1 passed in 0.13s\n<\/pre>\n<h4>3.5. Implementaci\u00f3n de los conjuntos mediante librer\u00eda<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3wEoxjP\">conjuntoConLibreria.py<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\n__all__ = [\n    'Conj',\n    'vacio',\n    'inserta',\n    'menor',\n    'elimina',\n    'pertenece',\n    'esVacio',\n    'conjuntoAleatorio'\n]\n\nfrom abc import abstractmethod\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Generic, Protocol, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nclass Comparable(Protocol):\n    @abstractmethod\n    def __lt__(self: A, otro: A) -> bool:\n        pass\n\nA = TypeVar('A', bound=Comparable)\n\n# Clase de los conjuntos mediante librer\u00eda\n# ========================================\n\n@dataclass\nclass Conj(Generic[A]):\n    _elementos: set[A] = field(default_factory=set)\n\n    def __repr__(self) -> str:\n        xs = [str(x) for x in self._elementos]\n        return \"{\" + \", \".join(xs) + \"}\"\n\n    def inserta(self, x: A) -> None:\n        \"\"\"\n        A\u00f1ade el elemento x al conjunto.\n        \"\"\"\n        self._elementos.add(x)\n\n    def menor(self) -> A:\n        \"\"\"\n        Devuelve el menor elemento del conjunto\n        \"\"\"\n        return min(self._elementos)\n\n    def elimina(self, x: A) -> None:\n        \"\"\"\n        Elimina el elemento x del conjunto.\n        \"\"\"\n        self._elementos.discard(x)\n\n    def esVacio(self) -> bool:\n        \"\"\"\n        Se verifica si el conjunto est\u00e1 vac\u00edo.\n        \"\"\"\n        return not self._elementos\n\n    def pertenece(self, x: A) -> bool:\n        \"\"\"\n        Se verifica si x pertenece al conjunto.\n        \"\"\"\n        return x in self._elementos\n\n# Funciones del tipo conjunto\n# ===========================\n\ndef vacio() -> Conj[A]:\n    \"\"\"\n    Crea y devuelve un conjunto vac\u00edo de tipo A.\n    \"\"\"\n    c: Conj[A] = Conj()\n    return c\n\ndef inserta(x: A, c: Conj[A]) -> Conj[A]:\n    \"\"\"\n    Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto\n    con el elemento insertado.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.inserta(x)\n    return _aux\n\ndef menor(c: Conj[A]) -> A:\n    \"\"\"\n    Devuelve el menor elemento del conjunto c.\n    \"\"\"\n    return c.menor()\n\ndef elimina(x: A, c: Conj[A]) -> Conj[A]:\n    \"\"\"\n    Elimina las ocurrencias de c en c y devuelve una copia del conjunto\n    resultante.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.elimina(x)\n    return _aux\n\ndef pertenece(x: A, c: Conj[A]) -> bool:\n    \"\"\"\n    Se verifica si x pertenece a c.\n    \"\"\"\n    return c.pertenece(x)\n\ndef esVacio(c: Conj[A]) -> bool:\n    \"\"\"\n    Se verifica si el conjunto est\u00e1 vac\u00edo.\n    \"\"\"\n    return c.esVacio()\n\n# Generador de conjuntos\n# ======================\n\ndef conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:\n    \"\"\"\n    Estrategia de b\u00fasqueda para generar conjuntos de enteros de forma\n    aleatoria.\n    \"\"\"\n    return st.builds(Conj, st.lists(st.integers()).map(set))\n\n# Comprobaci\u00f3n de las propiedades de los conjuntos\n# ================================================\n\n# Las propiedades son\n@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())\ndef test_conjuntos(c: Conj[int], x: int, y: int) -> None:\n    assert inserta(x, inserta(x, c)) == inserta(x, c)\n    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))\n    assert not pertenece(x, vacio())\n    assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)\n    assert elimina(x, vacio()) == vacio()\n\n    def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:\n        if x == y:\n            return elimina(x, c)\n        return inserta(y, elimina(x, c))\n\n    assert elimina(x, inserta(y, c)) == relacion(x, y, c)\n    assert esVacio(vacio())\n    assert not esVacio(inserta(x, c))\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q conjuntoConLibreria.py\n#    1 passed in 0.22s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>1. El tipo abstracto de datos de los conjuntos Un conjunto es una estructura de datos, caracterizada por ser una colecci\u00f3n de elementos en la que no importe ni el orden ni la repetici\u00f3n de elementos. Las operaciones que definen al tipo abstracto de datos (TAD) de los conjuntos (cuyos elementos son del tipo a)&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[331,585],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7919"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=7919"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7919\/revisions"}],"predecessor-version":[{"id":7968,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7919\/revisions\/7968"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7919"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7919"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7919"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}