TAD de las pilas: Transformaciones entre pilas y listas
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
|
1 2 |
listaApila :: [a] -> Pila a pilaAlista :: Pila a -> [a] |
tales que
listaApila xses la pila formada por los elementos dexs. Por ejemplo,
|
1 2 |
λ> listaApila [3, 2, 5] 5 | 2 | 3 |
pilaAlista pes la lista formada por los elementos de la pilap. Por ejemplo,
|
1 2 |
λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia))) [3, 2, 5] |
Comprobar con QuickCheck que ambas funciones son inversa; es decir,
|
1 2 |
pilaAlista (listaApila xs) == xs listaApila (pilaAlista p) == p |
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
module Transformaciones_pilas_listas where import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila) import Test.QuickCheck -- 1ª definición de listaApila -- =========================== listaApila :: [a] -> Pila a listaApila ys = aux (reverse ys) where aux [] = vacia aux (x:xs) = apila x (aux xs) -- 2ª definición de listaApila -- =========================== listaApila2 :: [a] -> Pila a listaApila2 = aux . reverse where aux [] = vacia aux (x:xs) = apila x (aux xs) -- 3ª definición de listaApila -- =========================== listaApila3 :: [a] -> Pila a listaApila3 = aux . reverse where aux = foldr apila vacia -- 4ª definición de listaApila -- =========================== listaApila4 :: [a] -> Pila a listaApila4 xs = foldr apila vacia (reverse xs) -- 5ª definición de listaApila -- =========================== listaApila5 :: [a] -> Pila a listaApila5 = foldr apila vacia . reverse -- Comprobación de equivalencia de las definiciones de listaApila -- ============================================================== -- La propiedad es prop_listaApila :: [Int] -> Bool prop_listaApila xs = all (== listaApila xs) [listaApila2 xs, listaApila3 xs, listaApila4 xs, listaApila5 xs] -- La comprobación es -- λ> quickCheck prop_listaApila -- +++ OK, passed 100 tests. -- 1ª definición de pilaAlista -- =========================== pilaAlista :: Pila a -> [a] pilaAlista p | esVacia p = [] | otherwise = pilaAlista dp ++ [cp] where cp = cima p dp = desapila p -- 2ª definición de pilaAlista -- =========================== pilaAlista2 :: Pila a -> [a] pilaAlista2 = reverse . aux where aux p | esVacia p = [] | otherwise = cp : aux dp where cp = cima p dp = desapila p -- Comprobación de equivalencia de las definiciones de pilaAlista -- ============================================================== -- La propiedad es prop_pilaAlista :: Pila Int -> Bool prop_pilaAlista p = pilaAlista p == pilaAlista2 p -- La comprobación es -- λ> quickCheck prop_pilaAlista -- +++ OK, passed 100 tests. -- Comprobación de las propiedades -- =============================== -- La primera propiedad es prop_1_listaApila :: [Int] -> Bool prop_1_listaApila xs = pilaAlista (listaApila xs) == xs -- La comprobación es -- λ> quickCheck prop_1_listaApila -- +++ OK, passed 100 tests. -- La segunda propiedad es prop_2_listaApila :: Pila Int -> Bool prop_2_listaApila p = listaApila (pilaAlista p) == p -- La comprobación es -- λ> quickCheck prop_2_listaApila -- +++ 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.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria, vacia) A = TypeVar('A') # 1ª definición de listaApila # =========================== def listaApila(ys: list[A]) -> Pila[A]: def aux(xs: list[A]) -> Pila[A]: if not xs: return vacia() return apila(xs[0], aux(xs[1:])) return aux(list(reversed(ys))) # 2ª solución de listaApila # ========================= def listaApila2(xs: list[A]) -> Pila[A]: p: Pila[A] = Pila() for x in xs: p.apila(x) return p # Comprobación de equivalencia de las definiciones de listaApila # ============================================================== # La propiedad es @given(st.lists(st.integers())) def test_listaApila(xs: list[int]) -> None: assert listaApila(xs) == listaApila2(xs) # 1ª definición de pilaAlista # =========================== def pilaAlista(p: Pila[A]) -> list[A]: if esVacia(p): return [] cp = cima(p) dp = desapila(p) return pilaAlista(dp) + [cp] # 2ª definición de pilaAlista # =========================== def pilaAlista2Aux(p: Pila[A]) -> list[A]: if p.esVacia(): return [] cp = p.cima() p.desapila() return pilaAlista2Aux(p) + [cp] def pilaAlista2(p: Pila[A]) -> list[A]: p1 = deepcopy(p) return pilaAlista2Aux(p1) # 3ª definición de pilaAlista # =========================== def pilaAlista3Aux(p: Pila[A]) -> list[A]: r = [] while not p.esVacia(): r.append(p.cima()) p.desapila() return r[::-1] def pilaAlista3(p: Pila[A]) -> list[A]: p1 = deepcopy(p) return pilaAlista3Aux(p1) # Comprobación de equivalencia de las definiciones de pilaAlista # ============================================================== @given(p=pilaAleatoria()) def test_pilaAlista(p: Pila[int]) -> None: assert pilaAlista(p) == pilaAlista2(p) assert pilaAlista(p) == pilaAlista3(p) # Comprobación de las propiedades # =============================== # La primera propiedad es @given(st.lists(st.integers())) def test_1_listaApila(xs: list[int]) -> None: assert pilaAlista(listaApila(xs)) == xs # La segunda propiedad es @given(p=pilaAleatoria()) def test_2_listaApila(p: Pila[int]) -> None: assert listaApila(pilaAlista(p)) == p # La comprobación es # src> poetry run pytest -v transformaciones_pilas_listas.py # test_listaApila PASSED # test_pilaAlista PASSED # test_1_listaApila PASSED # test_2_listaApila PASSED |
Aquí hay una implementación para las dos funciones que ha definido:
listaApila está implementada usando la función foldr, que aplica la función apila a cada elemento de la lista de entrada y la pila actual, comenzando con la pila vacía. Esto efectivamente agrega cada elemento de la lista a la pila, en orden inverso.
pilaAlista está implementado mediante recursión. Verifica si la pila está vacía, y si es así, devuelve una lista vacía. Si la pila no está vacía, toma el elemento superior de la pila con cima y lo conecta con el resultado de llamar a pilaAlista en la pila restante obtenida por desapila la pila original. Esto efectivamente saca cada elemento de la pila y lo agrega a la lista en el orden correcto.