TAD de las colas: Longitud de una cola
Utilizando el tipo abstracto de datos de las colas, definir la función
1 |
longitudCola :: Cola a -> Int |
tal que longitudCola c
es el número de elementos de la cola c
. Por ejemplo,
1 |
longitudCola (inserta 4 (inserta 2 (inserta 5 vacia))) == 3 |
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, resto, esVacia) import Transformaciones_colas_listas (colaAlista) import Test.QuickCheck -- 1ª solución -- =========== longitudCola1 :: Cola a -> Int longitudCola1 c | esVacia c = 0 | otherwise = 1 + longitudCola1 rc where rc = resto c -- 2ª solución -- =========== longitudCola2 :: Cola a -> Int longitudCola2 = length . colaAlista -- 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_longitudCola :: Cola Int -> Bool prop_longitudCola c = longitudCola1 c == longitudCola2 c -- La comprobación es -- λ> quickCheck prop_longitudCola -- +++ 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 |
from copy import deepcopy from typing import TypeVar from hypothesis import given from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, resto, vacia) from src.transformaciones_colas_listas import colaAlista A = TypeVar('A') # 1ª solución # =========== def longitudCola1(c: Cola[A]) -> int: if esVacia(c): return 0 return 1 + longitudCola1(resto(c)) # 2ª solución # =========== def longitudCola2(c: Cola[A]) -> int: return len(colaAlista(c)) # 3ª solución # =========== def longitudCola3Aux(c: Cola[A]) -> int: if c.esVacia(): return 0 c.resto() return 1 + longitudCola3Aux(c) def longitudCola3(c: Cola[A]) -> int: _c = deepcopy(c) return longitudCola3Aux(_c) # 4ª solución # =========== def longitudCola4Aux(c: Cola[A]) -> int: r = 0 while not esVacia(c): r = r + 1 c = resto(c) return r def longitudCola4(c: Cola[A]) -> int: _c = deepcopy(c) return longitudCola4Aux(_c) # 5ª solución # =========== def longitudCola5Aux(c: Cola[A]) -> int: r = 0 while not c.esVacia(): r = r + 1 c.resto() return r def longitudCola5(c: Cola[A]) -> int: _c = deepcopy(c) return longitudCola5Aux(_c) # Comprobación de equivalencia # ============================ # La propiedad es @given(c=colaAleatoria()) def test_longitudCola_(c: Cola[int]) -> None: r = longitudCola1(c) assert longitudCola2(c) == r assert longitudCola3(c) == r assert longitudCola4(c) == r assert longitudCola5(c) == r # La comprobación es # src> poetry run pytest -q longitudCola.py # 1 passed in 0.28s |