TAD de los conjuntos: Subconjunto determinado por una propiedad
Utilizando el tipo abstracto de datos de los conjuntos definir la función
|
1 |
filtra :: Ord a => (a -> Bool) -> Conj a -> Conj a |
tal filtra p c es el conjunto de elementos de c que verifican el predicado p. Por ejemplo,
|
1 2 3 4 |
λ> filtra even (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio)))) {2, 4} λ> filtra odd (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio)))) {5, 7} |
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 |
import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina) import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto) import Test.QuickCheck.HigherOrder -- 1ª solución -- =========== filtra :: Ord a => (a -> Bool) -> Conj a -> Conj a filtra p c | esVacio c = vacio | p mc = inserta mc (filtra p rc) | otherwise = filtra p rc where mc = menor c rc = elimina mc c -- 2ª solución -- =========== filtra2 :: Ord a => (a -> Bool) -> Conj a -> Conj a filtra2 p c = listaAconjunto (filter p (conjuntoAlista c)) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_filtra :: (Int -> Bool) -> [Int] -> Bool prop_filtra p xs = filtra p c == filtra2 p c where c = listaAconjunto xs -- La comprobación es -- λ> quickCheck' prop_filtra -- +++ 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 84 |
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, pertenece, vacio) from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista, listaAconjunto) class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) # 1ª solución # =========== def filtra(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]: if esVacio(c): return vacio() mc = menor(c) rc = elimina(mc, c) if p(mc): return inserta(mc, filtra(p, rc)) return filtra(p, rc) # 2ª solución # =========== def filtra2(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]: return listaAconjunto(list(filter(p, conjuntoAlista(c)))) # 3ª solución # =========== def filtra3Aux(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]: r: Conj[A] = vacio() while not esVacio(c): mc = menor(c) c = elimina(mc, c) if p(mc): r = inserta(mc, r) return r def filtra3(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]: _c = deepcopy(c) return filtra3Aux(p, _c) # 4ª solución # =========== def filtra4Aux(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]: r: Conj[A] = Conj() while not c.esVacio(): mc = c.menor() c.elimina(mc) if p(mc): r.inserta(mc) return r def filtra4(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]: _c = deepcopy(c) return filtra4Aux(p, _c) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(c=conjuntoAleatorio()) def test_filtra(c: Conj[int]) -> None: r = filtra(lambda x: x % 2 == 0, c) assert filtra2(lambda x: x % 2 == 0, c) == r assert filtra3(lambda x: x % 2 == 0, c) == r assert filtra4(lambda x: x % 2 == 0, c) == r # La comprobación es # src> poetry run pytest -q TAD_Subconjunto_por_propiedad.py # 1 passed in 0.28s |