Utilizando el tipo abstracto de datos de las pilas, definir la función
nubPila :: Eq a => Pila a -> Pila a |
tal que nubPila p
es la pila con los elementos de p
sin repeticiones. Por ejemplo,
λ> nubPila (apila 3 (apila 1 (apila 3 (apila 5 vacia)))) 1 | 3 | 5 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila) import Transformaciones_pilas_listas (listaApila, pilaAlista) import PertenecePila (pertenecePila) import Data.List (nub) import Test.QuickCheck -- 1ª solución -- =========== -- Se usará la función pertenecePila del ejercicio -- "Pertenencia a una pila" que se encuentra en -- https://bit.ly/3WdM9GC nubPila1 :: Eq a => Pila a -> Pila a nubPila1 p | esVacia p = vacia | pertenecePila cp dp = nubPila1 dp | otherwise = apila cp (nubPila1 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 nubPila2 :: Eq a => Pila a -> Pila a nubPila2 = listaApila . nub . pilaAlista -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_nubPila :: Pila Int -> Bool prop_nubPila p = nubPila1 p == nubPila2 p -- La comprobación es -- λ> quickCheck prop_nubPila -- +++ OK, passed 100 tests. |
from copy import deepcopy from typing import TypeVar from hypothesis import given from src.pertenecePila import pertenecePila 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 # =========== # Se usará la función pertenecePila del ejercicio # "Pertenencia a una pila" que se encuentra en # https://bit.ly/3WdM9GC def nubPila1(p: Pila[A]) -> Pila[A]: if esVacia(p): return p cp = cima(p) dp = desapila(p) if pertenecePila(cp, dp): return nubPila1(dp) return apila(cp, nubPila1(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 nub(xs: list[A]) -> list[A]: return [x for i, x in enumerate(xs) if x not in xs[:i]] def nubPila2(p: Pila[A]) -> Pila[A]: return listaApila(nub(pilaAlista(p))) # 3ª solución # =========== def nubPila3Aux(p: Pila[A]) -> Pila[A]: if p.esVacia(): return p cp = p.cima() p.desapila() if pertenecePila(cp, p): return nubPila3Aux(p) return apila(cp, nubPila3Aux(p)) def nubPila3(p: Pila[A]) -> Pila[A]: q = deepcopy(p) return nubPila3Aux(q) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(p=pilaAleatoria()) def test_nubPila(p: Pila[int]) -> None: r = nubPila1(p) assert nubPila2(p) == r assert nubPila3(p) == r # La comprobación es # src> poetry run pytest -q nubPila.py # 1 passed in 0.27s |