TAD de los conjuntos: Algunos elementos verifican una propiedad
Utilizando el tipo abstracto de datos de los conjuntos definir la función
|
1 |
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,
|
1 2 |
algunos even (inserta 4 (inserta 7 vacio)) == True algunos even (inserta 3 (inserta 7 vacio)) == False |
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 |
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) -- La función conjuntoAlista 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_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. |
|
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 81 82 83 |
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)) # 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 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 |