TAD de los conjunto - Unión de varios conjuntos

José A. Alonso

09-03-2023

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

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

tal unionG cs calcule la unión de la lista de conjuntos cs. Por ejemplo,

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

Se usará la función union definida en el ejercicio Unión de dos conjuntos.

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta)
import TAD_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

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

Soluciones en Python

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:]))

# 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