PFH: La semana en Exercitium (28 de enero de 2023)

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:

1. TAD de las pilas: Transformaciones entre pilas y listas
2. TAD de las pilas: Filtrado de pilas según una propiedad
3. TAD de las pilas: Aplicación de una función a los elementos de una pila
4. TAD de las pilas: Pertenencia a una pila
5. TAD de las pilas: Inclusión de pilas

A continuación se muestran las soluciones.

1. TAD de las pilas: Transformaciones entre pilas y listas

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

2. TAD de las pilas: Filtrado de pilas según una propiedad

Utilizando el tipo abstracto de datos de las pilas, definir la función

   filtraPila :: (a -> Bool) -> Pila a -> Pila a

1	filtraPila :: (a -> Bool) -> Pila a -> Pila a

tal que filtraPila p q es la pila obtenida con los elementos de pila q que verifican el predicado p, en el mismo orden. Por ejemplo,

   λ> ejPila = apila 6 (apila 3 (apila 1 (apila 4 vacia)))
   λ> ejPila
   6 | 3 | 1 | 4
   λ> filtraPila even ejPila
   6 | 4
   λ> filtraPila odd ejPila
   3 | 1

λ> ejPila = apila 6 (apila 3 (apila 1 (apila 4 vacia)))

λ> ejPila

6 | 3 | 1 | 4

λ> filtraPila even ejPila

6 | 4

λ> filtraPila odd ejPila

3 | 1

Soluciones

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 Test.QuickCheck.HigherOrder

-- 1ª solución
-- ===========

filtraPila1 :: (a -> Bool) -> Pila a -> Pila a
filtraPila1 p q
  | esVacia q = vacia
  | p cq      = apila cq (filtraPila1 p dq)
  | otherwise = filtraPila1 p dq
  where cq = cima q
        dq = desapila q

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

filtraPila2 :: (a -> Bool) -> Pila a -> Pila a
filtraPila2 p q =
  listaApila (filter p (pilaAlista q))

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_filtraPila :: (Int -> Bool) -> [Int] -> Bool
prop_filtraPila p xs =
  filtraPila1 p q == filtraPila2 p q
  where q = listaApila xs

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

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

import Transformaciones_pilas_listas (listaApila, pilaAlista)

import Test.QuickCheck.HigherOrder

-- 1ª solución

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

filtraPila1 :: (a -> Bool) -> Pila a -> Pila a

filtraPila1 p q

| esVacia q = vacia

| p cq = apila cq (filtraPila1 p dq)

| otherwise = filtraPila1 p dq

where cq = cima q

dq = desapila q

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

filtraPila2 :: (a -> Bool) -> Pila a -> Pila a

filtraPila2 p q =

listaApila (filter p (pilaAlista q))

-- Comprobación de equivalencia

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

-- La propiedad es

prop_filtraPila :: (Int -> Bool) -> [Int] -> Bool

prop_filtraPila p xs =

filtraPila1 p q == filtraPila2 p q

where q = listaApila xs

-- La comprobación es

-- λ> quickCheck' prop_filtraPila

-- +++ OK, passed 100 tests.

Soluciones en Python

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 filtraPila1(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:
    if esVacia(q):
        return q
    cq = cima(q)
    dq = desapila(q)
    r = filtraPila1(p, dq)
    if p(cq):
        return apila(cq, r)
    return r

# 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 filtraPila2(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:
    return listaApila(list(filter(p, pilaAlista(q))))

# 3ª solución
# ===========

def filtraPila3Aux(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:
    if q.esVacia():
        return q
    cq = q.cima()
    q.desapila()
    r = filtraPila3Aux(p, q)
    if p(cq):
        r.apila(cq)
    return r

def filtraPila3(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:
    q1 = deepcopy(q)
    return filtraPila3Aux(p, q1)

# 4ª solución
# ===========

def filtraPila4Aux(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:
    r: Pila[A] = Pila()
    while not q.esVacia():
        cq = q.cima()
        q.desapila()
        if p(cq):
            r.apila(cq)
    r1: Pila[A] = Pila()
    while not r.esVacia():
        r1.apila(r.cima())
        r.desapila()
    return r1

def filtraPila4(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:
    q1 = deepcopy(q)
    return filtraPila4Aux(p, q1)

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

# La propiedad es
@given(p=pilaAleatoria())
def test_filtraPila(p: Pila[int]) -> None:
    r = filtraPila1(lambda x: x % 2 == 0, p)
    assert filtraPila2(lambda x: x % 2 == 0, p) == r
    assert filtraPila3(lambda x: x % 2 == 0, p) == r
    assert filtraPila4(lambda x: x % 2 == 0, p) == r

# La comprobación es
#    src> poetry run pytest -q filtraPila.py
#    1 passed in 0.25s

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 filtraPila1(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:

if esVacia(q):

return q

cq = cima(q)

dq = desapila(q)

r = filtraPila1(p, dq)

if p(cq):

return apila(cq, r)

return r

# 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 filtraPila2(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:

return listaApila(list(filter(p, pilaAlista(q))))

# 3ª solución

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

def filtraPila3Aux(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:

if q.esVacia():

return q

cq = q.cima()

q.desapila()

r = filtraPila3Aux(p, q)

if p(cq):

r.apila(cq)

return r

def filtraPila3(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:

q1 = deepcopy(q)

return filtraPila3Aux(p, q1)

# 4ª solución

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

def filtraPila4Aux(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:

r: Pila[A] = Pila()

while not q.esVacia():

cq = q.cima()

q.desapila()

if p(cq):

r.apila(cq)

r1: Pila[A] = Pila()

while not r.esVacia():

r1.apila(r.cima())

r.desapila()

return r1

def filtraPila4(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:

q1 = deepcopy(q)

return filtraPila4Aux(p, q1)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(p=pilaAleatoria())

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

r = filtraPila1(lambda x: x % 2 == 0, p)

assert filtraPila2(lambda x: x % 2 == 0, p) == r

assert filtraPila3(lambda x: x % 2 == 0, p) == r

assert filtraPila4(lambda x: x % 2 == 0, p) == r

# La comprobación es

# src> poetry run pytest -q filtraPila.py

# 1 passed in 0.25s

3. 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

   mapPila :: (a -> a) -> Pila a -> Pila a

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,

   λ> mapPila (+1) (apila 5 (apila 2 (apila 7 vacia)))
   6 | 3 | 8

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.

Soluciones en Haskell

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.

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.

Soluciones en Python

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

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

4. TAD de las pilas: Pertenencia a una pila

Utilizando el tipo abstracto de datos de las pilas, definir la función

   pertenecePila :: Eq a => a -> Pila a -> Bool

1	pertenecePila :: Eq a => a -> Pila a -> Bool

tal que pertenecePila x p se verifica si x es un elemento de la pila p. Por ejemplo,

   pertenecePila 2 (apila 5 (apila 2 (apila 3 vacia))) == True
   pertenecePila 4 (apila 5 (apila 2 (apila 3 vacia))) == False

1 2	pertenecePila 2 (apila 5 (apila 2 (apila 3 vacia))) == True pertenecePila 4 (apila 5 (apila 2 (apila 3 vacia))) == False

Soluciones

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 (pilaAlista)
import Test.QuickCheck

-- 1ª solución
-- ===========

pertenecePila :: Eq a => a -> Pila a -> Bool
pertenecePila x p
  | esVacia p  = False
  | otherwise  = x == cp || pertenecePila x dp
  where cp = cima p
        dp = desapila p

-- 2ª solución
-- ===========

-- Se usará la función pilaAlista del ejercicio
-- "Transformaciones entre pilas y listas" que se encuentra en
-- https://bit.ly/3ZHewQ8

pertenecePila2 :: Eq a => a -> Pila a -> Bool
pertenecePila2 x p =
  x `elem` pilaAlista p

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_pertenecePila :: Int -> Pila Int -> Bool
prop_pertenecePila x p =
  pertenecePila x p == pertenecePila2 x p

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

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

import Transformaciones_pilas_listas (pilaAlista)

import Test.QuickCheck

-- 1ª solución

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

pertenecePila :: Eq a => a -> Pila a -> Bool

pertenecePila x p

| esVacia p = False

| otherwise = x == cp || pertenecePila x dp

where cp = cima p

dp = desapila p

-- 2ª solución

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

-- Se usará la función pilaAlista del ejercicio

-- "Transformaciones entre pilas y listas" que se encuentra en

-- https://bit.ly/3ZHewQ8

pertenecePila2 :: Eq a => a -> Pila a -> Bool

pertenecePila2 x p =

x `elem` pilaAlista p

-- Comprobación de equivalencia

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

-- La propiedad es

prop_pertenecePila :: Int -> Pila Int -> Bool

prop_pertenecePila x p =

pertenecePila x p == pertenecePila2 x p

-- La comprobación es

-- λ> quickCheck prop_pertenecePila

-- +++ 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)
from src.transformaciones_pilas_listas import pilaAlista

A = TypeVar('A')

# 1ª solución
# ===========

def pertenecePila(x: A, p: Pila[A]) -> bool:
    if esVacia(p):
        return False
    cp = cima(p)
    dp = desapila(p)
    return x == cp or pertenecePila(x, dp)

# 2ª solución
# ===========

# Se usará la función pilaAlista del ejercicio
# "Transformaciones entre pilas y listas" que se encuentra en
# https://bit.ly/3ZHewQ8

def pertenecePila2(x: A, p: Pila[A]) -> bool:
    return x in pilaAlista(p)

# 3ª solución
# ===========

def pertenecePila3Aux(x: A, p: Pila[A]) -> bool:
    if p.esVacia():
        return False
    cp = p.cima()
    p.desapila()
    return x == cp or pertenecePila3Aux(x, p)

def pertenecePila3(x: A, p: Pila[A]) -> bool:
    p1 = deepcopy(p)
    return pertenecePila3Aux(x, p1)

# 4ª solución
# ===========

def pertenecePila4Aux(x: A, p: Pila[A]) -> bool:
    while not p.esVacia():
        cp = p.cima()
        p.desapila()
        if x == cp:
            return True
    return False

def pertenecePila4(x: A, p: Pila[A]) -> bool:
    p1 = deepcopy(p)
    return pertenecePila4Aux(x, p1)

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

# La propiedad es
@given(x=st.integers(), p=pilaAleatoria())
def test_pertenecePila(x: int, p: Pila[int]) -> None:
    r = pertenecePila(x, p)
    assert pertenecePila2(x, p) == r
    assert pertenecePila3(x, p) == r
    assert pertenecePila4(x, p) == r

# La comprobación es
#    src> poetry run pytest -q pertenecePila.py
#    1 passed in 0.37s

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)

from src.transformaciones_pilas_listas import pilaAlista

A = TypeVar('A')

# 1ª solución

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

def pertenecePila(x: A, p: Pila[A]) -> bool:

if esVacia(p):

return False

cp = cima(p)

dp = desapila(p)

return x == cp or pertenecePila(x, dp)

# 2ª solución

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

# Se usará la función pilaAlista del ejercicio

# "Transformaciones entre pilas y listas" que se encuentra en

# https://bit.ly/3ZHewQ8

def pertenecePila2(x: A, p: Pila[A]) -> bool:

return x in pilaAlista(p)

# 3ª solución

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

def pertenecePila3Aux(x: A, p: Pila[A]) -> bool:

if p.esVacia():

return False

cp = p.cima()

p.desapila()

return x == cp or pertenecePila3Aux(x, p)

def pertenecePila3(x: A, p: Pila[A]) -> bool:

p1 = deepcopy(p)

return pertenecePila3Aux(x, p1)

# 4ª solución

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

def pertenecePila4Aux(x: A, p: Pila[A]) -> bool:

while not p.esVacia():

cp = p.cima()

p.desapila()

if x == cp:

return True

return False

def pertenecePila4(x: A, p: Pila[A]) -> bool:

p1 = deepcopy(p)

return pertenecePila4Aux(x, p1)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(x=st.integers(), p=pilaAleatoria())

def test_pertenecePila(x: int, p: Pila[int]) -> None:

r = pertenecePila(x, p)

assert pertenecePila2(x, p) == r

assert pertenecePila3(x, p) == r

assert pertenecePila4(x, p) == r

# La comprobación es

# src> poetry run pytest -q pertenecePila.py

# 1 passed in 0.37s

5. TAD de las pilas: Inclusión de pilas

Utilizando el tipo abstracto de datos de las pilas, definir la función

   contenidaPila :: Eq a => Pila a -> Pila a -> Bool

1	contenidaPila :: Eq a => Pila a -> Pila a -> Bool

tal que contenidaPila p1 p2 se verifica si todos los elementos de de la pila p1 son elementos de la pila p2. Por ejemplo,

   λ> ej1 = apila 3 (apila 2 vacia)
   λ> ej2 = apila 3 (apila 4 vacia)
   λ> ej3 = apila 5 (apila 2 (apila 3 vacia))
   λ> contenidaPila ej1 ej3
   True
   λ> contenidaPila ej2 ej3
   False

λ> ej1 = apila 3 (apila 2 vacia)

λ> ej2 = apila 3 (apila 4 vacia)

λ> ej3 = apila 5 (apila 2 (apila 3 vacia))

λ> contenidaPila ej1 ej3

True

λ> contenidaPila ej2 ej3

False

Soluciones

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 PertenecePila (pertenecePila)
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

contenidaPila1 :: Eq a => Pila a -> Pila a -> Bool
contenidaPila1 p1 p2
  | esVacia p1 = True
  | otherwise  = pertenecePila cp1 p2 && contenidaPila1 dp1 p2
  where cp1 = cima p1
        dp1 = desapila p1

-- 2ª solución
-- ===========

contenidaPila2 :: Eq a => Pila a -> Pila a -> Bool
contenidaPila2 p1 p2 =
  contenidaLista (pilaAlista p1) (pilaAlista p2)

contenidaLista :: Eq a => [a] -> [a] -> Bool
contenidaLista xs ys =
  all (`elem` ys) xs

-- (pilaALista p) es la lista formada por los elementos de la
-- lista p. Por ejemplo,
--    λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia)))
--    [3, 2, 5]
pilaAlista :: Pila a -> [a]
pilaAlista = reverse . aux
  where aux p | esVacia p = []
              | otherwise = cp : aux dp
          where cp = cima p
                dp = desapila p

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_contenidaPila :: Pila Int -> Pila Int -> Bool
prop_contenidaPila p1 p2 =
  contenidaPila1 p1 p2 == contenidaPila2 p1 p2

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

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

import PertenecePila (pertenecePila)

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

contenidaPila1 :: Eq a => Pila a -> Pila a -> Bool

contenidaPila1 p1 p2

| esVacia p1 = True

| otherwise = pertenecePila cp1 p2 && contenidaPila1 dp1 p2

where cp1 = cima p1

dp1 = desapila p1

-- 2ª solución

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

contenidaPila2 :: Eq a => Pila a -> Pila a -> Bool

contenidaPila2 p1 p2 =

contenidaLista (pilaAlista p1) (pilaAlista p2)

contenidaLista :: Eq a => [a] -> [a] -> Bool

contenidaLista xs ys =

all (`elem` ys) xs

-- (pilaALista p) es la lista formada por los elementos de la

-- lista p. Por ejemplo,

-- λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia)))

-- [3, 2, 5]

pilaAlista :: Pila a -> [a]

pilaAlista = reverse . aux

where aux p | esVacia p = []

| otherwise = cp : aux dp

where cp = cima p

dp = desapila p

-- Comprobación de equivalencia

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

-- La propiedad es

prop_contenidaPila :: Pila Int -> Pila Int -> Bool

prop_contenidaPila p1 p2 =

contenidaPila1 p1 p2 == contenidaPila2 p1 p2

-- La comprobación es

-- λ> quickCheck prop_contenidaPila

-- +++ 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 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 contenidaPila1(p1: Pila[A], p2: Pila[A]) -> bool:
    if esVacia(p1):
        return True
    cp1 = cima(p1)
    dp1 = desapila(p1)
    return pertenecePila(cp1, p2) and contenidaPila1(dp1, p2)

# 2ª solución
# ===========

# Se usará la función pilaAlista del ejercicio
# "Transformaciones entre pilas y listas" que se encuentra en
# https://bit.ly/3ZHewQ8

def contenidaPila2(p1: Pila[A], p2: Pila[A]) -> bool:
    return set(pilaAlista(p1)) <= set(pilaAlista(p2))

# 3ª solución
# ===========

def contenidaPila3Aux(p1: Pila[A], p2: Pila[A]) -> bool:
    if p1.esVacia():
        return True
    cp1 = p1.cima()
    p1.desapila()
    return pertenecePila(cp1, p2) and contenidaPila1(p1, p2)

def contenidaPila3(p1: Pila[A], p2: Pila[A]) -> bool:
    q = deepcopy(p1)
    return contenidaPila3Aux(q, p2)

# 4ª solución
# ===========

def contenidaPila4Aux(p1: Pila[A], p2: Pila[A]) -> bool:
    while not p1.esVacia():
        cp1 = p1.cima()
        p1.desapila()
        if not pertenecePila(cp1, p2):
            return False
    return True

def contenidaPila4(p1: Pila[A], p2: Pila[A]) -> bool:
    q = deepcopy(p1)
    return contenidaPila4Aux(q, p2)

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

# La propiedad es
@given(p1=pilaAleatoria(), p2=pilaAleatoria())
def test_contenidaPila(p1: Pila[int], p2: Pila[int]) -> None:
    r = contenidaPila1(p1, p2)
    assert contenidaPila2(p1, p2) == r
    assert contenidaPila3(p1, p2) == r
    assert contenidaPila4(p1, p2) == r

# La comprobación es
#    src> poetry run pytest -q contenidaPila.py
#    1 passed in 0.40s

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 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 contenidaPila1(p1: Pila[A], p2: Pila[A]) -> bool:

if esVacia(p1):

return True

cp1 = cima(p1)

dp1 = desapila(p1)

return pertenecePila(cp1, p2) and contenidaPila1(dp1, p2)

# 2ª solución

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

# Se usará la función pilaAlista del ejercicio

# "Transformaciones entre pilas y listas" que se encuentra en

# https://bit.ly/3ZHewQ8

def contenidaPila2(p1: Pila[A], p2: Pila[A]) -> bool:

return set(pilaAlista(p1)) <= set(pilaAlista(p2))

# 3ª solución

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

def contenidaPila3Aux(p1: Pila[A], p2: Pila[A]) -> bool:

if p1.esVacia():

return True

cp1 = p1.cima()

p1.desapila()

return pertenecePila(cp1, p2) and contenidaPila1(p1, p2)

def contenidaPila3(p1: Pila[A], p2: Pila[A]) -> bool:

q = deepcopy(p1)

return contenidaPila3Aux(q, p2)

# 4ª solución

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

def contenidaPila4Aux(p1: Pila[A], p2: Pila[A]) -> bool:

while not p1.esVacia():

cp1 = p1.cima()

p1.desapila()

if not pertenecePila(cp1, p2):

return False

return True

def contenidaPila4(p1: Pila[A], p2: Pila[A]) -> bool:

q = deepcopy(p1)

return contenidaPila4Aux(q, p2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(p1=pilaAleatoria(), p2=pilaAleatoria())

def test_contenidaPila(p1: Pila[int], p2: Pila[int]) -> None:

r = contenidaPila1(p1, p2)

assert contenidaPila2(p1, p2) == r

assert contenidaPila3(p1, p2) == r

assert contenidaPila4(p1, p2) == r

# La comprobación es

# src> poetry run pytest -q contenidaPila.py

# 1 passed in 0.40s

1. TAD de las pilas: Transformaciones entre pilas y listas

2. TAD de las pilas: Filtrado de pilas según una propiedad

3. TAD de las pilas: Aplicación de una función a los elementos de una pila

4. TAD de las pilas: Pertenencia a una pila

5. TAD de las pilas: Inclusión de pilas

Se puede imprimir o compartir con