{"id":7908,"date":"2023-03-04T10:51:17","date_gmt":"2023-03-04T09:51:17","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7908"},"modified":"2023-03-04T10:51:17","modified_gmt":"2023-03-04T09:51:17","slug":"04-mar-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/04-mar-23\/","title":{"rendered":"La semana en Exercitium (4 de marzo de 2023)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. TAD de las colas: M\u00e1ximo elemento de una cola<\/a><\/li>\n<li><a href=\"#ej2\">2. El tipo abstracto de datos de los conjuntos<\/a><\/li>\n<li><a href=\"#ej3\">3. TAD de los conjuntos: Transformaciones entre conjuntos y listas<\/a><\/li>\n<li><a href=\"#ej4\">4. TAD de los conjuntos: Reconocimiento de subconjuntos<\/a><\/li>\n<li><a href=\"#ej5\">5. TAD de los conjuntos: Reconocimiento de subconjuntos propios<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. TAD de las colas: M\u00e1ximo elemento de una cola<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3QWTsRL\">tipo abstracto de datos de las colas<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   maxCola :: Ord a => Cola a -> a\n<\/pre>\n<p>tal que <code>maxCola c<\/code> sea el mayor de los elementos de la cola <code>c<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> maxCola (inserta 3 (inserta 5 (inserta 1 vacia)))\n   5\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)\nimport Transformaciones_colas_listas (colaAlista)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmaxCola1 :: Ord a => Cola a -> a\nmaxCola1 c\n  | esVacia rc = pc\n  | otherwise  = max pc (maxCola1 rc)\n  where pc = primero c\n        rc = resto c\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmaxCola2 :: Ord a => Cola a -> a\nmaxCola2 =\n  maximum . colaAlista\n\n-- La funci\u00f3n colaAlista est\u00e1 definida en el ejercicio\n-- \"Transformaciones entre colas y listas\" que se encuentra en\n-- https:\/\/bit.ly\/3Xv0oIt\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_maxCola :: Cola Int -> Property\nprop_maxCola c =\n  not (esVacia c) ==> maxCola1 c == maxCola2 c\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_maxCola\n--    +++ OK, passed 100 tests; 16 discarded.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom copy import deepcopy\nfrom typing import TypeVar\n\nfrom hypothesis import assume, given\n\nfrom src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,\n                          resto, vacia)\nfrom src.transformaciones_colas_listas import colaAlista\n\nA = TypeVar('A', int, float, str)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef maxCola1(c: Cola[A]) -> A:\n    pc = primero(c)\n    rc = resto(c)\n    if esVacia(rc):\n        return pc\n    return max(pc, maxCola1(rc))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# Se usar\u00e1 la funci\u00f3n colaAlista del ejercicio\n# \"Transformaciones entre colas y listas\" que se encuentra en\n# https:\/\/bit.ly\/3ZHewQ8\n\ndef maxCola2(c: Cola[A]) -> A:\n    return max(colaAlista(c))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef maxCola3Aux(c: Cola[A]) -> A:\n    pc = c.primero()\n    c.resto()\n    if esVacia(c):\n        return pc\n    return max(pc, maxCola3Aux(c))\n\ndef maxCola3(c: Cola[A]) -> A:\n    _c = deepcopy(c)\n    return maxCola3Aux(_c)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef maxCola4Aux(c: Cola[A]) -> A:\n    r = c.primero()\n    while not esVacia(c):\n        pc = c.primero()\n        if pc > r:\n            r = pc\n        c.resto()\n    return r\n\ndef maxCola4(c: Cola[A]) -> A:\n    _c = deepcopy(c)\n    return maxCola4Aux(_c)\n\n# Comprobaci\u00f3n de equivalencia de las definiciones\n# ================================================\n\n# La propiedad es\n@given(c=colaAleatoria())\ndef test_maxCola(c: Cola[int]) -> None:\n    assume(not esVacia(c))\n    r = maxCola1(c)\n    assert maxCola2(c) == r\n    assert maxCola3(c) == r\n    assert maxCola4(c) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q maxCola.py\n#    1 passed in 0.30s\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. El tipo abstracto de datos de los conjuntos<\/h3>\n<h4>2.1. El tipo abstracto de datos de los conjuntos<\/h4>\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<h4>2.2. Los conjuntos en Haskell<\/h4>\n<h5>2.2.1. El tipo abstracto de datos de los conjuntos en Haskell<\/h5>\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<h5>2.2.2. Implementaci\u00f3n de los conjuntos mediante listas no ordenadas con duplicados<\/h5>\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<h5>2.2.3. Implementaci\u00f3n de los conjuntos mediante listas no ordenadas sin duplicados<\/h5>\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<h5>2.2.4. Implementaci\u00f3n de los conjuntos mediante listas ordenadas sin repeticiones<\/h5>\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<h5>2.2.5. Implementaci\u00f3n de los conjuntos mediante librer\u00eda<\/h5>\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<h4>2.3. Los conjuntos en Python<\/h4>\n<h5>2.3.1. El tipo abstracto de los conjuntos en Python<\/h5>\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<h5>2.3.2. Implementaci\u00f3n de los conjuntos mediante listas no ordenadas con duplicados<\/h5>\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<h5>2.3.3. Implementaci\u00f3n de los conjuntos mediante listas no ordenadas sin duplicados<\/h5>\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<h5>2.3.4. Implementaci\u00f3n de los conjuntos mediante listas ordenadas sin duplicados<\/h5>\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<h5>2.3.5. Implementaci\u00f3n de los conjuntos mediante librer\u00eda<\/h5>\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<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. TAD de los conjuntos: Transformaciones entre conjuntos y listas<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3HbB7fo\">tipo abstracto de datos de los conjuntos<\/a> definir las funciones<\/p>\n<pre lang=\"text\">\n   listaAconjunto :: [a] -> Conj a\n   conjuntoAlista :: Conj a -> [a]\n<\/pre>\n<p>tales que<br \/>\n+ <code>listaAconjunto xs<\/code> es el conjunto formado por los elementos de <code>xs<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n     \u03bb> listaAconjunto [3, 2, 5]\n     {2, 3, 5}\n<\/pre>\n<ul>\n<li><code>conjuntoAlista c<\/code> es la lista formada por los elementos del conjunto <code>c<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> conjuntoAlista (inserta 5 (inserta 2 (inserta 3 vacio)))\n     [2,3,5]\n<\/pre>\n<p>Comprobar con QuickCheck que ambas funciones son inversa; es decir,<\/p>\n<pre lang=\"text\">\n   conjuntoAlista (listaAconjunto xs) = sort (nub xs)\n   listaAconjunto (conjuntoAlista c)  = c\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)\nimport Data.List (sort, nub)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n de listaAconjunto\n-- ===============================\n\nlistaAconjunto :: Ord a => [a] -> Conj a\nlistaAconjunto []     = vacio\nlistaAconjunto (x:xs) = inserta x (listaAconjunto xs)\n\n-- 2\u00aa definici\u00f3n de listaAconjunto\n-- ===============================\n\nlistaAconjunto2 :: Ord a => [a] -> Conj a\nlistaAconjunto2 = foldr inserta vacio\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_listaAconjunto :: [Int] -> Bool\nprop_listaAconjunto xs =\n  listaAconjunto xs == listaAconjunto2 xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_listaAconjunto\n--    +++ OK, passed 100 tests.\n\n-- Definici\u00f3n de conjuntoAlista\n-- ============================\n\nconjuntoAlista :: Ord a => Conj a -> [a]\nconjuntoAlista c\n  | esVacio c = []\n  | otherwise = mc : conjuntoAlista rc\n  where mc = menor c\n        rc = elimina mc c\n\n-- Comprobaci\u00f3n de las propiedades\n-- ===============================\n\n-- La primera propiedad es\nprop_1_listaAconjunto :: [Int] -> Bool\nprop_1_listaAconjunto xs =\n  conjuntoAlista (listaAconjunto xs) == sort (nub xs)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_1_listaAconjunto\n--    +++ OK, passed 100 tests.\n\n-- La segunda propiedad es\nprop_2_listaAconjunto :: Conj Int -> Bool\nprop_2_listaAconjunto c =\n  listaAconjunto (conjuntoAlista c) == c\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_2_listaAconjunto\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\nfrom abc import abstractmethod\nfrom copy import deepcopy\nfrom functools import reduce\nfrom typing import Protocol, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,\n                              inserta, menor, pertenece, vacio)\n\nclass Comparable(Protocol):\n    @abstractmethod\n    def __lt__(self: A, otro: A) -> bool:\n        pass\n\nA = TypeVar('A', bound=Comparable)\n\n# 1\u00aa definici\u00f3n de listaAconjunto\n# ===============================\n\ndef listaAconjunto(xs: list[A]) -> Conj[A]:\n    if not xs:\n        return vacio()\n    return inserta(xs[0], listaAconjunto(xs[1:]))\n\n# 2\u00aa definici\u00f3n de listaAconjunto\n# ===============================\n\ndef listaAconjunto2(xs: list[A]) -> Conj[A]:\n    return reduce(lambda ys, y: inserta(y, ys), xs, vacio())\n\n# 3\u00aa soluci\u00f3n de listaAconjunto\n# =============================\n\ndef listaAconjunto3(xs: list[A]) -> Conj[A]:\n    c: Conj[A] = Conj()\n    for x in xs:\n        c.inserta(x)\n    return c\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.lists(st.integers()))\ndef test_listaAconjunto(xs: list[int]) -> None:\n    r = listaAconjunto(xs)\n    assert listaAconjunto2(xs) == r\n    assert listaAconjunto3(xs) == r\n\n# 1\u00aa definici\u00f3n de conjuntoAlista\n# ===============================\n\ndef conjuntoAlista(c: Conj[A]) -> list[A]:\n    if esVacio(c):\n        return []\n    mc = menor(c)\n    rc = elimina(mc, c)\n    return [mc] + conjuntoAlista(rc)\n\n# 2\u00aa definici\u00f3n de conjuntoAlista\n# ===============================\n\ndef conjuntoAlista2Aux(c: Conj[A]) -> list[A]:\n    if c.esVacio():\n        return []\n    mc = c.menor()\n    c.elimina(mc)\n    return [mc] + conjuntoAlista2Aux(c)\n\ndef conjuntoAlista2(c: Conj[A]) -> list[A]:\n    c1 = deepcopy(c)\n    return conjuntoAlista2Aux(c1)\n\n# 3\u00aa definici\u00f3n de conjuntoAlista\n# ===============================\n\ndef conjuntoAlista3Aux(c: Conj[A]) -> list[A]:\n    r = []\n    while not c.esVacio():\n        mc = c.menor()\n        r.append(mc)\n        c.elimina(mc)\n    return r\n\ndef conjuntoAlista3(c: Conj[A]) -> list[A]:\n    c1 = deepcopy(c)\n    return conjuntoAlista3Aux(c1)\n\n# Comprobaci\u00f3n de equivalencia de las definiciones de conjuntoAlista\n# ==============================================================\n\n@given(c=conjuntoAleatorio())\ndef test_conjuntoAlista(c: Conj[int]) -> None:\n    r = conjuntoAlista(c)\n    assert conjuntoAlista2(c) == r\n    assert conjuntoAlista3(c) == r\n\n# Comprobaci\u00f3n de las propiedades\n# ===============================\n\n# La primera propiedad es\n@given(st.lists(st.integers()))\ndef test_1_listaAconjunto(xs: list[int]) -> None:\n    assert conjuntoAlista(listaAconjunto(xs)) == sorted(list(set(xs)))\n\n# La segunda propiedad es\n@given(c=conjuntoAleatorio())\ndef test_2_listaAconjunto(c: Conj[int]) -> None:\n    assert listaAconjunto(conjuntoAlista(c)) == c\n\n# La comprobaci\u00f3n de las propiedades es\n#    > poetry run pytest -v TAD_Transformaciones_conjuntos_listas.py\n#       test_listaAconjunto PASSED\n#       test_conjuntoAlista PASSED\n#       test_1_listaAconjunto PASSED\n#       test_2_listaAconjunto PASSED\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. TAD de los conjuntos: Reconocimiento de subconjuntos<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3HbB7fo\">tipo abstracto de datos de los conjuntos<\/a> definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   subconjunto :: Ord a => Conj a -> Conj a -> Bool\n<\/pre>\n<p>tal que <code>subconjunto c1 c2<\/code> se verifica si todos los elementos de <code>c1<\/code> pertenecen a <code>c2<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> ej1 = inserta 5 (inserta 2 vacio)\n   \u03bb> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))\n   \u03bb> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))\n   \u03bb> subconjunto ej1 ej2\n   True\n   \u03bb> subconjunto ej1 ej3\n   False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)\nimport Transformaciones_conjuntos_listas (conjuntoAlista)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsubconjunto :: Ord a => Conj a -> Conj a -> Bool\nsubconjunto c1 c2\n  | esVacio c1 = True\n  | otherwise  =  pertenece mc1 c2 && subconjunto rc1 c2\n  where mc1 = menor c1\n        rc1 = elimina mc1 c1\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsubconjunto2 :: Ord a => Conj a -> Conj a -> Bool\nsubconjunto2 c1 c2 =\n  and [pertenece x c2 | x <- conjuntoAlista c1]\n\n-- La funci\u00f3n conjuntoAlista est\u00e1 definida en el ejercicio\n-- \"Transformaciones entre conjuntos y listas\" que se encuentra en\n-- https:\/\/bit.ly\/3RexzxH\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsubconjunto3 :: Ord a => Conj a -> Conj a -> Bool\nsubconjunto3 c1 c2 =\n  all (`pertenece` c2) (conjuntoAlista c1)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nsubconjunto4 :: Ord a => Conj a -> Conj a -> Bool\nsubconjunto4 c1 c2 =\n  sublista (conjuntoAlista c1) (conjuntoAlista c2)\n\n-- (sublista xs ys) se verifica si xs es una sublista de ys. Por\n-- ejemplo,\n--    sublista [5, 2] [3, 2, 5]  ==  True\n--    sublista [5, 2] [3, 4, 5]  ==  False\nsublista :: Ord a => [a] -> [a] -> Bool\nsublista [] _      = True\nsublista (x:xs) ys = elem x ys && sublista xs ys\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_subconjunto :: Conj Int -> Conj Int -> Bool\nprop_subconjunto c1 c2 =\n  all (== subconjunto c1 c2)\n      [subconjunto2 c1 c2,\n       subconjunto3 c1 c2,\n       subconjunto4 c1 c2]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_subconjunto\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\nfrom abc import abstractmethod\nfrom copy import deepcopy\nfrom typing import Protocol, TypeVar\n\nfrom hypothesis import given\n\nfrom src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,\n                              inserta, menor, pertenece, vacio)\nfrom src.TAD_Transformaciones_conjuntos_listas import conjuntoAlista\n\nclass Comparable(Protocol):\n    @abstractmethod\n    def __lt__(self: A, otro: A) -> bool:\n        pass\n\nA = TypeVar('A', bound=Comparable)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef subconjunto(c1: Conj[A], c2: Conj[A]) -> bool:\n    if esVacio(c1):\n        return True\n    mc1 = menor(c1)\n    rc1 = elimina(mc1, c1)\n    return pertenece(mc1, c2) and subconjunto(rc1, c2)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef subconjunto2(c1: Conj[A], c2: Conj[A]) -> bool:\n    return all((pertenece(x, c2) for x in conjuntoAlista(c1)))\n\n# La funci\u00f3n conjuntoAlista est\u00e1 definida en el ejercicio\n# \"Transformaciones entre conjuntos y listas\" que se encuentra en\n# https:\/\/bit.ly\/3RexzxH\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\n# (sublista xs ys) se verifica si xs es una sublista de ys. Por\n# ejemplo,\n#    sublista [5, 2] [3, 2, 5]  ==  True\n#    sublista [5, 2] [3, 4, 5]  ==  False\ndef sublista(xs: list[A], ys: list[A]) -> bool:\n    if not xs:\n        return True\n    return xs[0] in ys and sublista(xs[1:], ys)\n\ndef subconjunto3(c1: Conj[A], c2: Conj[A]) -> bool:\n    return sublista(conjuntoAlista(c1), conjuntoAlista(c2))\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef subconjunto4(c1: Conj[A], c2: Conj[A]) -> bool:\n    while not esVacio(c1):\n        mc1 = menor(c1)\n        if not pertenece(mc1, c2):\n            return False\n        c1 = elimina(mc1, c1)\n    return True\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef subconjunto5Aux(c1: Conj[A], c2: Conj[A]) -> bool:\n    while not c1.esVacio():\n        mc1 = c1.menor()\n        if not c2.pertenece(mc1):\n            return False\n        c1.elimina(mc1)\n    return True\n\ndef subconjunto5(c1: Conj[A], c2: Conj[A]) -> bool:\n    _c1 = deepcopy(c1)\n    return subconjunto5Aux(_c1, c2)\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())\ndef test_subconjunto(c1: Conj[int], c2: Conj[int]) -> None:\n    r = subconjunto(c1, c2)\n    assert subconjunto2(c1, c2) == r\n    assert subconjunto3(c1, c2) == r\n    assert subconjunto4(c1, c2) == r\n    assert subconjunto5(c1, c2) == r\n\n# La comprobaci\u00f3n de las propiedades es\n#    > poetry run pytest -q TAD_subconjunto.py\n#    1 passed in 0.37s\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. TAD de los conjuntos: Reconocimiento de subconjuntos propios<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3HbB7fo\">tipo abstracto de datos de los conjuntos<\/a> definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool\n<\/pre>\n<p>tal <code>subconjuntoPropio c1 c2<\/code> se verifica si <code>c1<\/code> es un subconjunto propio de <code>c2<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> ej1 = inserta 5 (inserta 2 vacio)\n   \u03bb> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))\n   \u03bb> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))\n   \u03bb> ej4 = inserta 2 (inserta 5 vacio)\n   \u03bb> subconjuntoPropio ej1 ej2\n   True\n   \u03bb> subconjuntoPropio ej1 ej3\n   False\n   \u03bb> subconjuntoPropio ej1 ej4\n   False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Conjunto (Conj, vacio, inserta)\nimport TAD_subconjunto (subconjunto)\n\nsubconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool\nsubconjuntoPropio c1 c2 =\n  subconjunto c1 c2 && c1 \/= c2\n\n-- La funci\u00f3n subconjunto est\u00e1 definida en el ejercicio\n-- \"Reconocimiento de subconjuntos\" que se encuentra en\n-- https:\/\/bit.ly\/3wPBtU5\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\nfrom abc import abstractmethod\nfrom typing import Protocol, TypeVar\n\nfrom src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,\n                              inserta, menor, pertenece, vacio)\nfrom src.TAD_subconjunto import subconjunto\n\nclass Comparable(Protocol):\n    @abstractmethod\n    def __lt__(self: A, otro: A) -> bool:\n        pass\n\nA = TypeVar('A', bound=Comparable)\n\ndef subconjuntoPropio(c1: Conj[A], c2: Conj[A]) -> bool:\n    return subconjunto(c1, c2) and c1 != c2\n\n# La funci\u00f3n subconjunto est\u00e1 definida en el ejercicio\n# \"Reconocimiento de subconjuntos\" que se encuentra en\n# https:\/\/bit.ly\/3wPBtU5\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. TAD de las colas: M\u00e1ximo elemento de una cola 2. El tipo abstracto de datos de los conjuntos 3. TAD de los conjuntos: Transformaciones entre conjuntos y listas 4. TAD de los conjuntos: Reconocimiento de subconjuntos 5. TAD de los conjuntos: Reconocimiento&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7908"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7908"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7908\/revisions"}],"predecessor-version":[{"id":7909,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7908\/revisions\/7909"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7908"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7908"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7908"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}