TAD de los conjuntos: Unión de varios conjuntos
Utilizando el tipo abstracto de datos de los conjuntos definir la función
|
1 |
unionG:: Ord a => [Conj a] -> Conj a |
tal unionG cs calcule la unión de la lista de conjuntos cs. Por ejemplo,
|
1 2 3 4 5 |
λ> ej1 = inserta 3 (inserta 5 vacio) λ> ej2 = inserta 5 (inserta 6 vacio) λ> ej3 = inserta 3 (inserta 6 vacio) λ> unionG [ej1, ej2, ej3] {3, 5, 6} |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
Haskell
|
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 |
import TAD.Conjunto (Conj, vacio, inserta) import TAD_Union_de_dos_conjuntos (union) import Test.QuickCheck -- 1ª solución -- =========== unionG :: Ord a => [Conj a] -> Conj a unionG [] = vacio unionG (c:cs) = c `union` unionG cs -- La función union está definida en el ejercicio -- "Unión de dos conjuntos" que se encuentra en -- https://bit.ly/3Y1jBl8 -- 2ª solución -- =========== unionG2 :: Ord a => [Conj a] -> Conj a unionG2 = foldr union vacio -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_unionG :: [Conj Int] -> Bool prop_unionG cs = unionG cs == unionG2 cs -- La comprobación es -- λ> quickCheck prop_unionG -- +++ OK, passed 100 tests. |
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 51 52 53 54 55 56 57 58 59 |
from __future__ import annotations from abc import abstractmethod from functools import reduce from typing import Protocol, TypeVar from hypothesis import given from hypothesis import strategies as st from src.TAD.conjunto import Conj, conjuntoAleatorio, inserta, vacio from src.TAD_Union_de_dos_conjuntos import union class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) # 1ª solución # =========== def unionG(cs: list[Conj[A]]) -> Conj[A]: if not cs: return vacio() return union(cs[0], unionG(cs[1:])) # La función union está definida en el ejercicio # "Unión de dos conjuntos" que se encuentra en # https://bit.ly/3Y1jBl8 # 2ª solución # =========== def unionG2(cs: list[Conj[A]]) -> Conj[A]: return reduce(union, cs, vacio()) # 3ª solución # =========== def unionG3(cs: list[Conj[A]]) -> Conj[A]: r: Conj[A] = vacio() for c in cs: r = union(c, r) return r # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(conjuntoAleatorio(), max_size=10)) def test_union(cs: list[Conj[int]]) -> None: r = unionG(cs) assert unionG2(cs) == r assert unionG3(cs) == r # La comprobación de las propiedades es # > poetry run pytest -q TAD_Union_de_varios_conjuntos.py # 1 passed in 0.75s |