TAD de las pilas: Filtrado de pilas según una propiedad
Utilizando el tipo abstracto de datos de las pilas, definir la función
|
1 |
filtraPila :: (a -> Bool) -> Pila a -> Pila a |
tal que filtraPila p q es la pila obtenida con los elementos de pila q que verifican el predicado p, en el mismo orden. Por ejemplo,
|
1 2 3 4 5 6 7 |
λ> ejPila = apila 6 (apila 3 (apila 1 (apila 4 vacia))) λ> ejPila 6 | 3 | 1 | 4 λ> filtraPila even ejPila 6 | 4 λ> filtraPila odd ejPila 3 | 1 |
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 |
import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila) import Transformaciones_pilas_listas (listaApila, pilaAlista) import Test.QuickCheck.HigherOrder -- 1ª solución -- =========== filtraPila1 :: (a -> Bool) -> Pila a -> Pila a filtraPila1 p q | esVacia q = vacia | p cq = apila cq (filtraPila1 p dq) | otherwise = filtraPila1 p dq where cq = cima q dq = desapila q -- 2ª solución -- =========== -- Se usarán las funciones listaApila y pilaAlista del ejercicio -- "Transformaciones entre pilas y listas" que se encuentra en -- https://bit.ly/3ZHewQ8 filtraPila2 :: (a -> Bool) -> Pila a -> Pila a filtraPila2 p q = listaApila (filter p (pilaAlista q)) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_filtraPila :: (Int -> Bool) -> [Int] -> Bool prop_filtraPila p xs = filtraPila1 p q == filtraPila2 p q where q = listaApila xs -- La comprobación es -- λ> quickCheck' prop_filtraPila -- +++ 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 |
from copy import deepcopy from typing import Callable, TypeVar from hypothesis import given from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria, vacia) from src.transformaciones_pilas_listas import listaApila, pilaAlista A = TypeVar('A') # 1ª solución # =========== def filtraPila1(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]: if esVacia(q): return q cq = cima(q) dq = desapila(q) r = filtraPila1(p, dq) if p(cq): return apila(cq, r) return r # 2ª solución # =========== # Se usarán las funciones listaApila y pilaAlista del ejercicio # "Transformaciones entre pilas y listas" que se encuentra en # https://bit.ly/3ZHewQ8 def filtraPila2(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]: return listaApila(list(filter(p, pilaAlista(q)))) # 3ª solución # =========== def filtraPila3Aux(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]: if q.esVacia(): return q cq = q.cima() q.desapila() r = filtraPila3Aux(p, q) if p(cq): r.apila(cq) return r def filtraPila3(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]: q1 = deepcopy(q) return filtraPila3Aux(p, q1) # 4ª solución # =========== def filtraPila4Aux(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]: r: Pila[A] = Pila() while not q.esVacia(): cq = q.cima() q.desapila() if p(cq): r.apila(cq) r1: Pila[A] = Pila() while not r.esVacia(): r1.apila(r.cima()) r.desapila() return r1 def filtraPila4(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]: q1 = deepcopy(q) return filtraPila4Aux(p, q1) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(p=pilaAleatoria()) def test_filtraPila(p: Pila[int]) -> None: r = filtraPila1(lambda x: x % 2 == 0, p) assert filtraPila2(lambda x: x % 2 == 0, p) == r assert filtraPila3(lambda x: x % 2 == 0, p) == r assert filtraPila4(lambda x: x % 2 == 0, p) == r # La comprobación es # src> poetry run pytest -q filtraPila.py # 1 passed in 0.25s |