TAD de los conjuntos: Unión de dos conjuntos
Utilizando el tipo abstracto de datos de los conjuntos definir la función
|
1 |
union :: Ord a => Conj a -> Conj a -> Conj a |
tal union c1 c2 es la unión de ambos conjuntos. Por ejemplo,
|
1 2 3 4 |
λ> 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
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. |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
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 |