Utilizando el tipo abstracto de datos de las pilas, definir la función
ordenaInserPila :: Ord a => Pila a -> Pila a |
tal que ordenaInserPila p
es la pila obtenida ordenando por inserción los los elementos de la pila p
. Por ejemplo,
λ> ordenaInserPila (apila 4 (apila 1 (apila 3 vacia))) 1 | 3 | 4 |
Comprobar con QuickCheck que la pila (ordenaInserPila p)
está ordenada.
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 OrdenadaPila (ordenadaPila) import Test.QuickCheck -- 1ª solución -- =========== ordenaInserPila1 :: Ord a => Pila a -> Pila a ordenaInserPila1 p | esVacia p = p | otherwise = insertaPila cp (ordenaInserPila1 dp) where cp = cima p dp = desapila p insertaPila :: Ord a => a -> Pila a -> Pila a insertaPila x p | esVacia p = apila x p | x < cp = apila x p | otherwise = apila cp (insertaPila x dp) where cp = cima p dp = desapila p -- 2ª solución -- =========== ordenaInserPila2 :: Ord a => Pila a -> Pila a ordenaInserPila2 = listaApila . reverse . ordenaInserLista . pilaAlista ordenaInserLista :: Ord a => [a] -> [a] ordenaInserLista [] = [] ordenaInserLista (x: xs) = insertaLista x (ordenaInserLista xs) insertaLista :: Ord a => a -> [a] -> [a] insertaLista x [] = [x] insertaLista x (y:ys) | x < y = x : y : ys | otherwise = y : insertaLista x ys -- Se usarán las funciones listaApila y pilaAlista del ejercicio -- "Transformaciones entre pilas y listas" que se encuentra en -- https://bit.ly/3ZHewQ8 -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_ordenaInserPila :: Pila Int -> Bool prop_ordenaInserPila p = ordenaInserPila1 p == ordenaInserPila2 p -- La comprobación es -- λ> quickCheck prop_ordenaInserPila -- +++ OK, passed 100 tests. -- Comprobación de la propiedad -- ============================ -- Se usará la función ordenadaPila del ejercicio -- "Reconocimiento de ordenación de pilas" que se encuentra en -- https://bit.ly/3COqRbK -- La propiedad es prop_ordenadaOrdenaInserPila :: Pila Int -> Bool prop_ordenadaOrdenaInserPila p = ordenadaPila (ordenaInserPila1 p) -- La comprobación es -- λ> quickCheck prop_ordenadaOrdenaInserPila -- +++ OK, passed 100 tests. |
from copy import deepcopy from typing import TypeVar from hypothesis import given from src.ordenadaPila import ordenadaPila from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria, vacia) from src.transformaciones_pilas_listas import listaApila, pilaAlista A = TypeVar('A', int, float, str) # 1ª solución # =========== def insertaPila(x: A, p: Pila[A]) -> Pila[A]: if esVacia(p): return apila(x, p) cp = cima(p) if x < cp: return apila(x, p) dp = desapila(p) return apila(cp, insertaPila(x, dp)) def ordenaInserPila1(p: Pila[A]) -> Pila[A]: if esVacia(p): return p cp = cima(p) dp = desapila(p) return insertaPila(cp, ordenaInserPila1(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 insertaLista(x: A, ys: list[A]) -> list[A]: if not ys: return [x] if x < ys[0]: return [x] + ys return [ys[0]] + insertaLista(x, ys[1:]) def ordenaInserLista(xs: list[A]) -> list[A]: if not xs: return [] return insertaLista(xs[0], ordenaInserLista(xs[1:])) def ordenaInserPila2(p: Pila[A]) -> Pila[A]: return listaApila(list(reversed(ordenaInserLista(pilaAlista(p))))) # 3ª solución # =========== def ordenaInserPila3Aux(p: Pila[A]) -> Pila[A]: if p.esVacia(): return p cp = p.cima() p.desapila() return insertaPila(cp, ordenaInserPila3Aux(p)) def ordenaInserPila3(p: Pila[A]) -> Pila[A]: q = deepcopy(p) return ordenaInserPila3Aux(q) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(p=pilaAleatoria()) def test_ordenaInserPila(p: Pila[int]) -> None: r = ordenaInserPila1(p) assert ordenaInserPila2(p) == r assert ordenaInserPila3(p) == r # La comprobación es # src> poetry run pytest -q ordenaInserPila.py # 1 passed in 0.31s # Comprobación de la propiedad # ============================ # Se usará la función ordenadaPila del ejercicio # "Reconocimiento de ordenación de pilas" que se encuentra en # https://bit.ly/3COqRbK # La propiedad es @given(p=pilaAleatoria()) def test_ordenadaOrdenaInserPila(p: Pila[int]) -> None: ordenadaPila(ordenaInserPila1(p)) # La comprobación es # src> poetry run pytest -q ordenaInserPila.py # 2 passed in 0.47s |
La función ordenaInserPila se puede definir mediante una función auxiliar que inserta un elemento en la pila de manera ordenada y recursivamente llama a sí misma hasta que la pila original esté vacía. La función auxiliar se puede definir de la siguiente manera:
La función ordenaInserPila se puede definir como sigue: