febrero 2023 – Exercitium

El tipo abstracto de datos de los conjuntos

PorJosé A. Alonso 28-febrero-202322-febrero-2023

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. Los conjuntos en Haskell

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

3. Los conjuntos en Python

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.

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

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

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

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

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

PorJosé A. Alonso 27-febrero-202327-enero-2023

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

TAD de las colas: Reconocimiento de ordenación de colas

PorJosé A. Alonso 24-febrero-202327-enero-2023

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

   ordenadaCola :: Ord a => Cola a -> Bool

1	ordenadaCola :: Ord a => Cola a -> Bool

tal que ordenadaCola c se verifica si los elementos de la cola c están ordenados en orden creciente. Por ejemplo,

   ordenadaCola (inserta 6 (inserta 5 (inserta 1 vacia))) == True
   ordenadaCola (inserta 1 (inserta 0 (inserta 6 vacia))) == False

1 2	ordenadaCola (inserta 6 (inserta 5 (inserta 1 vacia))) == True ordenadaCola (inserta 1 (inserta 0 (inserta 6 vacia))) == False

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

ordenadaCola :: Ord a => Cola a -> Bool
ordenadaCola c
  | esVacia c  = True
  | esVacia rc = True
  | otherwise  = pc <= prc && ordenadaCola rc
  where pc  = primero c
        rc  = resto c
        prc = primero rc

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

ordenadaCola2 :: Ord a => Cola a -> Bool
ordenadaCola2 =
  ordenadaLista . colaAlista

-- (ordenadaLista xs) se verifica si la lista xs está ordenada de menor
-- a mayor. Por ejemplo,
ordenadaLista :: Ord a => [a] -> Bool
ordenadaLista xs =
  and [x <= y | (x,y) <- zip xs (tail xs)]

-- 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_ordenadaCola :: Cola Int -> Bool
prop_ordenadaCola c =
  ordenadaCola c == ordenadaCola2 c

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

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

import Transformaciones_colas_listas (colaAlista)

import Test.QuickCheck

-- 1ª solución

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

ordenadaCola :: Ord a => Cola a -> Bool

ordenadaCola c

| esVacia c = True

| esVacia rc = True

| otherwise = pc <= prc && ordenadaCola rc

where pc = primero c

rc = resto c

prc = primero rc

-- 2ª solución

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

ordenadaCola2 :: Ord a => Cola a -> Bool

ordenadaCola2 =

ordenadaLista . colaAlista

-- (ordenadaLista xs) se verifica si la lista xs está ordenada de menor

-- a mayor. Por ejemplo,

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

ordenadaLista xs =

and [x <= y | (x,y) <- zip xs (tail xs)]

-- 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_ordenadaCola :: Cola Int -> Bool

prop_ordenadaCola c =

ordenadaCola c == ordenadaCola2 c

-- La comprobación es

-- λ> quickCheck prop_ordenadaCola

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import 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 ordenadaCola(c: Cola[A]) -> bool:
    if esVacia(c):
        return True
    pc = primero(c)
    rc = resto(c)
    if esVacia(rc):
        return True
    prc = primero(rc)
    return pc <= prc and ordenadaCola(rc)

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

# ordenadaLista(xs, ys) se verifica si xs es una lista ordenada. Por
# ejemplo,
#    >>> ordenadaLista([2, 5, 8])
#    True
#    >>> ordenadalista([2, 8, 5])
#    False
def ordenadaLista(xs: list[A]) -> bool:
    return all((x <= y for (x, y) in zip(xs, xs[1:])))

def ordenadaCola2(p: Cola[A]) -> bool:
    return ordenadaLista(colaAlista(p))

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

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

def ordenadaCola3Aux(c: Cola[A]) -> bool:
    if c.esVacia():
        return True
    pc = c.primero()
    c.resto()
    if c.esVacia():
        return True
    return pc <= c.primero() and ordenadaCola3Aux(c)

def ordenadaCola3(c: Cola[A]) -> bool:
    _c = deepcopy(c)
    return ordenadaCola3Aux(_c)

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

def ordenadaCola4Aux(c: Cola[A]) -> bool:
    while not c.esVacia():
        pc = c.primero()
        c.resto()
        if not c.esVacia() and pc > c.primero():
            return False
    return True

def ordenadaCola4(c: Cola[A]) -> bool:
    _c = deepcopy(c)
    return ordenadaCola4Aux(_c)

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

# La propiedad es
@given(p=colaAleatoria())
def test_ordenadaCola(p: Cola[int]) -> None:
    r = ordenadaCola(p)
    assert ordenadaCola2(p) == r
    assert ordenadaCola3(p) == r
    assert ordenadaCola4(p) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import 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 ordenadaCola(c: Cola[A]) -> bool:

if esVacia(c):

return True

pc = primero(c)

rc = resto(c)

if esVacia(rc):

return True

prc = primero(rc)

return pc <= prc and ordenadaCola(rc)

# 2ª solución

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

# ordenadaLista(xs, ys) se verifica si xs es una lista ordenada. Por

# ejemplo,

# >>> ordenadaLista([2, 5, 8])

# True

# >>> ordenadalista([2, 8, 5])

# False

def ordenadaLista(xs: list[A]) -> bool:

return all((x <= y for (x, y) in zip(xs, xs[1:])))

def ordenadaCola2(p: Cola[A]) -> bool:

return ordenadaLista(colaAlista(p))

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

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

# https://bit.ly/3Xv0oIt

# 3ª solución

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

def ordenadaCola3Aux(c: Cola[A]) -> bool:

if c.esVacia():

return True

pc = c.primero()

c.resto()

if c.esVacia():

return True

return pc <= c.primero() and ordenadaCola3Aux(c)

def ordenadaCola3(c: Cola[A]) -> bool:

_c = deepcopy(c)

return ordenadaCola3Aux(_c)

# 4ª solución

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

def ordenadaCola4Aux(c: Cola[A]) -> bool:

while not c.esVacia():

pc = c.primero()

c.resto()

if not c.esVacia() and pc > c.primero():

return False

return True

def ordenadaCola4(c: Cola[A]) -> bool:

_c = deepcopy(c)

return ordenadaCola4Aux(_c)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(p=colaAleatoria())

def test_ordenadaCola(p: Cola[int]) -> None:

r = ordenadaCola(p)

assert ordenadaCola2(p) == r

assert ordenadaCola3(p) == r

assert ordenadaCola4(p) == r

# La comprobación es

# src> poetry run pytest -q ordenadaCola.py

# 1 passed in 0.27s

TAD de las colas: Reconocimiento de subcolas

PorJosé A. Alonso 23-febrero-202327-enero-2023

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

   subCola :: Eq a => Cola a -> Cola a -> Bool

1	subCola :: Eq a => Cola a -> Cola a -> Bool

tal que subCola c1 c2 se verifica si c1 es una subcola de c2. Por ejemplo,

   λ> ej1 = inserta 2 (inserta 3 vacia)
   λ> ej2 = inserta 7 (inserta 2 (inserta 3 (inserta 5 vacia)))
   λ> ej3 = inserta 2 (inserta 7 (inserta 3 (inserta 5 vacia)))
   λ> subCola ej1 ej2
   True
   λ> subCola ej1 ej3
   False

λ> ej1 = inserta 2 (inserta 3 vacia)

λ> ej2 = inserta 7 (inserta 2 (inserta 3 (inserta 5 vacia)))

λ> ej3 = inserta 2 (inserta 7 (inserta 3 (inserta 5 vacia)))

λ> subCola ej1 ej2

True

λ> subCola ej1 ej3

False

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 PrefijoCola (prefijoCola)
import Data.List (isPrefixOf, tails)
import Test.QuickCheck

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

subCola1 :: Eq a => Cola a -> Cola a -> Bool
subCola1 c1 c2
    | esVacia c1 = True
    | esVacia c2 = False
    | pc1 == pc2 = prefijoCola rc1 rc2 || subCola1 c1 rc2
    | otherwise  = subCola1 c1 rc2
    where pc1 = primero c1
          rc1 = resto c1
          pc2 = primero c2
          rc2 = resto c2

-- La función PrefijoCola está definida en el ejercicio
-- "Reconocimiento de prefijos de colas" que se encuentra en
-- https://bit.ly/3HaK20x

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

subCola2 :: Eq a => Cola a -> Cola a -> Bool
subCola2 c1 c2 =
  sublista (colaAlista c1) (colaAlista c2)

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

-- (sublista xs ys) se verifica si xs es una sublista de ys. Por
-- ejemplo,
--    sublista [3,2] [5,3,2,7]  ==  True
--    sublista [3,2] [5,3,7,2]  ==  False
sublista :: Eq a => [a] -> [a] -> Bool
sublista xs ys =
  any (xs `isPrefixOf`) (tails ys)

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

-- La propiedad es
prop_subCola :: Cola Int -> Cola Int -> Bool
prop_subCola c1 c2 =
  subCola1 c1 c2 == subCola2 c1 c2

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

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

import Transformaciones_colas_listas (colaAlista)

import PrefijoCola (prefijoCola)

import Data.List (isPrefixOf, tails)

import Test.QuickCheck

-- 1ª solución

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

subCola1 :: Eq a => Cola a -> Cola a -> Bool

subCola1 c1 c2

| esVacia c1 = True

| esVacia c2 = False

| pc1 == pc2 = prefijoCola rc1 rc2 || subCola1 c1 rc2

| otherwise = subCola1 c1 rc2

where pc1 = primero c1

rc1 = resto c1

pc2 = primero c2

rc2 = resto c2

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

-- "Reconocimiento de prefijos de colas" que se encuentra en

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

-- 2ª solución

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

subCola2 :: Eq a => Cola a -> Cola a -> Bool

subCola2 c1 c2 =

sublista (colaAlista c1) (colaAlista c2)

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

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

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

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

-- ejemplo,

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

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

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

sublista xs ys =

any (xs `isPrefixOf`) (tails ys)

-- Comprobación de equivalencia

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

-- La propiedad es

prop_subCola :: Cola Int -> Cola Int -> Bool

prop_subCola c1 c2 =

subCola1 c1 c2 == subCola2 c1 c2

-- La comprobación es

-- λ> quickCheck prop_subCola

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

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

A = TypeVar('A')

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

def subCola1(c1: Cola[A], c2: Cola[A]) -> bool:
    if esVacia(c1):
        return True
    if esVacia(c2):
        return False
    pc1 = primero(c1)
    rc1 = resto(c1)
    pc2 = primero(c2)
    rc2 = resto(c2)
    if pc1 == pc2:
        return prefijoCola(rc1, rc2) or subCola1(c1, rc2)
    return subCola1(c1, rc2)

# La función prefijoCola está definida en el ejercicio
# "Reconocimiento de prefijos de colas" que se encuentra en
# https://bit.ly/3HaK20x

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

# sublista(xs, ys) se verifica si xs es una sublista de ys. Por
# ejemplo,
#    >>> sublista([3,2], [5,3,2,7])
#    True
#    >>> sublista([3,2], [5,3,7,2])
#    False
def sublista(xs: list[A], ys: list[A]) -> bool:
    return any(xs == ys[i:i+len(xs)] for i in range(len(ys) - len(xs) + 1))

def subCola2(c1: Cola[A], c2: Cola[A]) -> bool:
    return sublista(colaAlista(c1), colaAlista(c2))

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

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

def subCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    if c1.esVacia():
        return True
    if c2.esVacia():
        return False
    if c1.primero() != c2.primero():
        c2.resto()
        return subCola3Aux(c1, c2)
    q1 = deepcopy(c1)
    c1.resto()
    c2.resto()
    return prefijoCola(c1, c2) or subCola3Aux(q1, c2)

def subCola3(c1: Cola[A], c2: Cola[A]) -> bool:
    q1 = deepcopy(c1)
    q2 = deepcopy(c2)
    return subCola3Aux(q1, q2)

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

# La propiedad es
@given(c1=colaAleatoria(), c2=colaAleatoria())
def test_subCola(c1: Cola[int], c2: Cola[int]) -> None:
    r = subCola1(c1, c2)
    assert subCola2(c1, c2) == r
    assert subCola3(c1, c2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.prefijoCola import prefijoCola

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

resto, vacia)

from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

# 1ª solución

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

def subCola1(c1: Cola[A], c2: Cola[A]) -> bool:

if esVacia(c1):

return True

if esVacia(c2):

return False

pc1 = primero(c1)

rc1 = resto(c1)

pc2 = primero(c2)

rc2 = resto(c2)

if pc1 == pc2:

return prefijoCola(rc1, rc2) or subCola1(c1, rc2)

return subCola1(c1, rc2)

# La función prefijoCola está definida en el ejercicio

# "Reconocimiento de prefijos de colas" que se encuentra en

# https://bit.ly/3HaK20x

# 2ª solución

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

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

# ejemplo,

# >>> sublista([3,2], [5,3,2,7])

# True

# >>> sublista([3,2], [5,3,7,2])

# False

def sublista(xs: list[A], ys: list[A]) -> bool:

return any(xs == ys[i:i+len(xs)] for i in range(len(ys) - len(xs) + 1))

def subCola2(c1: Cola[A], c2: Cola[A]) -> bool:

return sublista(colaAlista(c1), colaAlista(c2))

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

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

# https://bit.ly/3Xv0oIt

# 3ª solución

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

def subCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:

if c1.esVacia():

return True

if c2.esVacia():

return False

if c1.primero() != c2.primero():

c2.resto()

return subCola3Aux(c1, c2)

q1 = deepcopy(c1)

c1.resto()

c2.resto()

return prefijoCola(c1, c2) or subCola3Aux(q1, c2)

def subCola3(c1: Cola[A], c2: Cola[A]) -> bool:

q1 = deepcopy(c1)

q2 = deepcopy(c2)

return subCola3Aux(q1, q2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(c1=colaAleatoria(), c2=colaAleatoria())

def test_subCola(c1: Cola[int], c2: Cola[int]) -> None:

r = subCola1(c1, c2)

assert subCola2(c1, c2) == r

assert subCola3(c1, c2) == r

# La comprobación es

# src> poetry run pytest -q subCola.py

# 1 passed in 0.31s

TAD de las colas: Reconocimiento de prefijos de colas

PorJosé A. Alonso 22-febrero-202327-enero-2023

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

   prefijoCola :: Eq a => Cola a -> Cola a -> Bool

1	prefijoCola :: Eq a => Cola a -> Cola a -> Bool

tal que prefijoCola c1 c2 se verifica si la cola c1 es justamente un prefijo de la cola c2. Por ejemplo,

   λ> ej1 = inserta 4 (inserta 2 vacia)
   λ> ej2 = inserta 5 (inserta 4 (inserta 2 vacia))
   λ> ej3 = inserta 5 (inserta 2 (inserta 4 vacia))
   λ> prefijoCola ej1 ej2
   True
   λ> prefijoCola ej1 ej3
   False

λ> ej1 = inserta 4 (inserta 2 vacia)

λ> ej2 = inserta 5 (inserta 4 (inserta 2 vacia))

λ> ej3 = inserta 5 (inserta 2 (inserta 4 vacia))

λ> prefijoCola ej1 ej2

True

λ> prefijoCola ej1 ej3

False

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 Data.List (isPrefixOf)
import Test.QuickCheck

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

prefijoCola :: Eq a => Cola a -> Cola a -> Bool
prefijoCola c1 c2
  | esVacia c1 = True
  | esVacia c2 = False
  | otherwise  = primero c1 == primero c2 &&
                 prefijoCola (resto c1) (resto c2)

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

prefijoCola2 :: Eq a => Cola a -> Cola a -> Bool
prefijoCola2 c1 c2 =
  colaAlista c1 `isPrefixOf` colaAlista c2

-- 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_prefijoCola :: Cola Int -> Cola Int -> Bool
prop_prefijoCola c1 c2 =
  prefijoCola c1 c2 == prefijoCola2 c1 c2

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

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

import Transformaciones_colas_listas (colaAlista)

import Data.List (isPrefixOf)

import Test.QuickCheck

-- 1ª solución

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

prefijoCola :: Eq a => Cola a -> Cola a -> Bool

prefijoCola c1 c2

| esVacia c1 = True

| esVacia c2 = False

| otherwise = primero c1 == primero c2 &&

prefijoCola (resto c1) (resto c2)

-- 2ª solución

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

prefijoCola2 :: Eq a => Cola a -> Cola a -> Bool

prefijoCola2 c1 c2 =

colaAlista c1 `isPrefixOf` colaAlista c2

-- 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_prefijoCola :: Cola Int -> Cola Int -> Bool

prop_prefijoCola c1 c2 =

prefijoCola c1 c2 == prefijoCola2 c1 c2

-- La comprobación es

-- λ> quickCheck prop_prefijoCola

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

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

A = TypeVar('A')

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

def prefijoCola(c1: Cola[A], c2: Cola[A]) -> bool:
    if esVacia(c1):
        return True
    if esVacia(c2):
        return False
    return primero(c1) == primero(c2) and prefijoCola(resto(c1), resto(c2))

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

def esPrefijoLista(xs: list[A], ys: list[A]) -> bool:
    return ys[:len(xs)] == xs

def prefijoCola2(c1: Cola[A], c2: Cola[A]) -> bool:
    return esPrefijoLista(colaAlista(c1), colaAlista(c2))

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

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

def prefijoCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    if c1.esVacia():
        return True
    if c2.esVacia():
        return False
    cc1 = c1.primero()
    c1.resto()
    cc2 = c2.primero()
    c2.resto()
    return cc1 == cc2 and prefijoCola3(c1, c2)

def prefijoCola3(c1: Cola[A], c2: Cola[A]) -> bool:
    q1 = deepcopy(c1)
    q2 = deepcopy(c2)
    return prefijoCola3Aux(q1, q2)

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

def prefijoCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    while not c2.esVacia() and not c1.esVacia():
        if c1.primero() != c2.primero():
            return False
        c1.resto()
        c2.resto()
    return c1.esVacia()

def prefijoCola4(c1: Cola[A], c2: Cola[A]) -> bool:
    q1 = deepcopy(c1)
    q2 = deepcopy(c2)
    return prefijoCola4Aux(q1, q2)

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

# La propiedad es
@given(c1=colaAleatoria(), c2=colaAleatoria())
def test_prefijoCola(c1: Cola[int], c2: Cola[int]) -> None:
    r = prefijoCola(c1, c2)
    assert prefijoCola2(c1, c2) == r
    assert prefijoCola3(c1, c2) == r
    assert prefijoCola4(c1, c2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

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

resto, vacia)

from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

# 1ª solución

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

def prefijoCola(c1: Cola[A], c2: Cola[A]) -> bool:

if esVacia(c1):

return True

if esVacia(c2):

return False

return primero(c1) == primero(c2) and prefijoCola(resto(c1), resto(c2))

# 2ª solución

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

def esPrefijoLista(xs: list[A], ys: list[A]) -> bool:

return ys[:len(xs)] == xs

def prefijoCola2(c1: Cola[A], c2: Cola[A]) -> bool:

return esPrefijoLista(colaAlista(c1), colaAlista(c2))

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

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

# https://bit.ly/3Xv0oIt

# 3ª solución

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

def prefijoCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:

if c1.esVacia():

return True

if c2.esVacia():

return False

cc1 = c1.primero()

c1.resto()

cc2 = c2.primero()

c2.resto()

return cc1 == cc2 and prefijoCola3(c1, c2)

def prefijoCola3(c1: Cola[A], c2: Cola[A]) -> bool:

q1 = deepcopy(c1)

q2 = deepcopy(c2)

return prefijoCola3Aux(q1, q2)

# 4ª solución

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

def prefijoCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool:

while not c2.esVacia() and not c1.esVacia():

if c1.primero() != c2.primero():

return False

c1.resto()

c2.resto()

return c1.esVacia()

def prefijoCola4(c1: Cola[A], c2: Cola[A]) -> bool:

q1 = deepcopy(c1)

q2 = deepcopy(c2)

return prefijoCola4Aux(q1, q2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(c1=colaAleatoria(), c2=colaAleatoria())

def test_prefijoCola(c1: Cola[int], c2: Cola[int]) -> None:

r = prefijoCola(c1, c2)

assert prefijoCola2(c1, c2) == r

assert prefijoCola3(c1, c2) == r

assert prefijoCola4(c1, c2) == r

# La comprobación es

# src> poetry run pytest -q prefijoCola.py

# 1 passed in 0.29s

TAD de las colas: Inclusión de colas

PorJosé A. Alonso 21-febrero-202327-enero-2023

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

   contenidaCola :: Eq a => Cola a -> Cola a -> Bool

1	contenidaCola :: Eq a => Cola a -> Cola a -> Bool

tal que contenidaCola c1 c2 se verifica si todos los elementos de la cola c1 son elementos de la cola c2. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 2 vacia)
   λ> ej2 = inserta 3 (inserta 4 vacia)
   λ> ej3 = inserta 5 (inserta 2 (inserta 3 vacia))
   λ> contenidaCola ej1 ej3
   True
   λ> contenidaCola ej2 ej3
   False

λ> ej1 = inserta 3 (inserta 2 vacia)

λ> ej2 = inserta 3 (inserta 4 vacia)

λ> ej3 = inserta 5 (inserta 2 (inserta 3 vacia))

λ> contenidaCola ej1 ej3

True

λ> contenidaCola ej2 ej3

False

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 PerteneceCola (perteneceCola)
import Transformaciones_colas_listas (colaAlista)
import Test.QuickCheck

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

contenidaCola1 :: Eq a => Cola a -> Cola a -> Bool
contenidaCola1 c1 c2
  | esVacia c1 = True
  | otherwise  = perteneceCola (primero c1) c2 &&
                 contenidaCola1 (resto c1) c2

-- La función perteneceCola está definida en el ejercicio
-- "TAD de las colas: Pertenencia a una cola" que se encuentra en
-- https://bit.ly/3RcVgqb

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

contenidaCola2 :: Eq a => Cola a -> Cola a -> Bool
contenidaCola2 c1 c2 =
  contenidaLista (colaAlista c1) (colaAlista c2)

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

contenidaLista :: Eq a => [a] -> [a] -> Bool
contenidaLista xs ys =
  all (`elem` ys) xs

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

-- La propiedad es
prop_contenidaCola :: Cola Int -> Cola Int -> Bool
prop_contenidaCola c1 c2 =
  contenidaCola1 c1 c2 == contenidaCola2 c1 c2

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

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

import PerteneceCola (perteneceCola)

import Transformaciones_colas_listas (colaAlista)

import Test.QuickCheck

-- 1ª solución

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

contenidaCola1 :: Eq a => Cola a -> Cola a -> Bool

contenidaCola1 c1 c2

| esVacia c1 = True

| otherwise = perteneceCola (primero c1) c2 &&

contenidaCola1 (resto c1) c2

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

-- "TAD de las colas: Pertenencia a una cola" que se encuentra en

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

-- 2ª solución

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

contenidaCola2 :: Eq a => Cola a -> Cola a -> Bool

contenidaCola2 c1 c2 =

contenidaLista (colaAlista c1) (colaAlista c2)

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

-- "TAD de las colas: Transformaciones entre colas y listas" que se

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

contenidaLista :: Eq a => [a] -> [a] -> Bool

contenidaLista xs ys =

all (`elem` ys) xs

-- Comprobación de equivalencia

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

-- La propiedad es

prop_contenidaCola :: Cola Int -> Cola Int -> Bool

prop_contenidaCola c1 c2 =

contenidaCola1 c1 c2 == contenidaCola2 c1 c2

-- La comprobación es

-- λ> quickCheck prop_contenidaCola

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

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

A = TypeVar('A')

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

def contenidaCola1(c1: Cola[A], c2: Cola[A]) -> bool:
    if esVacia(c1):
        return True
    return perteneceCola(primero(c1), c2) and contenidaCola1(resto(c1), c2)

# L función perteneceCola está definida en el ejercicio
# "Pertenencia a una cola" que se encuentra en
# https://bit.ly/3RcVgqb

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

def contenidaCola2(c1: Cola[A], c2: Cola[A]) -> bool:
    return set(colaAlista(c1)) <= set(colaAlista(c2))

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

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

def contenidaCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    if c1.esVacia():
        return True
    pc1 = c1.primero()
    c1.resto()
    return perteneceCola(pc1, c2) and contenidaCola1(c1, c2)

def contenidaCola3(c1: Cola[A], c2: Cola[A]) -> bool:
    _c1 = deepcopy(c1)
    return contenidaCola3Aux(_c1, c2)

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

def contenidaCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    while not c1.esVacia():
        pc1 = c1.primero()
        c1.resto()
        if not perteneceCola(pc1, c2):
            return False
    return True

def contenidaCola4(c1: Cola[A], c2: Cola[A]) -> bool:
    _c1 = deepcopy(c1)
    return contenidaCola4Aux(_c1, c2)

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

# La propiedad es
@given(c1=colaAleatoria(), c2=colaAleatoria())
def test_contenidaCola(c1: Cola[int], c2: Cola[int]) -> None:
    r = contenidaCola1(c1, c2)
    assert contenidaCola2(c1, c2) == r
    assert contenidaCola3(c1, c2) == r
    assert contenidaCola4(c1, c2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.perteneceCola import perteneceCola

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

resto, vacia)

from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

# 1ª solución

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

def contenidaCola1(c1: Cola[A], c2: Cola[A]) -> bool:

if esVacia(c1):

return True

return perteneceCola(primero(c1), c2) and contenidaCola1(resto(c1), c2)

# L función perteneceCola está definida en el ejercicio

# "Pertenencia a una cola" que se encuentra en

# https://bit.ly/3RcVgqb

# 2ª solución

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

def contenidaCola2(c1: Cola[A], c2: Cola[A]) -> bool:

return set(colaAlista(c1)) <= set(colaAlista(c2))

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

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

# https://bit.ly/3Xv0oIt

# 3ª solución

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

def contenidaCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:

if c1.esVacia():

return True

pc1 = c1.primero()

c1.resto()

return perteneceCola(pc1, c2) and contenidaCola1(c1, c2)

def contenidaCola3(c1: Cola[A], c2: Cola[A]) -> bool:

_c1 = deepcopy(c1)

return contenidaCola3Aux(_c1, c2)

# 4ª solución

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

def contenidaCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool:

while not c1.esVacia():

pc1 = c1.primero()

c1.resto()

if not perteneceCola(pc1, c2):

return False

return True