23-enero-2023 – Exercitium

TAD de las pilas: Transformaciones entre pilas y listas

PorJosé A. Alonso 23-enero-202322-enero-2023

Utilizando el tipo abstracto de datos de las pilas, definir las funciones

   listaApila :: [a] -> Pila a
   pilaAlista :: Pila a -> [a]

1 2	listaApila :: [a] -> Pila a pilaAlista :: Pila a -> [a]

tales que

listaApila xs es la pila formada por los elementos de xs. Por ejemplo,

     λ> listaApila [3, 2, 5]
     5 | 2 | 3

1 2	λ> listaApila [3, 2, 5] 5 \| 2 \| 3

pilaAlista p es la lista formada por los elementos de la pila p. Por ejemplo,

     λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia)))
     [3, 2, 5]

1 2	λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia))) [3, 2, 5]

Comprobar con QuickCheck que ambas funciones son inversa; es decir,

   pilaAlista (listaApila xs) == xs
   listaApila (pilaAlista p)  == p

1 2	pilaAlista (listaApila xs) == xs listaApila (pilaAlista p) == p

Soluciones

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

Soluciones en Haskell

module Transformaciones_pilas_listas where

import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)
import Test.QuickCheck

-- 1ª definición de listaApila
-- ===========================

listaApila :: [a] -> Pila a
listaApila ys = aux (reverse ys)
  where aux []     = vacia
        aux (x:xs) = apila x (aux xs)

-- 2ª definición de listaApila
-- ===========================

listaApila2 :: [a] -> Pila a
listaApila2 = aux . reverse
  where aux [] = vacia
        aux (x:xs) = apila x (aux xs)

-- 3ª definición de listaApila
-- ===========================

listaApila3 :: [a] -> Pila a
listaApila3 = aux . reverse
  where aux = foldr apila vacia

-- 4ª definición de listaApila
-- ===========================

listaApila4 :: [a] -> Pila a
listaApila4 xs = foldr apila vacia (reverse xs)

-- 5ª definición de listaApila
-- ===========================

listaApila5 :: [a] -> Pila a
listaApila5 = foldr apila vacia . reverse

-- Comprobación de equivalencia de las definiciones de listaApila
-- ==============================================================

-- La propiedad es
prop_listaApila :: [Int] -> Bool
prop_listaApila xs =
  all (== listaApila xs)
      [listaApila2 xs,
       listaApila3 xs,
       listaApila4 xs,
       listaApila5 xs]

-- La comprobación es
--    λ> quickCheck prop_listaApila
--    +++ OK, passed 100 tests.

-- 1ª definición de pilaAlista
-- ===========================

pilaAlista :: Pila a -> [a]
pilaAlista p
  | esVacia p = []
  | otherwise = pilaAlista dp ++ [cp]
  where cp = cima p
        dp = desapila p

-- 2ª definición de pilaAlista
-- ===========================

pilaAlista2 :: Pila a -> [a]
pilaAlista2 = reverse . aux
  where aux p | esVacia p = []
              | otherwise = cp : aux dp
          where cp = cima p
                dp = desapila p

-- Comprobación de equivalencia de las definiciones de pilaAlista
-- ==============================================================

-- La propiedad es
prop_pilaAlista :: Pila Int -> Bool
prop_pilaAlista p =
  pilaAlista p == pilaAlista2 p

-- La comprobación es
--    λ> quickCheck prop_pilaAlista
--    +++ OK, passed 100 tests.

-- Comprobación de las propiedades
-- ===============================

-- La primera propiedad es
prop_1_listaApila :: [Int] -> Bool
prop_1_listaApila xs =
  pilaAlista (listaApila xs) == xs

-- La comprobación es
--    λ> quickCheck prop_1_listaApila
--    +++ OK, passed 100 tests.

-- La segunda propiedad es
prop_2_listaApila :: Pila Int -> Bool
prop_2_listaApila p =
  listaApila (pilaAlista p) == p

-- La comprobación es
--    λ> quickCheck prop_2_listaApila
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

module Transformaciones_pilas_listas where

import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)

import Test.QuickCheck

-- 1ª definición de listaApila

-- ===========================

listaApila :: [a] -> Pila a

listaApila ys = aux (reverse ys)

where aux [] = vacia

aux (x:xs) = apila x (aux xs)

-- 2ª definición de listaApila

-- ===========================

listaApila2 :: [a] -> Pila a

listaApila2 = aux . reverse

where aux [] = vacia

aux (x:xs) = apila x (aux xs)

-- 3ª definición de listaApila

-- ===========================

listaApila3 :: [a] -> Pila a

listaApila3 = aux . reverse

where aux = foldr apila vacia

-- 4ª definición de listaApila

-- ===========================

listaApila4 :: [a] -> Pila a

listaApila4 xs = foldr apila vacia (reverse xs)

-- 5ª definición de listaApila

-- ===========================

listaApila5 :: [a] -> Pila a

listaApila5 = foldr apila vacia . reverse

-- Comprobación de equivalencia de las definiciones de listaApila

-- ==============================================================

-- La propiedad es

prop_listaApila :: [Int] -> Bool

prop_listaApila xs =

all (== listaApila xs)

[listaApila2 xs,

listaApila3 xs,

listaApila4 xs,

listaApila5 xs]

-- La comprobación es

-- λ> quickCheck prop_listaApila

-- +++ OK, passed 100 tests.

-- 1ª definición de pilaAlista

-- ===========================

pilaAlista :: Pila a -> [a]

pilaAlista p

| esVacia p = []

| otherwise = pilaAlista dp ++ [cp]

where cp = cima p

dp = desapila p

-- 2ª definición de pilaAlista

-- ===========================

pilaAlista2 :: Pila a -> [a]

pilaAlista2 = reverse . aux

where aux p | esVacia p = []

| otherwise = cp : aux dp

where cp = cima p

dp = desapila p

-- Comprobación de equivalencia de las definiciones de pilaAlista

-- ==============================================================

-- La propiedad es

prop_pilaAlista :: Pila Int -> Bool

prop_pilaAlista p =

pilaAlista p == pilaAlista2 p

-- La comprobación es

-- λ> quickCheck prop_pilaAlista

-- +++ OK, passed 100 tests.

-- Comprobación de las propiedades

-- ===============================

-- La primera propiedad es

prop_1_listaApila :: [Int] -> Bool

prop_1_listaApila xs =

pilaAlista (listaApila xs) == xs

-- La comprobación es

-- λ> quickCheck prop_1_listaApila

-- +++ OK, passed 100 tests.

-- La segunda propiedad es

prop_2_listaApila :: Pila Int -> Bool

prop_2_listaApila p =

listaApila (pilaAlista p) == p

-- La comprobación es

-- λ> quickCheck prop_2_listaApila

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,
                          vacia)

A = TypeVar('A')

# 1ª definición de listaApila
# ===========================

def listaApila(ys: list[A]) -> Pila[A]:
    def aux(xs: list[A]) -> Pila[A]:
        if not xs:
            return vacia()
        return apila(xs[0], aux(xs[1:]))

    return aux(list(reversed(ys)))

# 2ª solución de listaApila
# =========================

def listaApila2(xs: list[A]) -> Pila[A]:
    p: Pila[A] = Pila()
    for x in xs:
        p.apila(x)
    return p

# Comprobación de equivalencia de las definiciones de listaApila
# ==============================================================

# La propiedad es
@given(st.lists(st.integers()))
def test_listaApila(xs: list[int]) -> None:
    assert listaApila(xs) == listaApila2(xs)

# 1ª definición de pilaAlista
# ===========================

def pilaAlista(p: Pila[A]) -> list[A]:
    if esVacia(p):
        return []
    cp = cima(p)
    dp = desapila(p)
    return pilaAlista(dp) + [cp]

# 2ª definición de pilaAlista
# ===========================

def pilaAlista2Aux(p: Pila[A]) -> list[A]:
    if p.esVacia():
        return []
    cp = p.cima()
    p.desapila()
    return pilaAlista2Aux(p) + [cp]

def pilaAlista2(p: Pila[A]) -> list[A]:
    p1 = deepcopy(p)
    return pilaAlista2Aux(p1)

# 3ª definición de pilaAlista
# ===========================

def pilaAlista3Aux(p: Pila[A]) -> list[A]:
    r = []
    while not p.esVacia():
        r.append(p.cima())
        p.desapila()
    return r[::-1]

def pilaAlista3(p: Pila[A]) -> list[A]:
    p1 = deepcopy(p)
    return pilaAlista3Aux(p1)

# Comprobación de equivalencia de las definiciones de pilaAlista
# ==============================================================

@given(p=pilaAleatoria())
def test_pilaAlista(p: Pila[int]) -> None:
    assert pilaAlista(p) == pilaAlista2(p)
    assert pilaAlista(p) == pilaAlista3(p)

# Comprobación de las propiedades
# ===============================

# La primera propiedad es
@given(st.lists(st.integers()))
def test_1_listaApila(xs: list[int]) -> None:
    assert pilaAlista(listaApila(xs)) == xs

# La segunda propiedad es
@given(p=pilaAleatoria())
def test_2_listaApila(p: Pila[int]) -> None:
    assert listaApila(pilaAlista(p)) == p

# La comprobación es
#      src> poetry run pytest -v transformaciones_pilas_listas.py
#      test_listaApila PASSED
#      test_pilaAlista PASSED
#      test_1_listaApila PASSED
#      test_2_listaApila PASSED

100

101

102

103

104

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,

vacia)

A = TypeVar('A')

# 1ª definición de listaApila

# ===========================

def listaApila(ys: list[A]) -> Pila[A]:

def aux(xs: list[A]) -> Pila[A]:

if not xs:

return vacia()

return apila(xs[0], aux(xs[1:]))

return aux(list(reversed(ys)))

# 2ª solución de listaApila

# =========================

def listaApila2(xs: list[A]) -> Pila[A]:

p: Pila[A] = Pila()

for x in xs:

p.apila(x)

return p

# Comprobación de equivalencia de las definiciones de listaApila

# ==============================================================

# La propiedad es

@given(st.lists(st.integers()))

def test_listaApila(xs: list[int]) -> None:

assert listaApila(xs) == listaApila2(xs)

# 1ª definición de pilaAlista

# ===========================

def pilaAlista(p: Pila[A]) -> list[A]:

if esVacia(p):

return []

cp = cima(p)

dp = desapila(p)

return pilaAlista(dp) + [cp]

# 2ª definición de pilaAlista

# ===========================

def pilaAlista2Aux(p: Pila[A]) -> list[A]:

if p.esVacia():

return []

cp = p.cima()

p.desapila()

return pilaAlista2Aux(p) + [cp]

def pilaAlista2(p: Pila[A]) -> list[A]:

p1 = deepcopy(p)

return pilaAlista2Aux(p1)

# 3ª definición de pilaAlista

# ===========================

def pilaAlista3Aux(p: Pila[A]) -> list[A]:

r = []

while not p.esVacia():

r.append(p.cima())

p.desapila()

return r[::-1]

def pilaAlista3(p: Pila[A]) -> list[A]:

p1 = deepcopy(p)

return pilaAlista3Aux(p1)

# Comprobación de equivalencia de las definiciones de pilaAlista

# ==============================================================

@given(p=pilaAleatoria())

def test_pilaAlista(p: Pila[int]) -> None:

assert pilaAlista(p) == pilaAlista2(p)

assert pilaAlista(p) == pilaAlista3(p)

# Comprobación de las propiedades

# ===============================

# La primera propiedad es

@given(st.lists(st.integers()))

def test_1_listaApila(xs: list[int]) -> None:

assert pilaAlista(listaApila(xs)) == xs

# La segunda propiedad es

@given(p=pilaAleatoria())

def test_2_listaApila(p: Pila[int]) -> None:

assert listaApila(pilaAlista(p)) == p

# La comprobación es

# src> poetry run pytest -v transformaciones_pilas_listas.py

# test_listaApila PASSED

# test_pilaAlista PASSED

# test_1_listaApila PASSED

# test_2_listaApila PASSED

Día: 23-enero-2023

TAD de las pilas: Transformaciones entre pilas y listas

Entradas recientes

Buscar

Correo electrónico