Utilizando el tipo abstracto de datos de los conjuntos definir la función
union :: Ord a => Conj a -> Conj a -> Conj a |
union :: Ord a => Conj a -> Conj a -> Conj a
tal union c1 c2
es la unión de ambos conjuntos. Por ejemplo,
λ> ej1 = inserta 3 (inserta 5 vacio)
λ> ej2 = inserta 4 (inserta 3 vacio)
λ> union ej1 ej2
{3, 4, 5} |
λ> ej1 = inserta 3 (inserta 5 vacio)
λ> ej2 = inserta 4 (inserta 3 vacio)
λ> union ej1 ej2
{3, 4, 5}
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
Soluciones en Haskell
import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, esVacio)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import qualified Data.List as L (union)
import Test.QuickCheck
-- 1ª solución
-- ===========
union :: Ord a => Conj a -> Conj a -> Conj a
union c1 c2
| esVacio c1 = c2
| otherwise = inserta mc1 (rc1 `union` c2)
where mc1 = menor c1
rc1 = elimina mc1 c1
-- 2ª solución
-- ===========
union2 :: Ord a => Conj a -> Conj a -> Conj a
union2 c1 c2 =
foldr inserta c2 (conjuntoAlista c1)
-- La función conjuntoAlista está definida en el ejercicio
-- "Transformaciones entre conjuntos y listas" que se encuentra en
-- https://bit.ly/3RexzxH
-- 3ª solución
-- ===========
union3 :: Ord a => Conj a -> Conj a -> Conj a
union3 c1 c2 =
listaAconjunto (conjuntoAlista c1 `L.union` conjuntoAlista c2)
-- La función listaAconjunto está definida en el ejercicio
-- "Transformaciones entre conjuntos y listas" que se encuentra en
-- https://bit.ly/3RexzxH
-- Comprobación de equivalencia
-- ============================
-- La propiedad es
prop_union :: Conj Int -> Conj Int -> Bool
prop_union c1 c2 =
all (== union c1 c2)
[union2 c1 c2,
union3 c1 c2]
-- La comprobación es
-- λ> quickCheck prop_union
-- +++ OK, passed 100 tests. |
import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, esVacio)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import qualified Data.List as L (union)
import Test.QuickCheck
-- 1ª solución
-- ===========
union :: Ord a => Conj a -> Conj a -> Conj a
union c1 c2
| esVacio c1 = c2
| otherwise = inserta mc1 (rc1 `union` c2)
where mc1 = menor c1
rc1 = elimina mc1 c1
-- 2ª solución
-- ===========
union2 :: Ord a => Conj a -> Conj a -> Conj a
union2 c1 c2 =
foldr inserta c2 (conjuntoAlista c1)
-- La función conjuntoAlista está definida en el ejercicio
-- "Transformaciones entre conjuntos y listas" que se encuentra en
-- https://bit.ly/3RexzxH
-- 3ª solución
-- ===========
union3 :: Ord a => Conj a -> Conj a -> Conj a
union3 c1 c2 =
listaAconjunto (conjuntoAlista c1 `L.union` conjuntoAlista c2)
-- La función listaAconjunto está definida en el ejercicio
-- "Transformaciones entre conjuntos y listas" que se encuentra en
-- https://bit.ly/3RexzxH
-- Comprobación de equivalencia
-- ============================
-- La propiedad es
prop_union :: Conj Int -> Conj Int -> Bool
prop_union c1 c2 =
all (== union c1 c2)
[union2 c1 c2,
union3 c1 c2]
-- La comprobación es
-- λ> quickCheck prop_union
-- +++ OK, passed 100 tests.
Soluciones en Python
from __future__ import annotations
from abc import abstractmethod
from copy import deepcopy
from functools import reduce
from typing import Protocol, TypeVar
from hypothesis import given
from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
inserta, menor, vacio)
from src.TAD_Transformaciones_conjuntos_listas import conjuntoAlista
class Comparable(Protocol):
@abstractmethod
def __lt__(self: A, otro: A) -> bool:
pass
A = TypeVar('A', bound=Comparable)
# 1ª solución
# ===========
def union(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
if esVacio(c1):
return c2
mc1 = menor(c1)
rc1 = elimina(mc1, c1)
return inserta(mc1, union(rc1, c2))
# 2ª solución
# ===========
def union2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
return reduce(lambda c, x: inserta(x, c), conjuntoAlista(c1), c2)
# La función conjuntoAlista está definida en el ejercicio
# "Transformaciones entre conjuntos y listas" que se encuentra en
# https://bit.ly/3RexzxH
# 3ª solución
# ===========
def union3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
r = c2
while not esVacio(c1):
mc1 = menor(c1)
r = inserta(mc1, r)
c1 = elimina(mc1, c1)
return r
# 4ª solución
# ===========
def union4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
while not c1.esVacio():
mc1 = menor(c1)
c2.inserta(mc1)
c1.elimina(mc1)
return c2
def union4(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
_c1 = deepcopy(c1)
_c2 = deepcopy(c2)
return union4Aux(_c1, _c2)
# Comprobación de equivalencia
# ============================
# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_union(c1: Conj[int], c2: Conj[int]) -> None:
r = union(c1, c2)
assert union2(c1, c2) == r
assert union3(c1, c2) == r
assert union4(c1, c2) == r
# La comprobación de las propiedades es
# > poetry run pytest -q TAD_Union_de_dos_conjuntos.py
# 1 passed in 0.35s |
from __future__ import annotations
from abc import abstractmethod
from copy import deepcopy
from functools import reduce
from typing import Protocol, TypeVar
from hypothesis import given
from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
inserta, menor, vacio)
from src.TAD_Transformaciones_conjuntos_listas import conjuntoAlista
class Comparable(Protocol):
@abstractmethod
def __lt__(self: A, otro: A) -> bool:
pass
A = TypeVar('A', bound=Comparable)
# 1ª solución
# ===========
def union(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
if esVacio(c1):
return c2
mc1 = menor(c1)
rc1 = elimina(mc1, c1)
return inserta(mc1, union(rc1, c2))
# 2ª solución
# ===========
def union2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
return reduce(lambda c, x: inserta(x, c), conjuntoAlista(c1), c2)
# La función conjuntoAlista está definida en el ejercicio
# "Transformaciones entre conjuntos y listas" que se encuentra en
# https://bit.ly/3RexzxH
# 3ª solución
# ===========
def union3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
r = c2
while not esVacio(c1):
mc1 = menor(c1)
r = inserta(mc1, r)
c1 = elimina(mc1, c1)
return r
# 4ª solución
# ===========
def union4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
while not c1.esVacio():
mc1 = menor(c1)
c2.inserta(mc1)
c1.elimina(mc1)
return c2
def union4(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
_c1 = deepcopy(c1)
_c2 = deepcopy(c2)
return union4Aux(_c1, _c2)
# Comprobación de equivalencia
# ============================
# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_union(c1: Conj[int], c2: Conj[int]) -> None:
r = union(c1, c2)
assert union2(c1, c2) == r
assert union3(c1, c2) == r
assert union4(c1, c2) == r
# La comprobación de las propiedades es
# > poetry run pytest -q TAD_Union_de_dos_conjuntos.py
# 1 passed in 0.35s