Ir al contenido principal

TAD de las pilas - Eliminación de repeticiones en una pila

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

Se usarán las funciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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
-- ===========

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
-- ===========

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.

Soluciones en Python

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
# ===========

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
# ===========

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