TAD de las colas: Extensión de colas
Utilizando el tipo abstracto de datos de las colas, definir la función
|
1 |
extiendeCola :: Cola a -> Cola a -> Cola a |
tal que extiendeCola c1 c2 es la cola que resulta de poner los elementos de la cola c2 a continuación de los de la cola de c1. Por
ejemplo,
|
1 2 3 4 5 6 7 8 9 10 |
λ> ej1 = inserta 3 (inserta 2 vacia) λ> ej2 = inserta 5 (inserta 3 (inserta 4 vacia)) λ> ej1 2 | 3 λ> ej2 4 | 3 | 5 λ> extiendeCola ej1 ej2 2 | 3 | 4 | 3 | 5 λ> extiendeCola ej2 ej1 4 | 3 | 5 | 2 | 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 35 36 |
import TAD.Cola (Cola, vacia, inserta, primero, resto, esVacia) import Transformaciones_colas_listas (colaAlista, listaAcola) import Test.QuickCheck -- 1ª solución -- =========== extiendeCola :: Cola a -> Cola a -> Cola a extiendeCola c1 c2 | esVacia c2 = c1 | otherwise = extiendeCola (inserta pc2 c1) rq2 where pc2 = primero c2 rq2 = resto c2 -- 2ª solución -- =========== extiendeCola2 :: Cola a -> Cola a -> Cola a extiendeCola2 c1 c2 = listaAcola (colaAlista c1 ++ colaAlista c2) -- Las funciones colaAlista y listaAcola están definidas en el ejercicio -- "Transformaciones entre colas y listas" que se encuentra en -- https://bit.ly/3Xv0oIt -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_extiendeCola :: Cola Int -> Cola Int -> Bool prop_extiendeCola p c = extiendeCola p c == extiendeCola2 p c -- La comprobación es -- λ> quickCheck prop_extiendeCola -- +++ 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 TypeVar from hypothesis import given from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero, resto, vacia) from src.transformaciones_colas_listas import colaAlista, listaAcola A = TypeVar('A') # 1ª solución # =========== def extiendeCola(c1: Cola[A], c2: Cola[A]) -> Cola[A]: if esVacia(c2): return c1 pc2 = primero(c2) rc2 = resto(c2) return extiendeCola(inserta(pc2, c1), rc2) # 2ª solución # =========== def extiendeCola2(c1: Cola[A], c2: Cola[A]) -> Cola[A]: return listaAcola(colaAlista(c1) + colaAlista(c2)) # Las funciones colaAlista y listaAcola están definidas en el ejercicio # "Transformaciones entre colas y listas" que se encuentra en # https://bit.ly/3Xv0oIt # 3ª solución # =========== def extiendeCola3Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]: if c2.esVacia(): return c1 pc2 = c2.primero() c2.resto() return extiendeCola(inserta(pc2, c1), c2) def extiendeCola3(c1: Cola[A], c2: Cola[A]) -> Cola[A]: _c2 = deepcopy(c2) return extiendeCola3Aux(c1, _c2) # 4ª solución # =========== def extiendeCola4Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]: r = c1 while not esVacia(c2): r = inserta(primero(c2), r) c2 = resto(c2) return r def extiendeCola4(c1: Cola[A], c2: Cola[A]) -> Cola[A]: _c2 = deepcopy(c2) return extiendeCola4Aux(c1, _c2) # 5ª solución # =========== def extiendeCola5Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]: r = c1 while not c2.esVacia(): r.inserta(primero(c2)) c2.resto() return r def extiendeCola5(c1: Cola[A], c2: Cola[A]) -> Cola[A]: _c1 = deepcopy(c1) _c2 = deepcopy(c2) return extiendeCola5Aux(_c1, _c2) # Comprobación de equivalencia # ============================ # La propiedad es @given(c1=colaAleatoria(), c2=colaAleatoria()) def test_extiendeCola(c1: Cola[int], c2: Cola[int]) -> None: r = extiendeCola(c1, c2) assert extiendeCola2(c1, c2) == r assert extiendeCola3(c1, c2) == r assert extiendeCola4(c1, c2) == r # La comprobación es # src> poetry run pytest -q extiendeCola.py # 1 passed in 0.32s |