TAD de las colas: Pertenencia a una cola
Utilizando el tipo abstracto de datos de las colas, definir la función
|
1 |
perteneceCola :: Eq a => a -> Cola a -> Bool |
tal que perteneceCola x c se verifica si x es un elemento de la cola c. Por ejemplo,
|
1 2 |
perteneceCola 2 (inserta 5 (inserta 2 (inserta 3 vacia))) == True perteneceCola 4 (inserta 5 (inserta 2 (inserta 3 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 |
import TAD.Cola (Cola, vacia, inserta, primero, resto, esVacia) import Transformaciones_colas_listas colaAlista import Test.QuickCheck -- 1ª solución -- =========== perteneceCola :: Eq a => a -> Cola a -> Bool perteneceCola x c | esVacia c = False | otherwise = x == primero(c) || perteneceCola x (resto c) -- 2ª solución -- =========== perteneceCola2 :: Eq a => a -> Cola a -> Bool perteneceCola2 x c = x `elem` 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_perteneceCola :: Int -> Cola Int -> Bool prop_perteneceCola x p = perteneceCola x p == perteneceCola2 x p -- La comprobación es -- λ> quickCheck prop_perteneceCola -- +++ 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 |
from copy import deepcopy from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.TAD.cola import (Cola, vacia, inserta, primero, resto, esVacia, colaAleatoria) from src.transformaciones_colas_listas import colaAlista A = TypeVar('A') # 1ª solución # =========== def perteneceCola(x: A, c: Cola[A]) -> bool: if esVacia(c): return False return x == primero(c) or perteneceCola(x, resto(c)) # 2ª solución # =========== def perteneceCola2(x: A, c: Cola[A]) -> bool: return x in colaAlista(c) # Las 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 perteneceCola3Aux(x: A, c: Cola[A]) -> bool: if c.esVacia(): return False pc = c.primero() c.resto() return x == pc or perteneceCola3Aux(x, c) def perteneceCola3(x: A, c: Cola[A]) -> bool: c1 = deepcopy(c) return perteneceCola3Aux(x, c1) # 4ª solución # =========== def perteneceCola4Aux(x: A, c: Cola[A]) -> bool: while not c.esVacia(): pc = c.primero() c.resto() if x == pc: return True return False def perteneceCola4(x: A, c: Cola[A]) -> bool: c1 = deepcopy(c) return perteneceCola4Aux(x, c1) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(x=st.integers(), c=colaAleatoria()) def test_perteneceCola(x: int, c: Cola[int]) -> None: r = perteneceCola(x, c) assert perteneceCola2(x, c) == r assert perteneceCola3(x, c) == r assert perteneceCola4(x, c) == r # La comprobación es # src> poetry run pytest -q perteneceCola.py # 1 passed in 0.25s |