TAD de los conjuntos: Todos los elementos verifican una propiedad
Utilizando el tipo abstracto de datos de los conjuntos definir la función
|
1 |
todos :: Ord a => (a -> Bool) -> Conj a -> Bool |
tal que todos p c se verifica si todos los elemsntos de c verifican el predicado p. Por ejemplo,
|
1 2 |
todos even (inserta 4 (inserta 6 vacio)) == True todos even (inserta 4 (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 -- =========== todos :: Ord a => (a -> Bool) -> Conj a -> Bool todos p c | esVacio c = True | otherwise = p mc && todos p rc where mc = menor c rc = elimina mc c -- 2ª solución -- =========== todos2 :: Ord a => (a -> Bool) -> Conj a -> Bool todos2 p c = all 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_todos :: (Int -> Bool) -> [Int] -> Bool prop_todos p xs = todos p c == todos2 p c where c = listaAconjunto xs -- La comprobación es -- λ> quickCheck' prop_todos -- +++ 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 todos(p: Callable[[A], bool], c: Conj[A]) -> bool: if esVacio(c): return True mc = menor(c) rc = elimina(mc, c) return p(mc) and todos(p, rc) # 2ª solución # =========== def todos2(p: Callable[[A], bool], c: Conj[A]) -> bool: return all(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 todos3Aux(p: Callable[[A], bool], c: Conj[A]) -> bool: while not esVacio(c): mc = menor(c) c = elimina(mc, c) if not p(mc): return False return True def todos3(p: Callable[[A], bool], c: Conj[A]) -> bool: _c = deepcopy(c) return todos3Aux(p, _c) # 4ª solución # =========== def todos4Aux(p: Callable[[A], bool], c: Conj[A]) -> bool: while not c.esVacio(): mc = c.menor() c.elimina(mc) if not p(mc): return False return True def todos4(p: Callable[[A], bool], c: Conj[A]) -> bool: _c = deepcopy(c) return todos4Aux(p, _c) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(c=conjuntoAleatorio()) def test_todos(c: Conj[int]) -> None: r = todos(lambda x: x % 2 == 0, c) assert todos2(lambda x: x % 2 == 0, c) == r assert todos3(lambda x: x % 2 == 0, c) == r assert todos4(lambda x: x % 2 == 0, c) == r # La comprobación es # src> poetry run pytest -q TAD_TodosVerificanConj.py # 1 passed in 0.28s |