TAD de las colas: Todos los elementos verifican una propiedad
Utilizando el tipo abstracto de datos de las colas, definir la función
|
1 |
todosVerifican :: (a -> Bool) -> Cola a -> Bool |
tal que todosVerifican p c se verifica si todos los elementos de la cola c cumplen la propiedad p. Por ejemplo,
|
1 2 |
todosVerifican (>0) (inserta 3 (inserta 2 vacia)) == True todosVerifican (>0) (inserta 3 (inserta (-2) vacia)) == 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 37 |
import TAD.Cola (Cola, vacia, inserta, primero, resto, esVacia) import Transformaciones_colas_listas (colaAlista, listaAcola) import Test.QuickCheck.HigherOrder -- 1ª solución -- =========== todosVerifican1 :: (a -> Bool) -> Cola a -> Bool todosVerifican1 p c | esVacia c = True | otherwise = p pc && todosVerifican1 p rc where pc = primero c rc = resto c -- 2ª solución -- =========== todosVerifican2 :: (a -> Bool) -> Cola a -> Bool todosVerifican2 p c = all p (colaAlista c) -- La función colaAlista está definida en el ejercicio -- "Transformaciones entre colas y listas" que se encuentra en -- https://bit.ly/3Xv0oIt -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_todosVerifican :: (Int -> Bool) -> [Int] -> Bool prop_todosVerifican p xs = todosVerifican1 p c == todosVerifican2 p c where c = listaAcola xs -- La comprobación es -- λ> quickCheck' prop_todosVerifican -- +++ 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 85 86 87 88 |
from copy import deepcopy from typing import Callable, TypeVar from hypothesis import given from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero, resto, vacia) from src.transformaciones_colas_listas import colaAlista A = TypeVar('A') # 1ª solución # =========== def todosVerifican1(p: Callable[[A], bool], c: Cola[A]) -> bool: if esVacia(c): return True pc = primero(c) rc = resto(c) return p(pc) and todosVerifican1(p, rc) # 2ª solución # =========== def todosVerifican2(p: Callable[[A], bool], c: Cola[A]) -> bool: return all(p(x) for x in colaAlista(c)) # La función colaAlista está definida en el ejercicio # "Transformaciones entre colas y listas" que se encuentra en # https://bit.ly/3Xv0oIt # 3ª solución # =========== def todosVerifican3Aux(p: Callable[[A], bool], c: Cola[A]) -> bool: if c.esVacia(): return True pc = c.primero() c.resto() return p(pc) and todosVerifican3Aux(p, c) def todosVerifican3(p: Callable[[A], bool], c: Cola[A]) -> bool: _c = deepcopy(c) return todosVerifican3Aux(p, _c) # 4ª solución # =========== def todosVerifican4Aux(p: Callable[[A], bool], c: Cola[A]) -> bool: if c.esVacia(): return True pc = c.primero() c.resto() return p(pc) and todosVerifican4Aux(p, c) def todosVerifican4(p: Callable[[A], bool], c: Cola[A]) -> bool: _c = deepcopy(c) return todosVerifican4Aux(p, _c) # 5ª solución # =========== def todosVerifican5Aux(p: Callable[[A], bool], c: Cola[A]) -> bool: while not c.esVacia(): if not p(c.primero()): return False c.resto() return True def todosVerifican5(p: Callable[[A], bool], c: Cola[A]) -> bool: _c = deepcopy(c) return todosVerifican5Aux(p, _c) # Comprobación de equivalencia # ============================ # La propiedad es @given(c=colaAleatoria()) def test_filtraPila(c: Cola[int]) -> None: r = todosVerifican1(lambda x: x > 0, c) assert todosVerifican2(lambda x: x > 0, c) == r assert todosVerifican3(lambda x: x > 0, c) == r assert todosVerifican4(lambda x: x > 0, c) == r assert todosVerifican5(lambda x: x > 0, c) == r # La comprobación es # src> poetry run pytest -q todosVerifican.py # 1 passed in 0.25s |