La semana en Exercitium (4 de marzo de 2023)

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:

1. TAD de las colas: Máximo 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 de subconjuntos propios

A continuación se muestran las soluciones.

1. TAD de las colas: Máximo elemento de una cola

Utilizando el tipo abstracto de datos de las colas, definir la función

   maxCola :: Ord a => Cola a -> a

1	maxCola :: Ord a => Cola a -> a

tal que maxCola c sea el mayor de los elementos de la cola c. Por ejemplo,

   λ> maxCola (inserta 3 (inserta 5 (inserta 1 vacia)))
   5

1 2	λ> maxCola (inserta 3 (inserta 5 (inserta 1 vacia))) 5

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)
import Transformaciones_colas_listas (colaAlista)
import Test.QuickCheck

-- 1ª solución
-- ===========

maxCola1 :: Ord a => Cola a -> a
maxCola1 c
  | esVacia rc = pc
  | otherwise  = max pc (maxCola1 rc)
  where pc = primero c
        rc = resto c

-- 2ª solución
-- ===========

maxCola2 :: Ord a => Cola a -> a
maxCola2 =
  maximum . colaAlista

-- La función colaAlista está definida en el ejercicio
-- "Transformaciones entre colas y listas" que se encuentra en
-- https://bit.ly/3Xv0oIt

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_maxCola :: Cola Int -> Property
prop_maxCola c =
  not (esVacia c) ==> maxCola1 c == maxCola2 c

-- La comprobación es
--    λ> quickCheck prop_maxCola
--    +++ OK, passed 100 tests; 16 discarded.

import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)

import Transformaciones_colas_listas (colaAlista)

import Test.QuickCheck

-- 1ª solución

-- ===========

maxCola1 :: Ord a => Cola a -> a

maxCola1 c

| esVacia rc = pc

| otherwise = max pc (maxCola1 rc)

where pc = primero c

rc = resto c

-- 2ª solución

-- ===========

maxCola2 :: Ord a => Cola a -> a

maxCola2 =

maximum . colaAlista

-- La función colaAlista está definida en el ejercicio

-- "Transformaciones entre colas y listas" que se encuentra en

-- https://bit.ly/3Xv0oIt

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_maxCola :: Cola Int -> Property

prop_maxCola c =

not (esVacia c) ==> maxCola1 c == maxCola2 c

-- La comprobación es

-- λ> quickCheck prop_maxCola

-- +++ OK, passed 100 tests; 16 discarded.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import assume, given

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,
                          resto, vacia)
from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A', int, float, str)

# 1ª solución
# ===========

def maxCola1(c: Cola[A]) -> A:
    pc = primero(c)
    rc = resto(c)
    if esVacia(rc):
        return pc
    return max(pc, maxCola1(rc))

# 2ª solución
# ===========

# Se usará la función colaAlista del ejercicio
# "Transformaciones entre colas y listas" que se encuentra en
# https://bit.ly/3ZHewQ8

def maxCola2(c: Cola[A]) -> A:
    return max(colaAlista(c))

# 3ª solución
# ===========

def maxCola3Aux(c: Cola[A]) -> A:
    pc = c.primero()
    c.resto()
    if esVacia(c):
        return pc
    return max(pc, maxCola3Aux(c))

def maxCola3(c: Cola[A]) -> A:
    _c = deepcopy(c)
    return maxCola3Aux(_c)

# 4ª solución
# ===========

def maxCola4Aux(c: Cola[A]) -> A:
    r = c.primero()
    while not esVacia(c):
        pc = c.primero()
        if pc > r:
            r = pc
        c.resto()
    return r

def maxCola4(c: Cola[A]) -> A:
    _c = deepcopy(c)
    return maxCola4Aux(_c)

# Comprobación de equivalencia de las definiciones
# ================================================

# La propiedad es
@given(c=colaAleatoria())
def test_maxCola(c: Cola[int]) -> None:
    assume(not esVacia(c))
    r = maxCola1(c)
    assert maxCola2(c) == r
    assert maxCola3(c) == r
    assert maxCola4(c) == r

# La comprobación es
#    src> poetry run pytest -q maxCola.py
#    1 passed in 0.30s

from copy import deepcopy

from typing import TypeVar

from hypothesis import assume, given

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,

resto, vacia)

from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A', int, float, str)

# 1ª solución

# ===========

def maxCola1(c: Cola[A]) -> A:

pc = primero(c)

rc = resto(c)

if esVacia(rc):

return pc

return max(pc, maxCola1(rc))

# 2ª solución

# ===========

# Se usará la función colaAlista del ejercicio

# "Transformaciones entre colas y listas" que se encuentra en

# https://bit.ly/3ZHewQ8

def maxCola2(c: Cola[A]) -> A:

return max(colaAlista(c))

# 3ª solución

# ===========

def maxCola3Aux(c: Cola[A]) -> A:

pc = c.primero()

c.resto()

if esVacia(c):

return pc

return max(pc, maxCola3Aux(c))

def maxCola3(c: Cola[A]) -> A:

_c = deepcopy(c)

return maxCola3Aux(_c)

# 4ª solución

# ===========

def maxCola4Aux(c: Cola[A]) -> A:

r = c.primero()

while not esVacia(c):

pc = c.primero()

if pc > r:

r = pc

c.resto()

return r

def maxCola4(c: Cola[A]) -> A:

_c = deepcopy(c)

return maxCola4Aux(_c)

# Comprobación de equivalencia de las definiciones

# ================================================

# La propiedad es

@given(c=colaAleatoria())

def test_maxCola(c: Cola[int]) -> None:

assume(not esVacia(c))

r = maxCola1(c)

assert maxCola2(c) == r

assert maxCola3(c) == r

assert maxCola4(c) == r

# La comprobación es

# src> poetry run pytest -q maxCola.py

# 1 passed in 0.30s

2. El tipo abstracto de datos de los conjuntos

2.1. El tipo abstracto de datos de los conjuntos

Un conjunto es una estructura de datos, caracterizada por ser una colección de elementos en la que no importe ni el orden ni la repetición de elementos.

Las operaciones que definen al tipo abstracto de datos (TAD) de los conjuntos (cuyos elementos son del tipo a) son las siguientes:

   vacio      :: Conj a
   inserta    :: Ord a => a -> Conj a -> Conj a
   menor      :: Ord a => Conj a -> a
   elimina    :: Ord a => a -> Conj a -> Conj a
   pertenece  :: Ord a => a -> Conj a -> Bool
   esVacio    :: Conj a -> Bool

vacio :: Conj a

inserta :: Ord a => a -> Conj a -> Conj a

menor :: Ord a => Conj a -> a

elimina :: Ord a => a -> Conj a -> Conj a

pertenece :: Ord a => a -> Conj a -> Bool

esVacio :: Conj a -> Bool

tales que

vacio es el conjunto vacío.
(inserta x c) es el conjunto obtenido añadiendo el elemento x al
conjunto c.
(menor c) es el menor elemento del conjunto c.
(elimina x c) es el conjunto obtenido eliminando el elemento x del conjunto c.
(pertenece x c) se verifica si x pertenece al conjunto c.
(esVacio c) se verifica si c es el conjunto vacío.

Las operaciones tienen que verificar las siguientes propiedades:

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

2.2. Los conjuntos en Haskell

2.2.1. El tipo abstracto de datos de los conjuntos en Haskell

El TAD de los conjuntos se encuentra en el módulo Conjunto.hs cuyo contenido es el siguiente:

module TAD.Conjunto
  (Conj,
   vacio,     -- Conj a
   inserta,   -- Ord a => a -> Conj a -> Conj a
   menor,     -- Ord a => Conj a -> a
   elimina,   -- Ord a => a -> Conj a -> Conj a
   pertenece, -- Ord a => a -> Conj a -> Bool
   esVacio    -- Conj a -> Bool
  ) where

import TAD.ConjuntoConListasNoOrdenadasConDuplicados
-- import TAD.ConjuntoConListasNoOrdenadasSinDuplicados
-- import TAD.ConjuntoConListasOrdenadasSinDuplicados
-- import TAD.ConjuntosConLibreria

module TAD.Conjunto

(Conj,

vacio, -- Conj a

inserta, -- Ord a => a -> Conj a -> Conj a

menor, -- Ord a => Conj a -> a

elimina, -- Ord a => a -> Conj a -> Conj a

pertenece, -- Ord a => a -> Conj a -> Bool

esVacio -- Conj a -> Bool

) where

import TAD.ConjuntoConListasNoOrdenadasConDuplicados

-- import TAD.ConjuntoConListasNoOrdenadasSinDuplicados

-- import TAD.ConjuntoConListasOrdenadasSinDuplicados

-- import TAD.ConjuntosConLibreria

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:

mediante listas no ordenadas con duplicados,
mediante listas no ordenadas sin duplicados,
mediante listas ordenadas sin duplicados y
mediante la librería de conjuntos.

2.2.2. Implementación de los conjuntos mediante listas no ordenadas con duplicados

La implementación se encuentra en el módulo ConjuntoConListasNoOrdenadasConDuplicados.hs cuyo contenido es el siguiente:

module TAD.ConjuntoConListasNoOrdenadasConDuplicados
  (Conj,
   vacio,     -- Conj a
   inserta,   -- Ord a => a -> Conj a -> Conj a
   menor,     -- Ord a => Conj a -> a
   elimina,   -- Ord a => a -> Conj a -> Conj a
   pertenece, -- Ord a => a -> Conj a -> Bool
   esVacio    -- Conj a -> Bool
  ) where

import Data.List (intercalate, nub, sort)
import Test.QuickCheck

-- Conjuntos como listas no ordenadas con repeticiones:
newtype Conj a = Cj [a]

-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por
-- ejemplo,
--    λ> escribeConjunto (Cj [])
--    "{}"
--    λ> escribeConjunto (Cj [5])
--    "{5}"
--    λ> escribeConjunto (Cj [2, 5])
--    "{2, 5}"
--    λ> escribeConjunto (Cj [5, 2, 5])
--    "{2, 5}"
escribeConjunto :: (Show a, Ord a) => Conj a -> String
escribeConjunto (Cj xs) =
  "{" ++ intercalate ", " (map show (sort (nub xs))) ++ "}"

-- Procedimiento de escritura de conjuntos.
instance (Show a, Ord a) => Show (Conj a) where
  show = escribeConjunto

-- Nota: Aunque el conjunto no está ordenado y tenga repeticiones, al
-- escribirlo se hará sin repeticiones y ordenando sus elementos.

-- vacio es el conjunto vacío. Por ejemplo,
--    λ> vacio
--    {}
vacio :: Conj a
vacio = Cj []

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al
-- conjunto c. Por ejemplo,
--    λ> inserta 5 vacio
--    {5}
--    λ> inserta 2 (inserta 5 vacio)
--    {2, 5}
--    λ> inserta 5 (inserta 2 vacio)
--    {2, 5}
inserta :: Eq a => a -> Conj a -> Conj a
inserta x (Cj ys) = Cj (x:ys)

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,
--    λ> menor (inserta 5 (inserta 2 vacio))
--    2
menor :: Ord a => Conj a -> a
menor (Cj []) = error "conjunto vacío"
menor (Cj xs) = minimum xs

-- (elimina x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
--    λ> elimina 2 (inserta 5 (inserta 2 vacio))
--    {5}
elimina :: Eq a => a -> Conj a -> Conj a
elimina x (Cj ys) = Cj (filter (/= x) ys)

-- (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,
--    λ> esVacio (inserta 5 (inserta 2 vacio))
--    False
--    λ> esVacio vacio
--    True
esVacio :: Conj a -> Bool
esVacio (Cj xs) = null xs

-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,
--    λ> pertenece 2 (inserta 5 (inserta 2 vacio))
--    True
--    λ> pertenece 4 (inserta 5 (inserta 2 vacio))
--    False
pertenece :: Eq a => a -> Conj a -> Bool
pertenece x (Cj xs) = x `elem` xs

-- (subconjunto c1 c2) se verifica si c1 es un subconjunto de c2. Por
-- ejemplo,
--    subconjunto (Cj [1,3,2,1]) (Cj [3,1,3,2])  ==  True
--    subconjunto (Cj [1,3,4,1]) (Cj [3,1,3,2])  ==  False
subconjunto :: Ord a => Conj a -> Conj a -> Bool
subconjunto (Cj xs) (Cj ys) = sublista xs ys
  where sublista [] _      = True
        sublista (z:zs) vs = elem z vs && sublista zs vs

-- (igualConjunto c1 c2) se verifica si los conjuntos c1 y c2 son
-- iguales. Por ejemplo,
--    igualConjunto (Cj [1,3,2,1]) (Cj [3,1,3,2])  ==  True
--    igualConjunto (Cj [1,3,4,1]) (Cj [3,1,3,2])  ==  False
igualConjunto :: Ord a => Conj a -> Conj a -> Bool
igualConjunto c c' =
  subconjunto c c' && subconjunto c' c

--- Los conjuntos son comparables por igualdad.
instance Ord a => Eq (Conj a) where
  (==) = igualConjunto

-- Generador de conjuntos                                          --
-- ======================

-- genConjunto es un generador de conjuntos. Por ejemplo,
--    λ> sample (genConjunto :: Gen (Conj Int))
--    {}
--    {1}
--    {0, 2, 3}
--    {-6, 5}
--    {2, 5}
--    {-9, -6, 4, 8}
--    {0, 1}
--    {-13, -11, -5, -2, -1, 0, 4, 6, 7, 8, 9, 14}
--    {-7, -5, -2, -1, 1, 2, 10, 13, 15}
--    {-18, -17, -16, -10, -9, 0, 1, 3, 4, 13, 16}
--    {-20, -15, -7, -1, 2, 8, 10, 15, 20}
genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)
genConjunto = do
  xs <- listOf arbitrary
  return (foldr inserta vacio xs)

-- Los conjuntos son concreciones de los arbitrarios.
instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where
  arbitrary = genConjunto

-- Propiedades de los conjuntos                                        --
-- ============================

prop_conjuntos :: Int -> Int -> Conj Int -> Bool
prop_conjuntos x y c =
  inserta x (inserta x c) == inserta x c &&
  inserta x (inserta y c) == inserta y (inserta x c) &&
  not (pertenece x vacio) &&
  pertenece y (inserta x c) == (x == y) || pertenece y c &&
  elimina x vacio == vacio &&
  elimina x (inserta y c) == (if x == y
                              then elimina x c
                              else inserta y (elimina x c)) &&
  esVacio (vacio :: Conj Int) &&
  not (esVacio (inserta x c))

-- Comprobación
--    λ> quickCheck prop_conjuntos
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

module TAD.ConjuntoConListasNoOrdenadasConDuplicados

(Conj,

vacio, -- Conj a

inserta, -- Ord a => a -> Conj a -> Conj a

menor, -- Ord a => Conj a -> a

elimina, -- Ord a => a -> Conj a -> Conj a

pertenece, -- Ord a => a -> Conj a -> Bool

esVacio -- Conj a -> Bool

) where

import Data.List (intercalate, nub, sort)

import Test.QuickCheck

-- Conjuntos como listas no ordenadas con repeticiones:

newtype Conj a = Cj [a]

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

-- ejemplo,

-- λ> escribeConjunto (Cj [])

-- "{}"

-- λ> escribeConjunto (Cj [5])

-- "{5}"

-- λ> escribeConjunto (Cj [2, 5])

-- "{2, 5}"

-- λ> escribeConjunto (Cj [5, 2, 5])

-- "{2, 5}"

escribeConjunto :: (Show a, Ord a) => Conj a -> String

escribeConjunto (Cj xs) =

"{" ++ intercalate ", " (map show (sort (nub xs))) ++ "}"

-- Procedimiento de escritura de conjuntos.

instance (Show a, Ord a) => Show (Conj a) where

show = escribeConjunto

-- Nota: Aunque el conjunto no está ordenado y tenga repeticiones, al

-- escribirlo se hará sin repeticiones y ordenando sus elementos.

-- vacio es el conjunto vacío. Por ejemplo,

-- λ> vacio

-- {}

vacio :: Conj a

vacio = Cj []

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al

-- conjunto c. Por ejemplo,

-- λ> inserta 5 vacio

-- {5}

-- λ> inserta 2 (inserta 5 vacio)

-- {2, 5}

-- λ> inserta 5 (inserta 2 vacio)

-- {2, 5}

inserta :: Eq a => a -> Conj a -> Conj a

inserta x (Cj ys) = Cj (x:ys)

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,

-- λ> menor (inserta 5 (inserta 2 vacio))

-- 2

menor :: Ord a => Conj a -> a

menor (Cj []) = error "conjunto vacío"

menor (Cj xs) = minimum xs

-- (elimina x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c. Por ejemplo,

-- λ> elimina 2 (inserta 5 (inserta 2 vacio))

-- {5}

elimina :: Eq a => a -> Conj a -> Conj a

elimina x (Cj ys) = Cj (filter (/= x) ys)

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

-- λ> esVacio (inserta 5 (inserta 2 vacio))

-- False

-- λ> esVacio vacio

-- True

esVacio :: Conj a -> Bool

esVacio (Cj xs) = null xs

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

-- λ> pertenece 2 (inserta 5 (inserta 2 vacio))

-- True

-- λ> pertenece 4 (inserta 5 (inserta 2 vacio))

-- False

pertenece :: Eq a => a -> Conj a -> Bool

pertenece x (Cj xs) = x `elem` xs

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

-- ejemplo,

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

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

subconjunto :: Ord a => Conj a -> Conj a -> Bool

subconjunto (Cj xs) (Cj ys) = sublista xs ys

where sublista [] _ = True

sublista (z:zs) vs = elem z vs && sublista zs vs

-- (igualConjunto c1 c2) se verifica si los conjuntos c1 y c2 son

-- iguales. Por ejemplo,

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

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

igualConjunto :: Ord a => Conj a -> Conj a -> Bool

igualConjunto c c' =

subconjunto c c' && subconjunto c' c

--- Los conjuntos son comparables por igualdad.

instance Ord a => Eq (Conj a) where

(==) = igualConjunto

-- Generador de conjuntos --

-- ======================

-- genConjunto es un generador de conjuntos. Por ejemplo,

-- λ> sample (genConjunto :: Gen (Conj Int))

-- {}

-- {1}

-- {0, 2, 3}

-- {-6, 5}

-- {2, 5}

-- {-9, -6, 4, 8}

-- {0, 1}

-- {-13, -11, -5, -2, -1, 0, 4, 6, 7, 8, 9, 14}

-- {-7, -5, -2, -1, 1, 2, 10, 13, 15}

-- {-18, -17, -16, -10, -9, 0, 1, 3, 4, 13, 16}

-- {-20, -15, -7, -1, 2, 8, 10, 15, 20}

genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)

genConjunto = do

xs <- listOf arbitrary

return (foldr inserta vacio xs)

-- Los conjuntos son concreciones de los arbitrarios.

instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where

arbitrary = genConjunto

-- Propiedades de los conjuntos --

-- ============================

prop_conjuntos :: Int -> Int -> Conj Int -> Bool

prop_conjuntos x y c =

inserta x (inserta x c) == inserta x c &&

inserta x (inserta y c) == inserta y (inserta x c) &&

not (pertenece x vacio) &&

pertenece y (inserta x c) == (x == y) || pertenece y c &&

elimina x vacio == vacio &&

elimina x (inserta y c) == (if x == y

then elimina x c

else inserta y (elimina x c)) &&

esVacio (vacio :: Conj Int) &&

not (esVacio (inserta x c))

-- Comprobación

-- λ> quickCheck prop_conjuntos

-- +++ OK, passed 100 tests.

2.2.3. Implementación de los conjuntos mediante listas no ordenadas sin duplicados

La implementación se encuentra en el módulo ConjuntoConListasNoOrdenadasSinDuplicados.hs cuyo contenido es el siguiente:

module TAD.ConjuntoConListasNoOrdenadasSinDuplicados
  (Conj,
   vacio,     -- Conj a
   inserta,   -- Ord a => a -> Conj a -> Conj a
   menor,     -- Ord a => Conj a -> a
   elimina,   -- Ord a => a -> Conj a -> Conj a
   pertenece, -- Ord a => a -> Conj a -> Bool
   esVacio    -- Conj a -> Bool
  ) where

import Data.List (intercalate, sort)
import Test.QuickCheck

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

-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por
-- ejemplo,
--    λ> escribeConjunto (Cj [])
--    "{}"
--    λ> escribeConjunto (Cj [5])
--    "{5}"
--    λ> escribeConjunto (Cj [2, 5])
--    "{2, 5}"
--    λ> escribeConjunto (Cj [5, 2])
--    "{2, 5}"
escribeConjunto :: (Show a, Ord a) => Conj a -> String
escribeConjunto (Cj xs) =
  "{" ++ intercalate ", " (map show (sort xs)) ++ "}"

-- Procedimiento de escritura de conjuntos.
instance (Show a, Ord a) => Show (Conj a) where
  show = escribeConjunto

-- vacio es el conjunto vacío. Por ejemplo,
--    λ> vacio
--    {}
vacio :: Conj a
vacio = Cj []

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al
-- conjunto c. Por ejemplo,
--    λ> inserta 5 vacio
--    {5}
--    λ> inserta 2 (inserta 5 vacio)
--    {2, 5}
--    λ> inserta 5 (inserta 2 vacio)
--    {2, 5}
inserta :: Eq a => a -> Conj a -> Conj a
inserta x s@(Cj xs) | pertenece x s = s
                    | otherwise     = Cj (x:xs)

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,
--    λ> menor (inserta 5 (inserta 2 vacio))
--    2
menor :: Ord a => Conj a -> a
menor (Cj []) = error "conjunto vacío"
menor (Cj xs) = minimum xs

-- (elimina x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
--    λ> elimina 2 (inserta 5 (inserta 2 vacio))
--    {5}
elimina :: Eq a => a -> Conj a -> Conj a
elimina x (Cj s) = Cj [y | y <- s, y /= x]

-- (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,
--    λ> esVacio (inserta 5 (inserta 2 vacio))
--    False
--    λ> esVacio vacio
--    True
esVacio :: Conj a -> Bool
esVacio (Cj xs) = null xs

-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,
--    λ> pertenece 2 (inserta 5 (inserta 2 vacio))
--    True
--    λ> pertenece 4 (inserta 5 (inserta 2 vacio))
--    False
pertenece :: Eq a => a -> Conj a -> Bool
pertenece x (Cj xs) = x `elem` xs

-- (subconjunto c1 c2) se verifica si c1 es un subconjunto de c2. Por
-- ejemplo,
--    subconjunto (Cj [1,3,2]) (Cj [3,1,2])    ==  True
--    subconjunto (Cj [1,3,4,1]) (Cj [1,3,2])  ==  False
subconjunto :: Ord a => Conj a -> Conj a -> Bool
subconjunto (Cj xs) (Cj ys) = sublista xs ys
  where sublista [] _      = True
        sublista (z:zs) vs = elem z vs && sublista zs vs

-- (igualConjunto c1 c2) se verifica si los conjuntos c1 y c2 son
-- iguales. Por ejemplo,
--    igualConjunto (Cj [3,2,1]) (Cj [1,3,2])  ==  True
--    igualConjunto (Cj [1,3,4]) (Cj [1,3,2])  ==  False
igualConjunto :: Ord a => Conj a -> Conj a -> Bool
igualConjunto c c' =
  subconjunto c c' && subconjunto c' c

--- Los conjuntos son comparables por igualdad.
instance Ord a => Eq (Conj a) where
  (==) = igualConjunto

-- Generador de conjuntos                                          --
-- ======================

-- genConjunto es un generador de conjuntos. Por ejemplo,
--    λ> sample (genConjunto :: Gen (Conj Int))
--    {}
--    {-1, 0}
--    {-4, 1, 2}
--    {-3, 0, 2, 3, 4}
--    {-7}
--    {-10, -7, -5, -2, -1, 2, 5, 8}
--    {5, 7, 8, 10}
--    {-9, -6, -3, 8}
--    {-8, -6, -5, -1, 7, 9, 14}
--    {-18, -15, -14, -13, -3, -2, 1, 2, 4, 8, 12, 17}
--    {-17, -16, -13, -12, -11, -9, -6, -3, 0, 1, 3, 5, 6, 7, 16, 18}
genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)
genConjunto = do
  xs <- listOf arbitrary
  return (foldr inserta vacio xs)

-- Los conjuntos son concreciones de los arbitrarios.
instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where
  arbitrary = genConjunto

-- Propiedades de los conjuntos                                        --
-- ============================

prop_conjuntos :: Int -> Int -> Conj Int -> Bool
prop_conjuntos x y c =
  inserta x (inserta x c) == inserta x c &&
  inserta x (inserta y c) == inserta y (inserta x c) &&
  not (pertenece x vacio) &&
  pertenece y (inserta x c) == (x == y) || pertenece y c &&
  elimina x vacio == vacio &&
  elimina x (inserta y c) == (if x == y
                              then elimina x c
                              else inserta y (elimina x c)) &&
  esVacio (vacio :: Conj Int) &&
  not (esVacio (inserta x c))

-- Comprobación
--    λ> quickCheck prop_conjuntos
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

module TAD.ConjuntoConListasNoOrdenadasSinDuplicados

(Conj,

vacio, -- Conj a

inserta, -- Ord a => a -> Conj a -> Conj a

menor, -- Ord a => Conj a -> a

elimina, -- Ord a => a -> Conj a -> Conj a

pertenece, -- Ord a => a -> Conj a -> Bool

esVacio -- Conj a -> Bool

) where

import Data.List (intercalate, sort)

import Test.QuickCheck

-- Los conjuntos como listas no ordenadas sin repeticiones.

newtype Conj a = Cj [a]

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

-- ejemplo,

-- λ> escribeConjunto (Cj [])

-- "{}"

-- λ> escribeConjunto (Cj [5])

-- "{5}"

-- λ> escribeConjunto (Cj [2, 5])

-- "{2, 5}"

-- λ> escribeConjunto (Cj [5, 2])

-- "{2, 5}"

escribeConjunto :: (Show a, Ord a) => Conj a -> String

escribeConjunto (Cj xs) =

"{" ++ intercalate ", " (map show (sort xs)) ++ "}"

-- Procedimiento de escritura de conjuntos.

instance (Show a, Ord a) => Show (Conj a) where

show = escribeConjunto

-- vacio es el conjunto vacío. Por ejemplo,

-- λ> vacio

-- {}

vacio :: Conj a

vacio = Cj []

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al

-- conjunto c. Por ejemplo,

-- λ> inserta 5 vacio

-- {5}

-- λ> inserta 2 (inserta 5 vacio)

-- {2, 5}

-- λ> inserta 5 (inserta 2 vacio)

-- {2, 5}

inserta :: Eq a => a -> Conj a -> Conj a

inserta x s@(Cj xs) | pertenece x s = s

| otherwise = Cj (x:xs)

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,

-- λ> menor (inserta 5 (inserta 2 vacio))

-- 2

menor :: Ord a => Conj a -> a

menor (Cj []) = error "conjunto vacío"

menor (Cj xs) = minimum xs

-- (elimina x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c. Por ejemplo,

-- λ> elimina 2 (inserta 5 (inserta 2 vacio))

-- {5}

elimina :: Eq a => a -> Conj a -> Conj a

elimina x (Cj s) = Cj [y | y <- s, y /= x]

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

-- λ> esVacio (inserta 5 (inserta 2 vacio))

-- False

-- λ> esVacio vacio

-- True

esVacio :: Conj a -> Bool

esVacio (Cj xs) = null xs

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

-- λ> pertenece 2 (inserta 5 (inserta 2 vacio))

-- True

-- λ> pertenece 4 (inserta 5 (inserta 2 vacio))

-- False

pertenece :: Eq a => a -> Conj a -> Bool

pertenece x (Cj xs) = x `elem` xs

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

-- ejemplo,

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

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

subconjunto :: Ord a => Conj a -> Conj a -> Bool

subconjunto (Cj xs) (Cj ys) = sublista xs ys

where sublista [] _ = True

sublista (z:zs) vs = elem z vs && sublista zs vs

-- (igualConjunto c1 c2) se verifica si los conjuntos c1 y c2 son

-- iguales. Por ejemplo,

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

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

igualConjunto :: Ord a => Conj a -> Conj a -> Bool

igualConjunto c c' =

subconjunto c c' && subconjunto c' c

--- Los conjuntos son comparables por igualdad.

instance Ord a => Eq (Conj a) where

(==) = igualConjunto

-- Generador de conjuntos --

-- ======================

-- genConjunto es un generador de conjuntos. Por ejemplo,

-- λ> sample (genConjunto :: Gen (Conj Int))

-- {}

-- {-1, 0}

-- {-4, 1, 2}

-- {-3, 0, 2, 3, 4}

-- {-7}

-- {-10, -7, -5, -2, -1, 2, 5, 8}

-- {5, 7, 8, 10}

-- {-9, -6, -3, 8}

-- {-8, -6, -5, -1, 7, 9, 14}

-- {-18, -15, -14, -13, -3, -2, 1, 2, 4, 8, 12, 17}

-- {-17, -16, -13, -12, -11, -9, -6, -3, 0, 1, 3, 5, 6, 7, 16, 18}

genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)

genConjunto = do

xs <- listOf arbitrary

return (foldr inserta vacio xs)

-- Los conjuntos son concreciones de los arbitrarios.

instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where

arbitrary = genConjunto

-- Propiedades de los conjuntos --

-- ============================

prop_conjuntos :: Int -> Int -> Conj Int -> Bool

prop_conjuntos x y c =

inserta x (inserta x c) == inserta x c &&

inserta x (inserta y c) == inserta y (inserta x c) &&

not (pertenece x vacio) &&

pertenece y (inserta x c) == (x == y) || pertenece y c &&

elimina x vacio == vacio &&

elimina x (inserta y c) == (if x == y

then elimina x c

else inserta y (elimina x c)) &&

esVacio (vacio :: Conj Int) &&

not (esVacio (inserta x c))

-- Comprobación

-- λ> quickCheck prop_conjuntos

-- +++ OK, passed 100 tests.

2.2.4. Implementación de los conjuntos mediante listas ordenadas sin repeticiones

La implementación se encuentra en el módulo ConjuntoConListasOrdenadasSinDuplicados.hs cuyo contenido es el siguiente:

module TAD.ConjuntoConListasOrdenadasSinDuplicados
  (Conj,
   vacio,     -- Conj a
   inserta,   -- Ord a => a -> Conj a -> Conj a
   menor,     -- Ord a => Conj a -> a
   elimina,   -- Ord a => a -> Conj a -> Conj a
   pertenece, -- Ord a => a -> Conj a -> Bool
   esVacio    -- Conj a -> Bool
  ) where

import Data.List (intercalate)
import Test.QuickCheck

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

-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por
-- ejemplo,
--    λ> escribeConjunto (Cj [])
--    "{}"
--    λ> escribeConjunto (Cj [5])
--    "{5}"
--    λ> escribeConjunto (Cj [2, 5])
--    "{2, 5}"
--    λ> escribeConjunto (Cj [5, 2])
--    "{2, 5}"
escribeConjunto :: Show a => Conj a -> String
escribeConjunto (Cj xs) =
  "{" ++ intercalate ", " (map show xs) ++ "}"

-- Procedimiento de escritura de conjuntos.
instance Show a => Show (Conj a) where
  show = escribeConjunto

-- vacio es el conjunto vacío. Por ejemplo,
--    λ> vacio
--    {}
vacio :: Conj a
vacio = Cj []

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al
-- conjunto c. Por ejemplo,
--    λ> inserta 5 vacio
--    {5}
--    λ> inserta 2 (inserta 5 vacio)
--    {2, 5}
--    λ> inserta 5 (inserta 2 vacio)
--    {2, 5}
inserta :: Ord a => a -> Conj a -> Conj a
inserta x (Cj s) = Cj (agrega x s)
  where agrega z []                     = [z]
        agrega z s'@(y:ys) | z > y      = y : agrega z ys
                           | z < y      = z : s'
                           | otherwise  = s'

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,
--    λ> menor (inserta 5 (inserta 2 vacio))
--    2
menor :: Ord a => Conj a -> a
menor (Cj [])    = error "conjunto vacío"
menor (Cj (x:_)) = x

-- (elimina x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
--    λ> elimina 2 (inserta 5 (inserta 2 vacio))
--    {5}
elimina :: Ord a => a -> Conj a -> Conj a
elimina x (Cj s) = Cj (elimina' x s)
  where elimina' _ []                    = []
        elimina' z s'@(y:ys) | z > y     = y : elimina' z ys
                             | z < y     = s'
                             | otherwise = ys

-- (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,
--    λ> esVacio (inserta 5 (inserta 2 vacio))
--    False
--    λ> esVacio vacio
--    True
esVacio :: Conj a -> Bool
esVacio (Cj xs) = null xs

-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,
--    λ> pertenece 2 (inserta 5 (inserta 2 vacio))
--    True
--    λ> pertenece 4 (inserta 5 (inserta 2 vacio))
--    False
pertenece :: Ord a => a -> Conj a -> Bool
pertenece x (Cj s) = x `elem` takeWhile (<= x) s

-- Generador de conjuntos                                          --
-- ======================

-- genConjunto es un generador de conjuntos. Por ejemplo,
--    λ> sample (genConjunto :: Gen (Conj Int))
--    {}
--    {1}
--    {2}
--    {}
--    {-5, -1}
--    {-9, -8, 2, 3, 10}
--    {4}
--    {-13, -7, 1, 14}
--    {-12, -10, -9, -4, 1, 2, 5, 14, 16}
--    {-18, -15, -14, -13, -10, -7, -6, -4, -1, 1, 10, 11, 12, 16}
--    {-16, -9, -6, -5, -4, -2, 3, 6, 9, 13, 17}
genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)
genConjunto = do
  xs <- listOf arbitrary
  return (foldr inserta vacio xs)

-- Los conjuntos son concreciones de los arbitrarios.
instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where
  arbitrary = genConjunto

-- Propiedades de los conjuntos                                        --
-- ============================

prop_conjuntos :: Int -> Int -> Conj Int -> Bool
prop_conjuntos x y c =
  inserta x (inserta x c) == inserta x c &&
  inserta x (inserta y c) == inserta y (inserta x c) &&
  not (pertenece x vacio) &&
  pertenece y (inserta x c) == (x == y) || pertenece y c &&
  elimina x vacio == vacio &&
  elimina x (inserta y c) == (if x == y
                              then elimina x c
                              else inserta y (elimina x c)) &&
  esVacio (vacio :: Conj Int) &&
  not (esVacio (inserta x c))

-- Comprobación
--    λ> quickCheck prop_conjuntos
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

module TAD.ConjuntoConListasOrdenadasSinDuplicados

(Conj,

vacio, -- Conj a

inserta, -- Ord a => a -> Conj a -> Conj a

menor, -- Ord a => Conj a -> a

elimina, -- Ord a => a -> Conj a -> Conj a

pertenece, -- Ord a => a -> Conj a -> Bool

esVacio -- Conj a -> Bool

) where

import Data.List (intercalate)

import Test.QuickCheck

-- Los conjuntos como listas ordenadas sin repeticiones.

newtype Conj a = Cj [a]

deriving Eq

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

-- ejemplo,

-- λ> escribeConjunto (Cj [])

-- "{}"

-- λ> escribeConjunto (Cj [5])

-- "{5}"

-- λ> escribeConjunto (Cj [2, 5])

-- "{2, 5}"

-- λ> escribeConjunto (Cj [5, 2])

-- "{2, 5}"

escribeConjunto :: Show a => Conj a -> String

escribeConjunto (Cj xs) =

"{" ++ intercalate ", " (map show xs) ++ "}"

-- Procedimiento de escritura de conjuntos.

instance Show a => Show (Conj a) where

show = escribeConjunto

-- vacio es el conjunto vacío. Por ejemplo,

-- λ> vacio

-- {}

vacio :: Conj a

vacio = Cj []

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al

-- conjunto c. Por ejemplo,

-- λ> inserta 5 vacio

-- {5}

-- λ> inserta 2 (inserta 5 vacio)

-- {2, 5}

-- λ> inserta 5 (inserta 2 vacio)

-- {2, 5}

inserta :: Ord a => a -> Conj a -> Conj a

inserta x (Cj s) = Cj (agrega x s)

where agrega z [] = [z]

agrega z s'@(y:ys) | z > y = y : agrega z ys

| z < y = z : s'

| otherwise = s'

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,

-- λ> menor (inserta 5 (inserta 2 vacio))

-- 2

menor :: Ord a => Conj a -> a

menor (Cj []) = error "conjunto vacío"

menor (Cj (x:_)) = x

-- (elimina x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c. Por ejemplo,

-- λ> elimina 2 (inserta 5 (inserta 2 vacio))

-- {5}

elimina :: Ord a => a -> Conj a -> Conj a

elimina x (Cj s) = Cj (elimina' x s)

where elimina' _ [] = []

elimina' z s'@(y:ys) | z > y = y : elimina' z ys

| z < y = s'

| otherwise = ys

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

-- λ> esVacio (inserta 5 (inserta 2 vacio))

-- False

-- λ> esVacio vacio

-- True

esVacio :: Conj a -> Bool

esVacio (Cj xs) = null xs

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

-- λ> pertenece 2 (inserta 5 (inserta 2 vacio))

-- True

-- λ> pertenece 4 (inserta 5 (inserta 2 vacio))

-- False

pertenece :: Ord a => a -> Conj a -> Bool

pertenece x (Cj s) = x `elem` takeWhile (<= x) s

-- Generador de conjuntos --

-- ======================

-- genConjunto es un generador de conjuntos. Por ejemplo,

-- λ> sample (genConjunto :: Gen (Conj Int))

-- {}

-- {1}

-- {2}

-- {}

-- {-5, -1}

-- {-9, -8, 2, 3, 10}

-- {4}

-- {-13, -7, 1, 14}

-- {-12, -10, -9, -4, 1, 2, 5, 14, 16}

-- {-18, -15, -14, -13, -10, -7, -6, -4, -1, 1, 10, 11, 12, 16}

-- {-16, -9, -6, -5, -4, -2, 3, 6, 9, 13, 17}

genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)

genConjunto = do

xs <- listOf arbitrary

return (foldr inserta vacio xs)

-- Los conjuntos son concreciones de los arbitrarios.

instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where

arbitrary = genConjunto

-- Propiedades de los conjuntos --

-- ============================

prop_conjuntos :: Int -> Int -> Conj Int -> Bool

prop_conjuntos x y c =

inserta x (inserta x c) == inserta x c &&

inserta x (inserta y c) == inserta y (inserta x c) &&

not (pertenece x vacio) &&

pertenece y (inserta x c) == (x == y) || pertenece y c &&

elimina x vacio == vacio &&

elimina x (inserta y c) == (if x == y

then elimina x c

else inserta y (elimina x c)) &&

esVacio (vacio :: Conj Int) &&

not (esVacio (inserta x c))

-- Comprobación

-- λ> quickCheck prop_conjuntos

-- +++ OK, passed 100 tests.

2.2.5. Implementación de los conjuntos mediante librería

La implementación se encuentra en el módulo ConjuntoConLibreria.hs cuyo contenido es el siguiente:

module TAD.ConjuntoConLibreria
  (Conj,
   vacio,     -- Conj a
   inserta,   -- Ord a => a -> Conj a -> Conj a
   menor,     -- Ord a => Conj a -> a
   elimina,   -- Ord a => a -> Conj a -> Conj a
   pertenece, -- Ord a => a -> Conj a -> Bool
   esVacio    -- Conj a -> Bool
  ) where

import Data.Set as S (Set, empty, insert, findMin, delete, member, null,
                      fromList, toList)
import Data.List (intercalate)
import Test.QuickCheck

-- Los conjuntos como conjuntos de la librería Data.Set
newtype Conj a = Cj (Set a)
  deriving (Eq, Ord)

-- (escribeConjunto c) es la cadena correspondiente al conjunto c. Por
-- ejemplo,
--    λ> escribeConjunto (Cj (fromList []))
--    "{}"
--    λ> escribeConjunto (Cj (fromList [5]))
--    "{5}"
--    λ> escribeConjunto (Cj (fromList [2, 5]))
--    "{2, 5}"
--    λ> escribeConjunto (Cj (fromList [5, 2]))
--    "{2, 5}"
escribeConjunto :: Show a => Conj a -> String
escribeConjunto (Cj s) =
  "{" ++ intercalate ", " (map show (toList s)) ++ "}"

-- Procedimiento de escritura de conjuntos.
instance Show a => Show (Conj a) where
  show = escribeConjunto

-- vacio es el conjunto vacío. Por ejemplo,
--    λ> vacio
--    {}
vacio :: Conj a
vacio = Cj empty

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al
-- conjunto c. Por ejemplo,
--    λ> inserta 5 vacio
--    {5}
--    λ> inserta 2 (inserta 5 vacio)
--    {2, 5}
--    λ> inserta 5 (inserta 2 vacio)
--    {2, 5}
inserta :: Ord a => a -> Conj a -> Conj a
inserta x (Cj s) = Cj (insert x s)

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,
--    λ> menor (inserta 5 (inserta 2 vacio))
--    2
menor :: Ord a => Conj a -> a
menor (Cj s) = findMin s

-- (elimina x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
--    λ> elimina 2 (inserta 5 (inserta 2 vacio))
--    {5}
elimina :: Ord a => a -> Conj a -> Conj a
elimina x (Cj s) = Cj (delete x s)

-- (esVacio c) se verifica si c es el conjunto vacío. Por ejemplo,
--    λ> esVacio (inserta 5 (inserta 2 vacio))
--    False
--    λ> esVacio vacio
--    True
esVacio :: Conj a -> Bool
esVacio (Cj s) = S.null s

-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo,
--    λ> pertenece 2 (inserta 5 (inserta 2 vacio))
--    True
--    λ> pertenece 4 (inserta 5 (inserta 2 vacio))
--    False
pertenece :: Ord a => a -> Conj a -> Bool
pertenece x (Cj s) = member x s

-- Generador de conjuntos                                          --
-- ======================

-- genConjunto es un generador de conjuntos. Por ejemplo,
--    λ> sample (genConjunto :: Gen (Conj Int))
--    {}
--    {-2, 0}
--    {-1, 3}
--    {-3, 2}
--    {-5, -4, -3, 2, 4, 6, 7}
--    {-4, 4}
--    {-9, -6, -3, 1, 5, 11, 12}
--    {-10, -8, -7, -3, 1, 2, 8, 9, 10, 13}
--    {-13, -8, -7, -6, -1, 0, 1, 6, 7, 9, 11, 14, 16}
--    {-15, -12, -9, 1, 2, 9, 13, 15, 16, 18}
--    {-16}
genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)
genConjunto = do
  xs <- listOf arbitrary
  return (Cj (fromList xs))

-- Los conjuntos son concreciones de los arbitrarios.
instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where
  arbitrary = genConjunto

-- Propiedades de los conjuntos                                        --
-- ============================

prop_conjuntos :: Int -> Int -> Conj Int -> Bool
prop_conjuntos x y c =
  inserta x (inserta x c) == inserta x c &&
  inserta x (inserta y c) == inserta y (inserta x c) &&
  not (pertenece x vacio) &&
  pertenece y (inserta x c) == (x == y) || pertenece y c &&
  elimina x vacio == vacio &&
  elimina x (inserta y c) == (if x == y
                              then elimina x c
                              else inserta y (elimina x c)) &&
  esVacio (vacio :: Conj Int) &&
  not (esVacio (inserta x c))

-- Comprobación
--    λ> quickCheck prop_conjuntos
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

module TAD.ConjuntoConLibreria

(Conj,

vacio, -- Conj a

inserta, -- Ord a => a -> Conj a -> Conj a

menor, -- Ord a => Conj a -> a

elimina, -- Ord a => a -> Conj a -> Conj a

pertenece, -- Ord a => a -> Conj a -> Bool

esVacio -- Conj a -> Bool

) where

import Data.Set as S (Set, empty, insert, findMin, delete, member, null,

fromList, toList)

import Data.List (intercalate)

import Test.QuickCheck

-- Los conjuntos como conjuntos de la librería Data.Set

newtype Conj a = Cj (Set a)

deriving (Eq, Ord)

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

-- ejemplo,

-- λ> escribeConjunto (Cj (fromList []))

-- "{}"

-- λ> escribeConjunto (Cj (fromList [5]))

-- "{5}"

-- λ> escribeConjunto (Cj (fromList [2, 5]))

-- "{2, 5}"

-- λ> escribeConjunto (Cj (fromList [5, 2]))

-- "{2, 5}"

escribeConjunto :: Show a => Conj a -> String

escribeConjunto (Cj s) =

"{" ++ intercalate ", " (map show (toList s)) ++ "}"

-- Procedimiento de escritura de conjuntos.

instance Show a => Show (Conj a) where

show = escribeConjunto

-- vacio es el conjunto vacío. Por ejemplo,

-- λ> vacio

-- {}

vacio :: Conj a

vacio = Cj empty

-- (inserta x c) es el conjunto obtenido añadiendo el elemento x al

-- conjunto c. Por ejemplo,

-- λ> inserta 5 vacio

-- {5}

-- λ> inserta 2 (inserta 5 vacio)

-- {2, 5}

-- λ> inserta 5 (inserta 2 vacio)

-- {2, 5}

inserta :: Ord a => a -> Conj a -> Conj a

inserta x (Cj s) = Cj (insert x s)

-- (menor c) es el menor elemento del conjunto c. Por ejemplo,

-- λ> menor (inserta 5 (inserta 2 vacio))

-- 2

menor :: Ord a => Conj a -> a

menor (Cj s) = findMin s

-- (elimina x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c. Por ejemplo,

-- λ> elimina 2 (inserta 5 (inserta 2 vacio))

-- {5}

elimina :: Ord a => a -> Conj a -> Conj a

elimina x (Cj s) = Cj (delete x s)

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

-- λ> esVacio (inserta 5 (inserta 2 vacio))

-- False

-- λ> esVacio vacio

-- True

esVacio :: Conj a -> Bool

esVacio (Cj s) = S.null s

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

-- λ> pertenece 2 (inserta 5 (inserta 2 vacio))

-- True

-- λ> pertenece 4 (inserta 5 (inserta 2 vacio))

-- False

pertenece :: Ord a => a -> Conj a -> Bool

pertenece x (Cj s) = member x s

-- Generador de conjuntos --

-- ======================

-- genConjunto es un generador de conjuntos. Por ejemplo,

-- λ> sample (genConjunto :: Gen (Conj Int))

-- {}

-- {-2, 0}

-- {-1, 3}

-- {-3, 2}

-- {-5, -4, -3, 2, 4, 6, 7}

-- {-4, 4}

-- {-9, -6, -3, 1, 5, 11, 12}

-- {-10, -8, -7, -3, 1, 2, 8, 9, 10, 13}

-- {-13, -8, -7, -6, -1, 0, 1, 6, 7, 9, 11, 14, 16}

-- {-15, -12, -9, 1, 2, 9, 13, 15, 16, 18}

-- {-16}

genConjunto :: (Arbitrary a, Ord a) => Gen (Conj a)

genConjunto = do

xs <- listOf arbitrary

return (Cj (fromList xs))

-- Los conjuntos son concreciones de los arbitrarios.

instance (Arbitrary a, Ord a) => Arbitrary (Conj a) where

arbitrary = genConjunto

-- Propiedades de los conjuntos --

-- ============================

prop_conjuntos :: Int -> Int -> Conj Int -> Bool

prop_conjuntos x y c =

inserta x (inserta x c) == inserta x c &&

inserta x (inserta y c) == inserta y (inserta x c) &&

not (pertenece x vacio) &&

pertenece y (inserta x c) == (x == y) || pertenece y c &&

elimina x vacio == vacio &&

elimina x (inserta y c) == (if x == y

then elimina x c

else inserta y (elimina x c)) &&

esVacio (vacio :: Conj Int) &&

not (esVacio (inserta x c))

-- Comprobación

-- λ> quickCheck prop_conjuntos

-- +++ OK, passed 100 tests.

2.3. Los conjuntos en Python

2.3.1. El tipo abstracto de los conjuntos en Python

La implementación se encuentra en el módulo conjunto.py cuyo contenido es el siguiente:

__all__ = [
    'Conj',
    'vacio',
    'inserta',
    'menor',
    'elimina',
    'pertenece',
    'esVacio',
    'conjuntoAleatorio'
]

# from src.TAD.conjuntoConListasNoOrdenadasConDuplicados import (
#     Conj, conjuntoAleatorio, elimina, esVacio, inserta,
#     menor, pertenece, vacio)

# from src.TAD.conjuntoConListasNoOrdenadasSinDuplicados import (
#     Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,
#     vacio)

from src.TAD.conjuntoConListasOrdenadasSinDuplicados import (
    Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,
    vacio)

# from src.TAD.conjuntoConLibreria import (
#     Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,
#     vacio)

__all__ = [

'Conj',

'vacio',

'inserta',

'menor',

'elimina',

'pertenece',

'esVacio',

'conjuntoAleatorio'

]

# from src.TAD.conjuntoConListasNoOrdenadasConDuplicados import (

# Conj, conjuntoAleatorio, elimina, esVacio, inserta,

# menor, pertenece, vacio)

# from src.TAD.conjuntoConListasNoOrdenadasSinDuplicados import (

# Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,

# vacio)

from src.TAD.conjuntoConListasOrdenadasSinDuplicados import (

Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,

vacio)

# from src.TAD.conjuntoConLibreria import (

# Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece,

# vacio)

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:

mediante listas no ordenadas con duplicados,
mediante listas no ordenadas sin duplicados,
mediante listas ordenadas sin duplicados y
mediante la librería de conjuntos.

2.3.2. Implementación de los conjuntos mediante listas no ordenadas con duplicados

La implementación se encuentra en el módulo conjuntoConListasNoOrdenadasConDuplicados.py en el que se define la clase Conj con los siguientes métodos:

inserta(x) añade x al conjunto.
menor() es el menor elemento del conjunto.
elimina(x) elimina las ocurrencias de x en el conjunto.
pertenece(x) se verifica si x pertenece al conjunto.
esVacia() se verifica si la cola es vacía.

Por ejemplo,

   >>> c = Conj()
   >>> c
   {}
   >>> c.inserta(5)
   >>> c.inserta(2)
   >>> c.inserta(3)
   >>> c.inserta(4)
   >>> c.inserta(5)
   >>> c
   {2, 3, 4, 5}
   >>> c.menor()
   2
   >>> c.elimina(3)
   >>> c
   {2, 4, 5}
   >>> c.pertenece(4)
   True
   >>> c.pertenece(3)
   False
   >>> c.esVacio()
   False
   >>> c = Conj()
   >>> c.esVacio()
   True
   >>> c = Conj()
   >>> c.inserta(2)
   >>> c.inserta(5)
   >>> d = Conj()
   >>> d.inserta(5)
   >>> d.inserta(2)
   >>> d.inserta(5)
   >>> c == d
   True

>>> c = Conj()

>>> c

{}

>>> c.inserta(5)

>>> c.inserta(2)

>>> c.inserta(3)

>>> c.inserta(4)

>>> c.inserta(5)

>>> c

{2, 3, 4, 5}

>>> c.menor()

>>> c.elimina(3)

>>> c

{2, 4, 5}

>>> c.pertenece(4)

True

>>> c.pertenece(3)

False

>>> c.esVacio()

False

>>> c = Conj()

>>> c.esVacio()

True

>>> c = Conj()

>>> c.inserta(2)

>>> c.inserta(5)

>>> d = Conj()

>>> d.inserta(5)

>>> d.inserta(2)

>>> d.inserta(5)

>>> c == d

True

Además se definen las correspondientes funciones. Por ejemplo,

   >>> vacio()
   {}
   >>> inserta(5, inserta(3, inserta(2, inserta(5, vacio()))))
   {2, 3, 5}
   >>> menor(inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))
   2
   >>> elimina(5, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))
   {2, 3}
   >>> pertenece(5, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))
   True
   >>> pertenece(1, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))
   False
   >>> esVacio(inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))
   False
   >>> esVacio(vacio())
   True
   >>> inserta(5, inserta(2, vacio())) == inserta(2, inserta(5, (inserta(2, vacio()))))
   True

>>> vacio()

{}

>>> inserta(5, inserta(3, inserta(2, inserta(5, vacio()))))

{2, 3, 5}

>>> menor(inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))

>>> elimina(5, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))

{2, 3}

>>> pertenece(5, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))

True

>>> pertenece(1, inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))

False

>>> esVacio(inserta(5, inserta(3, inserta(2, inserta(5, vacio())))))

False

>>> esVacio(vacio())

True

>>> inserta(5, inserta(2, vacio())) == inserta(2, inserta(5, (inserta(2, vacio()))))

True

Finalmente, se define un generador aleatorio de conjuntos y se comprueba que los conjuntos cumplen las propiedades de su especificación.

from __future__ import annotations

__all__ = [
    'Conj',
    'vacio',
    'inserta',
    'menor',
    'elimina',
    'pertenece',
    'esVacio',
    'conjuntoAleatorio'
]

from abc import abstractmethod
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Any, Generic, Protocol, TypeVar

from hypothesis import given
from hypothesis import strategies as st

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# Clase de los conjuntos mediante listas no ordenadas con duplicados
# ==================================================================

@dataclass
class Conj(Generic[A]):
    _elementos: list[A] = field(default_factory=list)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos del conjunto entre llaves
        y separados por ", ".
        """
        return '{' + ', '.join(str(x) for x in sorted(list(set(self._elementos)))) + '}'

    def __eq__(self, c: Any) -> bool:
        """
        Se verifica si el conjunto es igual a c; es decir, tienen los
        mismos elementos sin importar el orden ni las repeticiones.
        """
        return sorted(list(set(self._elementos))) == sorted(list(set(c._elementos)))

    def inserta(self, x: A) -> None:
        """
        Añade el elemento x al conjunto.
        """
        self._elementos.append(x)

    def menor(self) -> A:
        """
        Devuelve el menor elemento del conjunto
        """
        return min(self._elementos)

    def elimina(self, x: A) -> None:
        """
        Elimina el elemento x del conjunto.
        """
        while x in self._elementos:
            self._elementos.remove(x)

    def esVacio(self) -> bool:
        """
        Se verifica si el conjunto está vacío.
        """
        return not self._elementos

    def pertenece(self, x: A) -> bool:
        """
        Se verifica si x pertenece al conjunto.
        """
        return x in self._elementos

# Funciones del tipo conjunto
# ===========================

def vacio() -> Conj[A]:
    """
    Crea y devuelve un conjunto vacío de tipo A.
    """
    c: Conj[A] = Conj()
    return c

def inserta(x: A, c: Conj[A]) -> Conj[A]:
    """
    Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto
    con el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux

def menor(c: Conj[A]) -> A:
    """
    Devuelve el menor elemento del conjunto c.
    """
    return c.menor()

def elimina(x: A, c: Conj[A]) -> Conj[A]:
    """
    Elimina las ocurrencias de c en c y devuelve una copia del conjunto
    resultante.
    """
    _aux = deepcopy(c)
    _aux.elimina(x)
    return _aux

def pertenece(x: A, c: Conj[A]) -> bool:
    """
    Se verifica si x pertenece a c.
    """
    return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:
    """
    Se verifica si el conjunto está vacío.
    """
    return c.esVacio()

# Generador de conjuntos
# ======================

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:
    """
    Genera una estrategia de búsqueda para generar conjuntos de enteros
    de forma aleatoria.

    Utiliza la librería Hypothesis para generar una lista de enteros y
    luego se convierte en una instancia de la clase cola.
    """
    return st.lists(st.integers()).map(Conj)

# Comprobación de las propiedades de los conjuntos
# ================================================

# Las propiedades son
@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())
def test_conjuntos(c: Conj[int], x: int, y: int) -> None:
    v: Conj[int] = vacio()
    assert inserta(x, inserta(x, c)) == inserta(x, c)
    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))
    assert not pertenece(x, v)
    assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)
    assert elimina(x, v) == v

    def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:
        if x == y:
            return elimina(x, c)
        return inserta(y, elimina(x, c))

    assert elimina(x, inserta(y, c)) == relacion(x, y, c)
    assert esVacio(vacio())
    assert not esVacio(inserta(x, c))

# La comprobación es
#    > poetry run pytest -q conjuntoConListasNoOrdenadasConDuplicados.py
#    1 passed in 0.33s

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

from __future__ import annotations

__all__ = [

'Conj',

'vacio',

'inserta',

'menor',

'elimina',

'pertenece',

'esVacio',

'conjuntoAleatorio'

]

from abc import abstractmethod

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Any, Generic, Protocol, TypeVar

from hypothesis import given

from hypothesis import strategies as st

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# Clase de los conjuntos mediante listas no ordenadas con duplicados

# ==================================================================

@dataclass

class Conj(Generic[A]):

_elementos: list[A] = field(default_factory=list)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos del conjunto entre llaves

y separados por ", ".

"""

return '{' + ', '.join(str(x) for x in sorted(list(set(self._elementos)))) + '}'

def __eq__(self, c: Any) -> bool:

"""

Se verifica si el conjunto es igual a c; es decir, tienen los

mismos elementos sin importar el orden ni las repeticiones.

"""

return sorted(list(set(self._elementos))) == sorted(list(set(c._elementos)))

def inserta(self, x: A) -> None:

"""

Añade el elemento x al conjunto.

"""

self._elementos.append(x)

def menor(self) -> A:

"""

Devuelve el menor elemento del conjunto

"""

return min(self._elementos)

def elimina(self, x: A) -> None:

"""

Elimina el elemento x del conjunto.

"""

while x in self._elementos:

self._elementos.remove(x)

def esVacio(self) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return not self._elementos

def pertenece(self, x: A) -> bool:

"""

Se verifica si x pertenece al conjunto.

"""

return x in self._elementos

# Funciones del tipo conjunto

# ===========================

def vacio() -> Conj[A]:

"""

Crea y devuelve un conjunto vacío de tipo A.

"""

c: Conj[A] = Conj()

return c

def inserta(x: A, c: Conj[A]) -> Conj[A]:

"""

Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto

con el elemento insertado.

"""

_aux = deepcopy(c)

_aux.inserta(x)

return _aux

def menor(c: Conj[A]) -> A:

"""

Devuelve el menor elemento del conjunto c.

"""

return c.menor()

def elimina(x: A, c: Conj[A]) -> Conj[A]:

"""

Elimina las ocurrencias de c en c y devuelve una copia del conjunto

resultante.

"""

_aux = deepcopy(c)

_aux.elimina(x)

return _aux

def pertenece(x: A, c: Conj[A]) -> bool:

"""

Se verifica si x pertenece a c.

"""

return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return c.esVacio()

# Generador de conjuntos

# ======================

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:

"""

Genera una estrategia de búsqueda para generar conjuntos de enteros

de forma aleatoria.

Utiliza la librería Hypothesis para generar una lista de enteros y

luego se convierte en una instancia de la clase cola.

"""

return st.lists(st.integers()).map(Conj)

# Comprobación de las propiedades de los conjuntos

# ================================================

# Las propiedades son

@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())

def test_conjuntos(c: Conj[int], x: int, y: int) -> None:

v: Conj[int] = vacio()

assert inserta(x, inserta(x, c)) == inserta(x, c)

assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))

assert not pertenece(x, v)

assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)

assert elimina(x, v) == v

def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:

if x == y:

return elimina(x, c)

return inserta(y, elimina(x, c))

assert elimina(x, inserta(y, c)) == relacion(x, y, c)

assert esVacio(vacio())

assert not esVacio(inserta(x, c))

# La comprobación es

# > poetry run pytest -q conjuntoConListasNoOrdenadasConDuplicados.py

# 1 passed in 0.33s

2.3.3. Implementación de los conjuntos mediante listas no ordenadas sin duplicados

La implementación se encuentra en el módulo conjuntoConListasNoOrdenadasSinDuplicados.py cuyo contenido es

from __future__ import annotations

__all__ = [
    'Conj',
    'vacio',
    'inserta',
    'menor',
    'elimina',
    'pertenece',
    'esVacio',
    'conjuntoAleatorio'
]

from abc import abstractmethod
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Any, Generic, Protocol, TypeVar

from hypothesis import given
from hypothesis import strategies as st

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# Clase de los conjuntos mediante listas no ordenadas sin duplicados
# ==================================================================

@dataclass
class Conj(Generic[A]):
    _elementos: list[A] = field(default_factory=list)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos del conjunto entre llaves
        y separados por ", ".
        """
        return '{' + ', '.join(str(x) for x in sorted(self._elementos)) + '}'

    def __eq__(self, c: Any) -> bool:
        """
        Se verifica si el conjunto es igual a c; es decir, tienen los
        mismos elementos sin importar el orden ni las repeticiones.
        """
        return sorted(self._elementos) == sorted(c._elementos)

    def inserta(self, x: A) -> None:
        """
        Añade el elemento x al conjunto.
        """
        if x not in self._elementos:
            self._elementos.append(x)

    def menor(self) -> A:
        """
        Devuelve el menor elemento del conjunto
        """
        return min(self._elementos)

    def elimina(self, x: A) -> None:
        """
        Elimina el elemento x del conjunto.
        """
        if x in self._elementos:
            self._elementos.remove(x)

    def esVacio(self) -> bool:
        """
        Se verifica si el conjunto está vacío.
        """
        return not self._elementos

    def pertenece(self, x: A) -> bool:
        """
        Se verifica si x pertenece al conjunto.
        """
        return x in self._elementos

# Funciones del tipo conjunto
# ===========================

def vacio() -> Conj[A]:
    """
    Crea y devuelve un conjunto vacío de tipo A.
    """
    c: Conj[A] = Conj()
    return c

def inserta(x: A, c: Conj[A]) -> Conj[A]:
    """
    Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto
    con el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux

def menor(c: Conj[A]) -> A:
    """
    Devuelve el menor elemento del conjunto c.
    """
    return c.menor()

def elimina(x: A, c: Conj[A]) -> Conj[A]:
    """
    Elimina las ocurrencias de c en c y devuelve una copia del conjunto
    resultante.
    """
    _aux = deepcopy(c)
    _aux.elimina(x)
    return _aux

def pertenece(x: A, c: Conj[A]) -> bool:
    """
    Se verifica si x pertenece a c.
    """
    return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:
    """
    Se verifica si el conjunto está vacío.
    """
    return c.esVacio()

# Generador de conjuntos
# ======================

def sin_duplicados(xs: list[int]) -> list[int]:
    return list(set(xs))

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:
    """
    Estrategia de búsqueda para generar conjuntos de enteros de forma
    aleatoria.
    """
    xs = st.lists(st.integers()).map(sin_duplicados)
    return xs.map(Conj)

# Comprobación de las propiedades de los conjuntos
# ================================================

# Las propiedades son
@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())
def test_conjuntos(c: Conj[int], x: int, y: int) -> None:
    assert inserta(x, inserta(x, c)) == inserta(x, c)
    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))
    assert not pertenece(x, vacio())
    assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)
    assert elimina(x, vacio()) == vacio()

    def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:
        if x == y:
            return elimina(x, c)
        return inserta(y, elimina(x, c))

    assert elimina(x, inserta(y, c)) == relacion(x, y, c)
    assert esVacio(vacio())
    assert not esVacio(inserta(x, c))

# La comprobación es
#    > poetry run pytest -q conjuntoConListasNoOrdenadasSinDuplicados.py
#    1 passed in 0.26s

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

from __future__ import annotations

__all__ = [

'Conj',

'vacio',

'inserta',

'menor',

'elimina',

'pertenece',

'esVacio',

'conjuntoAleatorio'

]

from abc import abstractmethod

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Any, Generic, Protocol, TypeVar

from hypothesis import given

from hypothesis import strategies as st

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# Clase de los conjuntos mediante listas no ordenadas sin duplicados

# ==================================================================

@dataclass

class Conj(Generic[A]):

_elementos: list[A] = field(default_factory=list)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos del conjunto entre llaves

y separados por ", ".

"""

return '{' + ', '.join(str(x) for x in sorted(self._elementos)) + '}'

def __eq__(self, c: Any) -> bool:

"""

Se verifica si el conjunto es igual a c; es decir, tienen los

mismos elementos sin importar el orden ni las repeticiones.

"""

return sorted(self._elementos) == sorted(c._elementos)

def inserta(self, x: A) -> None:

"""

Añade el elemento x al conjunto.

"""

if x not in self._elementos:

self._elementos.append(x)

def menor(self) -> A:

"""

Devuelve el menor elemento del conjunto

"""

return min(self._elementos)

def elimina(self, x: A) -> None:

"""

Elimina el elemento x del conjunto.

"""

if x in self._elementos:

self._elementos.remove(x)

def esVacio(self) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return not self._elementos

def pertenece(self, x: A) -> bool:

"""

Se verifica si x pertenece al conjunto.

"""

return x in self._elementos

# Funciones del tipo conjunto

# ===========================

def vacio() -> Conj[A]:

"""

Crea y devuelve un conjunto vacío de tipo A.

"""

c: Conj[A] = Conj()

return c

def inserta(x: A, c: Conj[A]) -> Conj[A]:

"""

Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto

con el elemento insertado.

"""

_aux = deepcopy(c)

_aux.inserta(x)

return _aux

def menor(c: Conj[A]) -> A:

"""

Devuelve el menor elemento del conjunto c.

"""

return c.menor()

def elimina(x: A, c: Conj[A]) -> Conj[A]:

"""

Elimina las ocurrencias de c en c y devuelve una copia del conjunto

resultante.

"""

_aux = deepcopy(c)

_aux.elimina(x)

return _aux

def pertenece(x: A, c: Conj[A]) -> bool:

"""

Se verifica si x pertenece a c.

"""

return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return c.esVacio()

# Generador de conjuntos

# ======================

def sin_duplicados(xs: list[int]) -> list[int]:

return list(set(xs))

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:

"""

Estrategia de búsqueda para generar conjuntos de enteros de forma

aleatoria.

"""

xs = st.lists(st.integers()).map(sin_duplicados)

return xs.map(Conj)

# Comprobación de las propiedades de los conjuntos

# ================================================

# Las propiedades son

@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())

def test_conjuntos(c: Conj[int], x: int, y: int) -> None:

assert inserta(x, inserta(x, c)) == inserta(x, c)

assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))

assert not pertenece(x, vacio())

assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)

assert elimina(x, vacio()) == vacio()

def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:

if x == y:

return elimina(x, c)

return inserta(y, elimina(x, c))

assert elimina(x, inserta(y, c)) == relacion(x, y, c)

assert esVacio(vacio())

assert not esVacio(inserta(x, c))

# La comprobación es

# > poetry run pytest -q conjuntoConListasNoOrdenadasSinDuplicados.py

# 1 passed in 0.26s

2.3.4. Implementación de los conjuntos mediante listas ordenadas sin duplicados

La implementación se encuentra en el módulo conjuntoConListasOrdenadasSinDuplicados.py cuyo contenido es el siguiente:

from __future__ import annotations

__all__ = [
    'Conj',
    'vacio',
    'inserta',
    'menor',
    'elimina',
    'pertenece',
    'esVacio',
    'conjuntoAleatorio'
]

from abc import abstractmethod
from bisect import bisect_left, insort_left
from copy import deepcopy
from dataclasses import dataclass, field
from itertools import takewhile
from typing import Generic, Protocol, TypeVar

from hypothesis import given
from hypothesis import strategies as st

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# Clase de los conjuntos mediante listas ordenadas sin duplicados
# ===============================================================

@dataclass
class Conj(Generic[A]):
    _elementos: list[A] = field(default_factory=list)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos del conjunto entre llaves
        y separados por ", ".
        """
        return '{' + ', '.join(str(x) for x in self._elementos) + '}'

    def inserta(self, x: A) -> None:
        """
        Añade el elemento x al conjunto.
        """
        if x not in self._elementos:
            insort_left(self._elementos, x)

    def menor(self) -> A:
        """
        Devuelve el menor elemento del conjunto
        """
        return self._elementos[0]

    def elimina(self, x: A) -> None:
        """
        Elimina el elemento x del conjunto.
        """
        pos = bisect_left(self._elementos, x)
        if pos < len(self._elementos) and self._elementos[pos] == x:
            self._elementos.pop(pos)

    def esVacio(self) -> bool:
        """
        Se verifica si el conjunto está vacío.
        """
        return not self._elementos

    def pertenece(self, x: A) -> bool:
        """
        Se verifica si x pertenece al conjunto.
        """
        return x in takewhile(lambda y: y <= x, self._elementos)

# Funciones del tipo conjunto
# ===========================

def vacio() -> Conj[A]:
    """
    Crea y devuelve un conjunto vacío de tipo A.
    """
    c: Conj[A] = Conj()
    return c

def inserta(x: A, c: Conj[A]) -> Conj[A]:
    """
    Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto
    con el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux

def menor(c: Conj[A]) -> A:
    """
    Devuelve el menor elemento del conjunto c.
    """
    return c.menor()

def elimina(x: A, c: Conj[A]) -> Conj[A]:
    """
    Elimina las ocurrencias de c en c y devuelve una copia del conjunto
    resultante.
    """
    _aux = deepcopy(c)
    _aux.elimina(x)
    return _aux

def pertenece(x: A, c: Conj[A]) -> bool:
    """
    Se verifica si x pertenece a c.
    """
    return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:
    """
    Se verifica si el conjunto está vacío.
    """
    return c.esVacio()

# Generador de conjuntos
# ======================

def sin_duplicados_y_ordenado(xs: list[int]) -> list[int]:
    xs = list(set(xs))
    xs.sort()
    return xs

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:
    """
    Estrategia de búsqueda para generar conjuntos de enteros de forma
    aleatoria.
    """
    xs = st.lists(st.integers()).map(sin_duplicados_y_ordenado)
    return xs.map(Conj)

# Comprobación de las propiedades de los conjuntos
# ================================================

# Las propiedades son
@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())
def test_conjuntos(c: Conj[int], x: int, y: int) -> None:
    assert inserta(x, inserta(x, c)) == inserta(x, c)
    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))
    assert not pertenece(x, vacio())
    assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)
    assert elimina(x, vacio()) == vacio()

    def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:
        if x == y:
            return elimina(x, c)
        return inserta(y, elimina(x, c))

    assert elimina(x, inserta(y, c)) == relacion(x, y, c)
    assert esVacio(vacio())
    assert not esVacio(inserta(x, c))

# La comprobación es
#    > poetry run pytest -q conjuntoConListasOrdenadasSinDuplicados.py
#    1 passed in 0.13s

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

from __future__ import annotations

__all__ = [

'Conj',

'vacio',

'inserta',

'menor',

'elimina',

'pertenece',

'esVacio',

'conjuntoAleatorio'

]

from abc import abstractmethod

from bisect import bisect_left, insort_left

from copy import deepcopy

from dataclasses import dataclass, field

from itertools import takewhile

from typing import Generic, Protocol, TypeVar

from hypothesis import given

from hypothesis import strategies as st

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# Clase de los conjuntos mediante listas ordenadas sin duplicados

# ===============================================================

@dataclass

class Conj(Generic[A]):

_elementos: list[A] = field(default_factory=list)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos del conjunto entre llaves

y separados por ", ".

"""

return '{' + ', '.join(str(x) for x in self._elementos) + '}'

def inserta(self, x: A) -> None:

"""

Añade el elemento x al conjunto.

"""

if x not in self._elementos:

insort_left(self._elementos, x)

def menor(self) -> A:

"""

Devuelve el menor elemento del conjunto

"""

return self._elementos[0]

def elimina(self, x: A) -> None:

"""

Elimina el elemento x del conjunto.

"""

pos = bisect_left(self._elementos, x)

if pos < len(self._elementos) and self._elementos[pos] == x:

self._elementos.pop(pos)

def esVacio(self) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return not self._elementos

def pertenece(self, x: A) -> bool:

"""

Se verifica si x pertenece al conjunto.

"""

return x in takewhile(lambda y: y <= x, self._elementos)

# Funciones del tipo conjunto

# ===========================

def vacio() -> Conj[A]:

"""

Crea y devuelve un conjunto vacío de tipo A.

"""

c: Conj[A] = Conj()

return c

def inserta(x: A, c: Conj[A]) -> Conj[A]:

"""

Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto

con el elemento insertado.

"""

_aux = deepcopy(c)

_aux.inserta(x)

return _aux

def menor(c: Conj[A]) -> A:

"""

Devuelve el menor elemento del conjunto c.

"""

return c.menor()

def elimina(x: A, c: Conj[A]) -> Conj[A]:

"""

Elimina las ocurrencias de c en c y devuelve una copia del conjunto

resultante.

"""

_aux = deepcopy(c)

_aux.elimina(x)

return _aux

def pertenece(x: A, c: Conj[A]) -> bool:

"""

Se verifica si x pertenece a c.

"""

return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return c.esVacio()

# Generador de conjuntos

# ======================

def sin_duplicados_y_ordenado(xs: list[int]) -> list[int]:

xs = list(set(xs))

xs.sort()

return xs

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:

"""

Estrategia de búsqueda para generar conjuntos de enteros de forma

aleatoria.

"""

xs = st.lists(st.integers()).map(sin_duplicados_y_ordenado)

return xs.map(Conj)

# Comprobación de las propiedades de los conjuntos

# ================================================

# Las propiedades son

@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())

def test_conjuntos(c: Conj[int], x: int, y: int) -> None:

assert inserta(x, inserta(x, c)) == inserta(x, c)

assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))

assert not pertenece(x, vacio())

assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)

assert elimina(x, vacio()) == vacio()

def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:

if x == y:

return elimina(x, c)

return inserta(y, elimina(x, c))

assert elimina(x, inserta(y, c)) == relacion(x, y, c)

assert esVacio(vacio())

assert not esVacio(inserta(x, c))

# La comprobación es

# > poetry run pytest -q conjuntoConListasOrdenadasSinDuplicados.py

# 1 passed in 0.13s

2.3.5. Implementación de los conjuntos mediante librería

La implementación se encuentra en el módulo conjuntoConLibreria.py cuyo contenido es el siguiente:

from __future__ import annotations

__all__ = [
    'Conj',
    'vacio',
    'inserta',
    'menor',
    'elimina',
    'pertenece',
    'esVacio',
    'conjuntoAleatorio'
]

from abc import abstractmethod
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, Protocol, TypeVar

from hypothesis import given
from hypothesis import strategies as st

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# Clase de los conjuntos mediante librería
# ========================================

@dataclass
class Conj(Generic[A]):
    _elementos: set[A] = field(default_factory=set)

    def __repr__(self) -> str:
        xs = [str(x) for x in self._elementos]
        return "{" + ", ".join(xs) + "}"

    def inserta(self, x: A) -> None:
        """
        Añade el elemento x al conjunto.
        """
        self._elementos.add(x)

    def menor(self) -> A:
        """
        Devuelve el menor elemento del conjunto
        """
        return min(self._elementos)

    def elimina(self, x: A) -> None:
        """
        Elimina el elemento x del conjunto.
        """
        self._elementos.discard(x)

    def esVacio(self) -> bool:
        """
        Se verifica si el conjunto está vacío.
        """
        return not self._elementos

    def pertenece(self, x: A) -> bool:
        """
        Se verifica si x pertenece al conjunto.
        """
        return x in self._elementos

# Funciones del tipo conjunto
# ===========================

def vacio() -> Conj[A]:
    """
    Crea y devuelve un conjunto vacío de tipo A.
    """
    c: Conj[A] = Conj()
    return c

def inserta(x: A, c: Conj[A]) -> Conj[A]:
    """
    Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto
    con el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux

def menor(c: Conj[A]) -> A:
    """
    Devuelve el menor elemento del conjunto c.
    """
    return c.menor()

def elimina(x: A, c: Conj[A]) -> Conj[A]:
    """
    Elimina las ocurrencias de c en c y devuelve una copia del conjunto
    resultante.
    """
    _aux = deepcopy(c)
    _aux.elimina(x)
    return _aux

def pertenece(x: A, c: Conj[A]) -> bool:
    """
    Se verifica si x pertenece a c.
    """
    return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:
    """
    Se verifica si el conjunto está vacío.
    """
    return c.esVacio()

# Generador de conjuntos
# ======================

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:
    """
    Estrategia de búsqueda para generar conjuntos de enteros de forma
    aleatoria.
    """
    return st.builds(Conj, st.lists(st.integers()).map(set))

# Comprobación de las propiedades de los conjuntos
# ================================================

# Las propiedades son
@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())
def test_conjuntos(c: Conj[int], x: int, y: int) -> None:
    assert inserta(x, inserta(x, c)) == inserta(x, c)
    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))
    assert not pertenece(x, vacio())
    assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)
    assert elimina(x, vacio()) == vacio()

    def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:
        if x == y:
            return elimina(x, c)
        return inserta(y, elimina(x, c))

    assert elimina(x, inserta(y, c)) == relacion(x, y, c)
    assert esVacio(vacio())
    assert not esVacio(inserta(x, c))

# La comprobación es
#    > poetry run pytest -q conjuntoConLibreria.py
#    1 passed in 0.22s

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

from __future__ import annotations

__all__ = [

'Conj',

'vacio',

'inserta',

'menor',

'elimina',

'pertenece',

'esVacio',

'conjuntoAleatorio'

]

from abc import abstractmethod

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Generic, Protocol, TypeVar

from hypothesis import given

from hypothesis import strategies as st

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# Clase de los conjuntos mediante librería

# ========================================

@dataclass

class Conj(Generic[A]):

_elementos: set[A] = field(default_factory=set)

def __repr__(self) -> str:

xs = [str(x) for x in self._elementos]

return "{" + ", ".join(xs) + "}"

def inserta(self, x: A) -> None:

"""

Añade el elemento x al conjunto.

"""

self._elementos.add(x)

def menor(self) -> A:

"""

Devuelve el menor elemento del conjunto

"""

return min(self._elementos)

def elimina(self, x: A) -> None:

"""

Elimina el elemento x del conjunto.

"""

self._elementos.discard(x)

def esVacio(self) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return not self._elementos

def pertenece(self, x: A) -> bool:

"""

Se verifica si x pertenece al conjunto.

"""

return x in self._elementos

# Funciones del tipo conjunto

# ===========================

def vacio() -> Conj[A]:

"""

Crea y devuelve un conjunto vacío de tipo A.

"""

c: Conj[A] = Conj()

return c

def inserta(x: A, c: Conj[A]) -> Conj[A]:

"""

Inserta un elemento x en el conjunto c y devuelve un nuevo comjunto

con el elemento insertado.

"""

_aux = deepcopy(c)

_aux.inserta(x)

return _aux

def menor(c: Conj[A]) -> A:

"""

Devuelve el menor elemento del conjunto c.

"""

return c.menor()

def elimina(x: A, c: Conj[A]) -> Conj[A]:

"""

Elimina las ocurrencias de c en c y devuelve una copia del conjunto

resultante.

"""

_aux = deepcopy(c)

_aux.elimina(x)

return _aux

def pertenece(x: A, c: Conj[A]) -> bool:

"""

Se verifica si x pertenece a c.

"""

return c.pertenece(x)

def esVacio(c: Conj[A]) -> bool:

"""

Se verifica si el conjunto está vacío.

"""

return c.esVacio()

# Generador de conjuntos

# ======================

def conjuntoAleatorio() -> st.SearchStrategy[Conj[int]]:

"""

Estrategia de búsqueda para generar conjuntos de enteros de forma

aleatoria.

"""

return st.builds(Conj, st.lists(st.integers()).map(set))

# Comprobación de las propiedades de los conjuntos

# ================================================

# Las propiedades son

@given(c=conjuntoAleatorio(), x=st.integers(), y=st.integers())

def test_conjuntos(c: Conj[int], x: int, y: int) -> None:

assert inserta(x, inserta(x, c)) == inserta(x, c)

assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))

assert not pertenece(x, vacio())

assert pertenece(y, inserta(x, c)) == (x == y) or pertenece(y, c)

assert elimina(x, vacio()) == vacio()

def relacion(x: int, y: int, c: Conj[int]) -> Conj[int]:

if x == y:

return elimina(x, c)

return inserta(y, elimina(x, c))

assert elimina(x, inserta(y, c)) == relacion(x, y, c)

assert esVacio(vacio())

assert not esVacio(inserta(x, c))

# La comprobación es

# > poetry run pytest -q conjuntoConLibreria.py

# 1 passed in 0.22s

3. TAD de los conjuntos: Transformaciones entre conjuntos y listas

Utilizando el tipo abstracto de datos de los conjuntos definir las funciones

   listaAconjunto :: [a] -> Conj a
   conjuntoAlista :: Conj a -> [a]

1 2	listaAconjunto :: [a] -> Conj a conjuntoAlista :: Conj a -> [a]

tales que
+ listaAconjunto xs es el conjunto formado por los elementos de xs. Por ejemplo,

     λ> listaAconjunto [3, 2, 5]
     {2, 3, 5}

1 2	λ> listaAconjunto [3, 2, 5] {2, 3, 5}

conjuntoAlista c es la lista formada por los elementos del conjunto c. Por ejemplo,

     λ> conjuntoAlista (inserta 5 (inserta 2 (inserta 3 vacio)))
     [2,3,5]

1 2	λ> conjuntoAlista (inserta 5 (inserta 2 (inserta 3 vacio))) [2,3,5]

Comprobar con QuickCheck que ambas funciones son inversa; es decir,

   conjuntoAlista (listaAconjunto xs) = sort (nub xs)
   listaAconjunto (conjuntoAlista c)  = c

1 2	conjuntoAlista (listaAconjunto xs) = sort (nub xs) listaAconjunto (conjuntoAlista c) = c

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)
import Data.List (sort, nub)
import Test.QuickCheck

-- 1ª definición de listaAconjunto
-- ===============================

listaAconjunto :: Ord a => [a] -> Conj a
listaAconjunto []     = vacio
listaAconjunto (x:xs) = inserta x (listaAconjunto xs)

-- 2ª definición de listaAconjunto
-- ===============================

listaAconjunto2 :: Ord a => [a] -> Conj a
listaAconjunto2 = foldr inserta vacio

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_listaAconjunto :: [Int] -> Bool
prop_listaAconjunto xs =
  listaAconjunto xs == listaAconjunto2 xs

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

-- Definición de conjuntoAlista
-- ============================

conjuntoAlista :: Ord a => Conj a -> [a]
conjuntoAlista c
  | esVacio c = []
  | otherwise = mc : conjuntoAlista rc
  where mc = menor c
        rc = elimina mc c

-- Comprobación de las propiedades
-- ===============================

-- La primera propiedad es
prop_1_listaAconjunto :: [Int] -> Bool
prop_1_listaAconjunto xs =
  conjuntoAlista (listaAconjunto xs) == sort (nub xs)

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

-- La segunda propiedad es
prop_2_listaAconjunto :: Conj Int -> Bool
prop_2_listaAconjunto c =
  listaAconjunto (conjuntoAlista c) == c

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

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)

import Data.List (sort, nub)

import Test.QuickCheck

-- 1ª definición de listaAconjunto

-- ===============================

listaAconjunto :: Ord a => [a] -> Conj a

listaAconjunto [] = vacio

listaAconjunto (x:xs) = inserta x (listaAconjunto xs)

-- 2ª definición de listaAconjunto

-- ===============================

listaAconjunto2 :: Ord a => [a] -> Conj a

listaAconjunto2 = foldr inserta vacio

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_listaAconjunto :: [Int] -> Bool

prop_listaAconjunto xs =

listaAconjunto xs == listaAconjunto2 xs

-- La comprobación es

-- λ> quickCheck prop_listaAconjunto

-- +++ OK, passed 100 tests.

-- Definición de conjuntoAlista

-- ============================

conjuntoAlista :: Ord a => Conj a -> [a]

conjuntoAlista c

| esVacio c = []

| otherwise = mc : conjuntoAlista rc

where mc = menor c

rc = elimina mc c

-- Comprobación de las propiedades

-- ===============================

-- La primera propiedad es

prop_1_listaAconjunto :: [Int] -> Bool

prop_1_listaAconjunto xs =

conjuntoAlista (listaAconjunto xs) == sort (nub xs)

-- La comprobación es

-- λ> quickCheck prop_1_listaAconjunto

-- +++ OK, passed 100 tests.

-- La segunda propiedad es

prop_2_listaAconjunto :: Conj Int -> Bool

prop_2_listaAconjunto c =

listaAconjunto (conjuntoAlista c) == c

-- La comprobación es

-- λ> quickCheck prop_2_listaAconjunto

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from functools import reduce
from typing import Protocol, TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª definición de listaAconjunto
# ===============================

def listaAconjunto(xs: list[A]) -> Conj[A]:
    if not xs:
        return vacio()
    return inserta(xs[0], listaAconjunto(xs[1:]))

# 2ª definición de listaAconjunto
# ===============================

def listaAconjunto2(xs: list[A]) -> Conj[A]:
    return reduce(lambda ys, y: inserta(y, ys), xs, vacio())

# 3ª solución de listaAconjunto
# =============================

def listaAconjunto3(xs: list[A]) -> Conj[A]:
    c: Conj[A] = Conj()
    for x in xs:
        c.inserta(x)
    return c

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.lists(st.integers()))
def test_listaAconjunto(xs: list[int]) -> None:
    r = listaAconjunto(xs)
    assert listaAconjunto2(xs) == r
    assert listaAconjunto3(xs) == r

# 1ª definición de conjuntoAlista
# ===============================

def conjuntoAlista(c: Conj[A]) -> list[A]:
    if esVacio(c):
        return []
    mc = menor(c)
    rc = elimina(mc, c)
    return [mc] + conjuntoAlista(rc)

# 2ª definición de conjuntoAlista
# ===============================

def conjuntoAlista2Aux(c: Conj[A]) -> list[A]:
    if c.esVacio():
        return []
    mc = c.menor()
    c.elimina(mc)
    return [mc] + conjuntoAlista2Aux(c)

def conjuntoAlista2(c: Conj[A]) -> list[A]:
    c1 = deepcopy(c)
    return conjuntoAlista2Aux(c1)

# 3ª definición de conjuntoAlista
# ===============================

def conjuntoAlista3Aux(c: Conj[A]) -> list[A]:
    r = []
    while not c.esVacio():
        mc = c.menor()
        r.append(mc)
        c.elimina(mc)
    return r

def conjuntoAlista3(c: Conj[A]) -> list[A]:
    c1 = deepcopy(c)
    return conjuntoAlista3Aux(c1)

# Comprobación de equivalencia de las definiciones de conjuntoAlista
# ==============================================================

@given(c=conjuntoAleatorio())
def test_conjuntoAlista(c: Conj[int]) -> None:
    r = conjuntoAlista(c)
    assert conjuntoAlista2(c) == r
    assert conjuntoAlista3(c) == r

# Comprobación de las propiedades
# ===============================

# La primera propiedad es
@given(st.lists(st.integers()))
def test_1_listaAconjunto(xs: list[int]) -> None:
    assert conjuntoAlista(listaAconjunto(xs)) == sorted(list(set(xs)))

# La segunda propiedad es
@given(c=conjuntoAleatorio())
def test_2_listaAconjunto(c: Conj[int]) -> None:
    assert listaAconjunto(conjuntoAlista(c)) == c

# La comprobación de las propiedades es
#    > poetry run pytest -v TAD_Transformaciones_conjuntos_listas.py
#       test_listaAconjunto PASSED
#       test_conjuntoAlista PASSED
#       test_1_listaAconjunto PASSED
#       test_2_listaAconjunto PASSED

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

from __future__ import annotations

from abc import abstractmethod

from copy import deepcopy

from functools import reduce

from typing import Protocol, TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, pertenece, vacio)

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª definición de listaAconjunto

# ===============================

def listaAconjunto(xs: list[A]) -> Conj[A]:

if not xs:

return vacio()

return inserta(xs[0], listaAconjunto(xs[1:]))

# 2ª definición de listaAconjunto

# ===============================

def listaAconjunto2(xs: list[A]) -> Conj[A]:

return reduce(lambda ys, y: inserta(y, ys), xs, vacio())

# 3ª solución de listaAconjunto

# =============================

def listaAconjunto3(xs: list[A]) -> Conj[A]:

c: Conj[A] = Conj()

for x in xs:

c.inserta(x)

return c

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(st.integers()))

def test_listaAconjunto(xs: list[int]) -> None:

r = listaAconjunto(xs)

assert listaAconjunto2(xs) == r

assert listaAconjunto3(xs) == r

# 1ª definición de conjuntoAlista

# ===============================

def conjuntoAlista(c: Conj[A]) -> list[A]:

if esVacio(c):

return []

mc = menor(c)

rc = elimina(mc, c)

return [mc] + conjuntoAlista(rc)

# 2ª definición de conjuntoAlista

# ===============================

def conjuntoAlista2Aux(c: Conj[A]) -> list[A]:

if c.esVacio():

return []

mc = c.menor()

c.elimina(mc)

return [mc] + conjuntoAlista2Aux(c)

def conjuntoAlista2(c: Conj[A]) -> list[A]:

c1 = deepcopy(c)

return conjuntoAlista2Aux(c1)

# 3ª definición de conjuntoAlista

# ===============================

def conjuntoAlista3Aux(c: Conj[A]) -> list[A]:

r = []

while not c.esVacio():

mc = c.menor()

r.append(mc)

c.elimina(mc)

return r

def conjuntoAlista3(c: Conj[A]) -> list[A]:

c1 = deepcopy(c)

return conjuntoAlista3Aux(c1)

# Comprobación de equivalencia de las definiciones de conjuntoAlista

# ==============================================================

@given(c=conjuntoAleatorio())

def test_conjuntoAlista(c: Conj[int]) -> None:

r = conjuntoAlista(c)

assert conjuntoAlista2(c) == r

assert conjuntoAlista3(c) == r

# Comprobación de las propiedades

# ===============================

# La primera propiedad es

@given(st.lists(st.integers()))

def test_1_listaAconjunto(xs: list[int]) -> None:

assert conjuntoAlista(listaAconjunto(xs)) == sorted(list(set(xs)))

# La segunda propiedad es

@given(c=conjuntoAleatorio())

def test_2_listaAconjunto(c: Conj[int]) -> None:

assert listaAconjunto(conjuntoAlista(c)) == c

# La comprobación de las propiedades es

# > poetry run pytest -v TAD_Transformaciones_conjuntos_listas.py

# test_listaAconjunto PASSED

# test_conjuntoAlista PASSED

# test_1_listaAconjunto PASSED

# test_2_listaAconjunto PASSED

4. TAD de los conjuntos: Reconocimiento de subconjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

   subconjunto :: Ord a => Conj a -> Conj a -> Bool

1	subconjunto :: Ord a => Conj a -> Conj a -> Bool

tal que subconjunto c1 c2 se verifica si todos los elementos de c1 pertenecen a c2. Por ejemplo,

   λ> ej1 = inserta 5 (inserta 2 vacio)
   λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))
   λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))
   λ> subconjunto ej1 ej2
   True
   λ> subconjunto ej1 ej3
   False

λ> ej1 = inserta 5 (inserta 2 vacio)

λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))

λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))

λ> subconjunto ej1 ej2

True

λ> subconjunto ej1 ej3

False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)
import Transformaciones_conjuntos_listas (conjuntoAlista)
import Test.QuickCheck

-- 1ª solución
-- ===========

subconjunto :: Ord a => Conj a -> Conj a -> Bool
subconjunto c1 c2
  | esVacio c1 = True
  | otherwise  =  pertenece mc1 c2 && subconjunto rc1 c2
  where mc1 = menor c1
        rc1 = elimina mc1 c1

-- 2ª solución
-- ===========

subconjunto2 :: Ord a => Conj a -> Conj a -> Bool
subconjunto2 c1 c2 =
  and [pertenece x c2 | x <- conjuntoAlista c1]

-- La función conjuntoAlista está definida en el ejercicio
-- "Transformaciones entre conjuntos y listas" que se encuentra en
-- https://bit.ly/3RexzxH

-- 3ª solución
-- ===========

subconjunto3 :: Ord a => Conj a -> Conj a -> Bool
subconjunto3 c1 c2 =
  all (`pertenece` c2) (conjuntoAlista c1)

-- 4ª solución
-- ===========

subconjunto4 :: Ord a => Conj a -> Conj a -> Bool
subconjunto4 c1 c2 =
  sublista (conjuntoAlista c1) (conjuntoAlista c2)

-- (sublista xs ys) se verifica si xs es una sublista de ys. Por
-- ejemplo,
--    sublista [5, 2] [3, 2, 5]  ==  True
--    sublista [5, 2] [3, 4, 5]  ==  False
sublista :: Ord a => [a] -> [a] -> Bool
sublista [] _      = True
sublista (x:xs) ys = elem x ys && sublista xs ys

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_subconjunto :: Conj Int -> Conj Int -> Bool
prop_subconjunto c1 c2 =
  all (== subconjunto c1 c2)
      [subconjunto2 c1 c2,
       subconjunto3 c1 c2,
       subconjunto4 c1 c2]

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

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)

import Transformaciones_conjuntos_listas (conjuntoAlista)

import Test.QuickCheck

-- 1ª solución

-- ===========

subconjunto :: Ord a => Conj a -> Conj a -> Bool

subconjunto c1 c2

| esVacio c1 = True

| otherwise = pertenece mc1 c2 && subconjunto rc1 c2

where mc1 = menor c1

rc1 = elimina mc1 c1

-- 2ª solución

-- ===========

subconjunto2 :: Ord a => Conj a -> Conj a -> Bool

subconjunto2 c1 c2 =

and [pertenece x c2 | x <- conjuntoAlista c1]

-- La función conjuntoAlista está definida en el ejercicio

-- "Transformaciones entre conjuntos y listas" que se encuentra en

-- https://bit.ly/3RexzxH

-- 3ª solución

-- ===========

subconjunto3 :: Ord a => Conj a -> Conj a -> Bool

subconjunto3 c1 c2 =

all (`pertenece` c2) (conjuntoAlista c1)

-- 4ª solución

-- ===========

subconjunto4 :: Ord a => Conj a -> Conj a -> Bool

subconjunto4 c1 c2 =

sublista (conjuntoAlista c1) (conjuntoAlista c2)

-- (sublista xs ys) se verifica si xs es una sublista de ys. Por

-- ejemplo,

-- sublista [5, 2] [3, 2, 5] == True

-- sublista [5, 2] [3, 4, 5] == False

sublista :: Ord a => [a] -> [a] -> Bool

sublista [] _ = True

sublista (x:xs) ys = elem x ys && sublista xs ys

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_subconjunto :: Conj Int -> Conj Int -> Bool

prop_subconjunto c1 c2 =

all (== subconjunto c1 c2)

[subconjunto2 c1 c2,

subconjunto3 c1 c2,

subconjunto4 c1 c2]

-- La comprobación es

-- λ> quickCheck prop_subconjunto

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_Transformaciones_conjuntos_listas import conjuntoAlista

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª solución
# ===========

def subconjunto(c1: Conj[A], c2: Conj[A]) -> bool:
    if esVacio(c1):
        return True
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    return pertenece(mc1, c2) and subconjunto(rc1, c2)

# 2ª solución
# ===========

def subconjunto2(c1: Conj[A], c2: Conj[A]) -> bool:
    return all((pertenece(x, c2) for x in conjuntoAlista(c1)))

# La función conjuntoAlista está definida en el ejercicio
# "Transformaciones entre conjuntos y listas" que se encuentra en
# https://bit.ly/3RexzxH

# 3ª solución
# ===========

# (sublista xs ys) se verifica si xs es una sublista de ys. Por
# ejemplo,
#    sublista [5, 2] [3, 2, 5]  ==  True
#    sublista [5, 2] [3, 4, 5]  ==  False
def sublista(xs: list[A], ys: list[A]) -> bool:
    if not xs:
        return True
    return xs[0] in ys and sublista(xs[1:], ys)

def subconjunto3(c1: Conj[A], c2: Conj[A]) -> bool:
    return sublista(conjuntoAlista(c1), conjuntoAlista(c2))

# 4ª solución
# ===========

def subconjunto4(c1: Conj[A], c2: Conj[A]) -> bool:
    while not esVacio(c1):
        mc1 = menor(c1)
        if not pertenece(mc1, c2):
            return False
        c1 = elimina(mc1, c1)
    return True

# 5ª solución
# ===========

def subconjunto5Aux(c1: Conj[A], c2: Conj[A]) -> bool:
    while not c1.esVacio():
        mc1 = c1.menor()
        if not c2.pertenece(mc1):
            return False
        c1.elimina(mc1)
    return True

def subconjunto5(c1: Conj[A], c2: Conj[A]) -> bool:
    _c1 = deepcopy(c1)
    return subconjunto5Aux(_c1, c2)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_subconjunto(c1: Conj[int], c2: Conj[int]) -> None:
    r = subconjunto(c1, c2)
    assert subconjunto2(c1, c2) == r
    assert subconjunto3(c1, c2) == r
    assert subconjunto4(c1, c2) == r
    assert subconjunto5(c1, c2) == r

# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_subconjunto.py
#    1 passed in 0.37s

from __future__ import annotations

from abc import abstractmethod

from copy import deepcopy

from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, pertenece, vacio)

from src.TAD_Transformaciones_conjuntos_listas import conjuntoAlista

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª solución

# ===========

def subconjunto(c1: Conj[A], c2: Conj[A]) -> bool:

if esVacio(c1):

return True

mc1 = menor(c1)

rc1 = elimina(mc1, c1)

return pertenece(mc1, c2) and subconjunto(rc1, c2)

# 2ª solución

# ===========

def subconjunto2(c1: Conj[A], c2: Conj[A]) -> bool:

return all((pertenece(x, c2) for x in conjuntoAlista(c1)))

# La función conjuntoAlista está definida en el ejercicio

# "Transformaciones entre conjuntos y listas" que se encuentra en

# https://bit.ly/3RexzxH

# 3ª solución

# ===========

# (sublista xs ys) se verifica si xs es una sublista de ys. Por

# ejemplo,

# sublista [5, 2] [3, 2, 5] == True

# sublista [5, 2] [3, 4, 5] == False

def sublista(xs: list[A], ys: list[A]) -> bool:

if not xs:

return True

return xs[0] in ys and sublista(xs[1:], ys)

def subconjunto3(c1: Conj[A], c2: Conj[A]) -> bool:

return sublista(conjuntoAlista(c1), conjuntoAlista(c2))

# 4ª solución

# ===========

def subconjunto4(c1: Conj[A], c2: Conj[A]) -> bool:

while not esVacio(c1):

mc1 = menor(c1)

if not pertenece(mc1, c2):

return False

c1 = elimina(mc1, c1)

return True

# 5ª solución

# ===========

def subconjunto5Aux(c1: Conj[A], c2: Conj[A]) -> bool:

while not c1.esVacio():

mc1 = c1.menor()

if not c2.pertenece(mc1):

return False

c1.elimina(mc1)

return True

def subconjunto5(c1: Conj[A], c2: Conj[A]) -> bool:

_c1 = deepcopy(c1)

return subconjunto5Aux(_c1, c2)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())

def test_subconjunto(c1: Conj[int], c2: Conj[int]) -> None:

r = subconjunto(c1, c2)

assert subconjunto2(c1, c2) == r

assert subconjunto3(c1, c2) == r

assert subconjunto4(c1, c2) == r

assert subconjunto5(c1, c2) == r

# La comprobación de las propiedades es

# > poetry run pytest -q TAD_subconjunto.py

# 1 passed in 0.37s

5. TAD de los conjuntos: Reconocimiento de subconjuntos propios

Utilizando el tipo abstracto de datos de los conjuntos definir la función

   subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool

1	subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool

tal subconjuntoPropio c1 c2 se verifica si c1 es un subconjunto propio de c2. Por ejemplo,

   λ> ej1 = inserta 5 (inserta 2 vacio)
   λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))
   λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))
   λ> ej4 = inserta 2 (inserta 5 vacio)
   λ> subconjuntoPropio ej1 ej2
   True
   λ> subconjuntoPropio ej1 ej3
   False
   λ> subconjuntoPropio ej1 ej4
   False

λ> ej1 = inserta 5 (inserta 2 vacio)

λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))

λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))

λ> ej4 = inserta 2 (inserta 5 vacio)

λ> subconjuntoPropio ej1 ej2

True

λ> subconjuntoPropio ej1 ej3

False

λ> subconjuntoPropio ej1 ej4

False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta)
import TAD_subconjunto (subconjunto)

subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool
subconjuntoPropio c1 c2 =
  subconjunto c1 c2 && c1 /= c2

-- La función subconjunto está definida en el ejercicio
-- "Reconocimiento de subconjuntos" que se encuentra en
-- https://bit.ly/3wPBtU5

import TAD.Conjunto (Conj, vacio, inserta)

import TAD_subconjunto (subconjunto)

subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool

subconjuntoPropio c1 c2 =

subconjunto c1 c2 && c1 /= c2

-- La función subconjunto está definida en el ejercicio

-- "Reconocimiento de subconjuntos" que se encuentra en

-- https://bit.ly/3wPBtU5

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from typing import Protocol, TypeVar

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_subconjunto import subconjunto

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

def subconjuntoPropio(c1: Conj[A], c2: Conj[A]) -> bool:
    return subconjunto(c1, c2) and c1 != c2

# La función subconjunto está definida en el ejercicio
# "Reconocimiento de subconjuntos" que se encuentra en
# https://bit.ly/3wPBtU5

from __future__ import annotations

from abc import abstractmethod

from typing import Protocol, TypeVar

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, pertenece, vacio)

from src.TAD_subconjunto import subconjunto

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

def subconjuntoPropio(c1: Conj[A], c2: Conj[A]) -> bool:

return subconjunto(c1, c2) and c1 != c2

# La función subconjunto está definida en el ejercicio

# "Reconocimiento de subconjuntos" que se encuentra en

# https://bit.ly/3wPBtU5

1. TAD de las colas: Máximo elemento de una cola

2. El tipo abstracto de datos de los conjuntos

2.1. El tipo abstracto de datos de los conjuntos

2.2. Los conjuntos en Haskell

2.2.1. El tipo abstracto de datos de los conjuntos en Haskell

2.2.2. Implementación de los conjuntos mediante listas no ordenadas con duplicados

2.2.3. Implementación de los conjuntos mediante listas no ordenadas sin duplicados

2.2.4. Implementación de los conjuntos mediante listas ordenadas sin repeticiones

2.2.5. Implementación de los conjuntos mediante librería

2.3. Los conjuntos en Python

2.3.1. El tipo abstracto de los conjuntos en Python

2.3.2. Implementación de los conjuntos mediante listas no ordenadas con duplicados

2.3.3. Implementación de los conjuntos mediante listas no ordenadas sin duplicados

2.3.4. Implementación de los conjuntos mediante listas ordenadas sin duplicados

2.3.5. Implementación de los conjuntos mediante librería

3. TAD de los conjuntos: Transformaciones entre conjuntos y listas

4. TAD de los conjuntos: Reconocimiento de subconjuntos

5. TAD de los conjuntos: Reconocimiento de subconjuntos propios

Se puede imprimir o compartir con