TAD de las colas: Transformaciones entre colas y listas
Utilizando el tipo abstracto de datos de las colas, definir las funciones
|
1 2 |
listaAcola :: [a] -> Cola a colaAlista :: Cola a -> [a] |
tales que
listaAcola xses la cola formada por los elementos dexs. Por ejemplo,
|
1 2 |
λ> listaAcola [3, 2, 5] 3 | 2 | 5 |
colaAlista ces la lista formada por los elementos de la colac. Por ejemplo,
|
1 2 |
λ> colaAlista (inserta 5 (inserta 2 (inserta 3 vacia))) [3, 2, 5] |
Comprobar con QuickCheck que ambas funciones son inversa; es decir,
|
1 2 |
colaAlista (listaAcola xs) = xs listaAcola (colaAlista c) = c |
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 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 |
import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto) import Test.QuickCheck -- 1ª definición de listaAcola -- =========================== listaAcola :: [a] -> Cola a listaAcola ys = aux (reverse ys) where aux [] = vacia aux (x:xs) = inserta x (aux xs) -- 2ª definición de listaAcola -- =========================== listaAcola2 :: [a] -> Cola a listaAcola2 = aux . reverse where aux [] = vacia aux (x:xs) = inserta x (aux xs) -- 3ª definición de listaAcola -- =========================== listaAcola3 :: [a] -> Cola a listaAcola3 = aux . reverse where aux = foldr inserta vacia -- 4ª definición de listaAcola -- =========================== listaAcola4 :: [a] -> Cola a listaAcola4 xs = foldr inserta vacia (reverse xs) -- 5ª definición de listaAcola -- =========================== listaAcola5 :: [a] -> Cola a listaAcola5 = foldr inserta vacia . reverse -- Comprobación de equivalencia de las definiciones de listaAcola -- ============================================================== -- La propiedad es prop_listaAcola :: [Int] -> Bool prop_listaAcola xs = all (== listaAcola xs) [listaAcola2 xs, listaAcola3 xs, listaAcola4 xs, listaAcola5 xs] -- La comprobación es -- λ> quickCheck prop_listaAcola -- +++ OK, passed 100 tests. -- Definición de colaAlista -- ======================== colaAlista :: Cola a -> [a] colaAlista c | esVacia c = [] | otherwise = pc : colaAlista rc where pc = primero c rc = resto c -- Comprobación de las propiedades -- =============================== -- La primera propiedad es prop_1_listaAcola :: [Int] -> Bool prop_1_listaAcola xs = colaAlista (listaAcola xs) == xs -- La comprobación es -- λ> quickCheck prop_1_listaAcola -- +++ OK, passed 100 tests. -- La segunda propiedad es prop_2_listaAcola :: Cola Int -> Bool prop_2_listaAcola c = listaAcola (colaAlista c) == c -- La comprobación es -- λ> quickCheck prop_2_listaAcola -- +++ 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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
from copy import deepcopy from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.TAD.cola import (Cola, inserta, primero, resto, esVacia, vacia, colaAleatoria) A = TypeVar('A') # 1ª definición de listaAcola # =========================== def listaAcola(ys: list[A]) -> Cola[A]: def aux(xs: list[A]) -> Cola[A]: if not xs: return vacia() return inserta(xs[0], aux(xs[1:])) return aux(list(reversed(ys))) # 2ª solución de listaAcola # ========================= def listaAcola2(xs: list[A]) -> Cola[A]: p: Cola[A] = Cola() for x in xs: p.inserta(x) return p # Comprobación de equivalencia de las definiciones de listaAcola # ============================================================== # La propiedad es @given(st.lists(st.integers())) def test_listaAcola(xs: list[int]) -> None: assert listaAcola(xs) == listaAcola2(xs) # 1ª definición de colaAlista # =========================== def colaAlista(c: Cola[A]) -> list[A]: if esVacia(c): return [] pc = primero(c) rc = resto(c) return [pc] + colaAlista(rc) # 2ª definición de colaAlista # =========================== def colaAlista2Aux(c: Cola[A]) -> list[A]: if c.esVacia(): return [] pc = c.primero() c.resto() return [pc] + colaAlista2Aux(c) def colaAlista2(c: Cola[A]) -> list[A]: c1 = deepcopy(c) return colaAlista2Aux(c1) # 3ª definición de colaAlista # =========================== def colaAlista3Aux(c: Cola[A]) -> list[A]: r = [] while not c.esVacia(): r.append(c.primero()) c.resto() return r def colaAlista3(c: Cola[A]) -> list[A]: c1 = deepcopy(c) return colaAlista3Aux(c1) # Comprobación de equivalencia de las definiciones de colaAlista # ============================================================== @given(p=colaAleatoria()) def test_colaAlista(p: Cola[int]) -> None: assert colaAlista(p) == colaAlista2(p) assert colaAlista(p) == colaAlista3(p) # Comprobación de las propiedades # =============================== # La primera propiedad es @given(st.lists(st.integers())) def test_1_listaAcola(xs: list[int]) -> None: assert colaAlista(listaAcola(xs)) == xs # La segunda propiedad es @given(c=colaAleatoria()) def test_2_listaAcola(c: Cola[int]) -> None: assert listaAcola(colaAlista(c)) == c # La comprobación es # src> poetry run pytest -v transformaciones_colas_listas.py # test_listaAcola PASSED # test_colaAlista PASSED # test_1_listaAcola PASSED # test_2_listaAcola PASSED |
La función listaAcola puede ser definida de la siguiente manera:
Y la función colaAlista puede ser definida de la siguiente manera: