TAD de los conjuntos - Algunos elementos verifican una propiedad

José A. Alonso

24-03-2023

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

   algunos :: Ord a => (a -> Bool) -> Conj a -> Bool

tal que algunos p c se verifica si algún elemento de c verifica el predicado p. Por ejemplo,

   algunos even (inserta 4 (inserta 7 vacio))  ==  True
   algunos even (inserta 3 (inserta 7 vacio))  ==  False

Soluciones

Se usarán las funciones conjuntoAlista y listaAconjunto definidas en el ejercicio Transformaciones entre conjuntos y listas.

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import Test.QuickCheck.HigherOrder

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

algunos :: Ord a => (a -> Bool) -> Conj a -> Bool
algunos p c
  | esVacio c = False
  | otherwise = p mc || algunos p rc
  where mc = menor c
        rc = elimina mc c

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

algunos2 :: Ord a => (a -> Bool) -> Conj a -> Bool
algunos2 p c = any p (conjuntoAlista c)

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

-- La propiedad es
prop_algunos :: (Int -> Bool) -> [Int] -> Bool
prop_algunos p xs =
  algunos p c == algunos2 p c
  where c = listaAconjunto xs

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

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from typing import Callable, 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 algunos(p: Callable[[A], bool], c: Conj[A]) -> bool:
    if esVacio(c):
        return False
    mc = menor(c)
    rc = elimina(mc, c)
    return p(mc) or algunos(p, rc)

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

def algunos2(p: Callable[[A], bool], c: Conj[A]) -> bool:
    return any(p(x) for x in conjuntoAlista(c))

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

def algunos3Aux(p: Callable[[A], bool], c: Conj[A]) -> bool:
    while not esVacio(c):
        mc = menor(c)
        c = elimina(mc, c)
        if p(mc):
            return True
    return False

def algunos3(p: Callable[[A], bool], c: Conj[A]) -> bool:
    _c = deepcopy(c)
    return algunos3Aux(p, _c)

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

def algunos4Aux(p: Callable[[A], bool], c: Conj[A]) -> bool:
    while not c.esVacio():
        mc = c.menor()
        c.elimina(mc)
        if p(mc):
            return True
    return False

def algunos4(p: Callable[[A], bool], c: Conj[A]) -> bool:
    _c = deepcopy(c)
    return algunos4Aux(p, _c)

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

# La propiedad es
@given(c=conjuntoAleatorio())
def test_algunos(c: Conj[int]) -> None:
    r = algunos(lambda x: x % 2 == 0, c)
    assert algunos2(lambda x: x % 2 == 0, c) == r
    assert algunos3(lambda x: x % 2 == 0, c) == r
    assert algunos4(lambda x: x % 2 == 0, c) == r

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