TAD de las pilas: Aplicación de una función a los elementos de una pila
Utilizando el tipo abstracto de datos de las pilas, definir la función
|
1 |
mapPila :: (a -> a) -> Pila a -> Pila a |
tal que mapPila f p es la pila formada con las imágenes por f de los elementos de pila p, en el mismo orden. Por ejemplo,
|
1 2 |
λ> mapPila (+1) (apila 5 (apila 2 (apila 7 vacia))) 6 | 3 | 8 |
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 |
import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila) import Transformaciones_pilas_listas (listaApila, pilaAlista) import Test.QuickCheck.HigherOrder -- 1ª solución -- =========== mapPila1 :: (a -> a) -> Pila a -> Pila a mapPila1 f p | esVacia p = p | otherwise = apila (f cp) (mapPila1 f dp) where cp = cima p dp = desapila p -- 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 mapPila2 :: (a -> a) -> Pila a -> Pila a mapPila2 f p = listaApila (map f (pilaAlista p)) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_mapPila :: (Int -> Int) -> [Int] -> Bool prop_mapPila f p = mapPila1 f q == mapPila2 f q where q = listaApila p -- La comprobación es -- λ> quickCheck' prop_mapPila -- +++ 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 |
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 mapPila1(f: Callable[[A], A], p: Pila[A]) -> Pila[A]: if esVacia(p): return p cp = cima(p) dp = desapila(p) return apila(f(cp), mapPila1(f, dp)) # 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 mapPila2(f: Callable[[A], A], p: Pila[A]) -> Pila[A]: return listaApila(list(map(f, pilaAlista(p)))) # 3ª solución # =========== def mapPila3Aux(f: Callable[[A], A], p: Pila[A]) -> Pila[A]: if p.esVacia(): return p cp = p.cima() p.desapila() r = mapPila3Aux(f, p) r.apila(f(cp)) return r def mapPila3(f: Callable[[A], A], p: Pila[A]) -> Pila[A]: p1 = deepcopy(p) return mapPila3Aux(f, p1) # 4ª solución # =========== def mapPila4Aux(f: Callable[[A], A], p: Pila[A]) -> Pila[A]: r: Pila[A] = Pila() while not p.esVacia(): cp = p.cima() p.desapila() r.apila(f(cp)) r1: Pila[A] = Pila() while not r.esVacia(): r1.apila(r.cima()) r.desapila() return r1 def mapPila4(f: Callable[[A], A], p: Pila[A]) -> Pila[A]: p1 = deepcopy(p) return mapPila4Aux(f, p1) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(p=pilaAleatoria()) def test_mapPila(p: Pila[int]) -> None: r = mapPila1(lambda x: x + 1 == 0, p) assert mapPila2(lambda x: x + 1 == 0, p) == r assert mapPila3(lambda x: x + 1 == 0, p) == r assert mapPila4(lambda x: x + 1 == 0, p) == r # La comprobación es # src> poetry run pytest -q mapPila.py # 1 passed in 0.29s |
La función mapPila se puede definir de la siguiente manera:
La función recibe una función «f» y una pila «p». Utiliza recursión para recorrer los elementos de la pila «p» desde la cima hasta el fondo, aplicando la función «f» en cada elemento y agregando el resultado al fondo de una nueva pila que es devuelta como resultado. Si la pila «p» está vacía, se devuelve una pila vacía.