TAD

TAD de las colas: Todos los elementos verifican una propiedad

PorJosé A. Alonso 13-febrero-202324-enero-2023

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

   todosVerifican :: (a -> Bool) -> Cola a -> Bool

1	todosVerifican :: (a -> Bool) -> Cola a -> Bool

tal que todosVerifican p c se verifica si todos los elementos de la cola c cumplen la propiedad p. Por ejemplo,

   todosVerifican (>0) (inserta 3 (inserta 2 vacia))    == True
   todosVerifican (>0) (inserta 3 (inserta (-2) vacia)) == False

1 2	todosVerifican (>0) (inserta 3 (inserta 2 vacia)) == True todosVerifican (>0) (inserta 3 (inserta (-2) vacia)) == False

Soluciones

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

Soluciones en Haskell

import TAD.Cola (Cola, vacia, inserta, primero, resto, esVacia)
import Transformaciones_colas_listas (colaAlista, listaAcola)
import Test.QuickCheck.HigherOrder

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

todosVerifican1 :: (a -> Bool) -> Cola a -> Bool
todosVerifican1 p c
  | esVacia c = True
  | otherwise = p pc && todosVerifican1 p rc
  where pc = primero c
        rc = resto c

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

todosVerifican2 :: (a -> Bool) -> Cola a -> Bool
todosVerifican2 p c =
  all p (colaAlista c)

-- La función colaAlista está definida en el ejercicio
-- "Transformaciones entre colas y listas" que se encuentra en
-- https://bit.ly/3Xv0oIt

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

-- La propiedad es
prop_todosVerifican :: (Int -> Bool) -> [Int] -> Bool
prop_todosVerifican p xs =
  todosVerifican1 p c == todosVerifican2 p c
  where c = listaAcola xs

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

import TAD.Cola (Cola, vacia, inserta, primero, resto, esVacia)

import Transformaciones_colas_listas (colaAlista, listaAcola)

import Test.QuickCheck.HigherOrder

-- 1ª solución

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

todosVerifican1 :: (a -> Bool) -> Cola a -> Bool

todosVerifican1 p c

| esVacia c = True

| otherwise = p pc && todosVerifican1 p rc

where pc = primero c

rc = resto c

-- 2ª solución

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

todosVerifican2 :: (a -> Bool) -> Cola a -> Bool

todosVerifican2 p c =

all p (colaAlista c)

-- La función colaAlista está definida en el ejercicio

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

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

-- Comprobación de equivalencia

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

-- La propiedad es

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

prop_todosVerifican p xs =

todosVerifican1 p c == todosVerifican2 p c

where c = listaAcola xs

-- La comprobación es

-- λ> quickCheck' prop_todosVerifican

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import Callable, TypeVar

from hypothesis import given

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,
                          resto, vacia)
from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

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

def todosVerifican1(p: Callable[[A], bool], c: Cola[A]) -> bool:
    if esVacia(c):
        return True
    pc = primero(c)
    rc = resto(c)
    return p(pc) and todosVerifican1(p, rc)

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

def todosVerifican2(p: Callable[[A], bool], c: Cola[A]) -> bool:
    return all(p(x) for x in colaAlista(c))

# La función colaAlista está definida en el ejercicio
# "Transformaciones entre colas y listas" que se encuentra en
# https://bit.ly/3Xv0oIt

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

def todosVerifican3Aux(p: Callable[[A], bool], c: Cola[A]) -> bool:
    if c.esVacia():
        return True
    pc = c.primero()
    c.resto()
    return p(pc) and todosVerifican3Aux(p, c)

def todosVerifican3(p: Callable[[A], bool], c: Cola[A]) -> bool:
    _c = deepcopy(c)
    return todosVerifican3Aux(p, _c)

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

def todosVerifican4Aux(p: Callable[[A], bool], c: Cola[A]) -> bool:
    if c.esVacia():
        return True
    pc = c.primero()
    c.resto()
    return p(pc) and todosVerifican4Aux(p, c)

def todosVerifican4(p: Callable[[A], bool], c: Cola[A]) -> bool:
    _c = deepcopy(c)
    return todosVerifican4Aux(p, _c)

# 5ª solución
# ===========

def todosVerifican5Aux(p: Callable[[A], bool], c: Cola[A]) -> bool:
    while not c.esVacia():
        if not p(c.primero()):
            return False
        c.resto()
    return True

def todosVerifican5(p: Callable[[A], bool], c: Cola[A]) -> bool:
    _c = deepcopy(c)
    return todosVerifican5Aux(p, _c)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(c=colaAleatoria())
def test_filtraPila(c: Cola[int]) -> None:
    r = todosVerifican1(lambda x: x > 0, c)
    assert todosVerifican2(lambda x: x > 0, c) == r
    assert todosVerifican3(lambda x: x > 0, c) == r
    assert todosVerifican4(lambda x: x > 0, c) == r
    assert todosVerifican5(lambda x: x > 0, c) == r

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

from copy import deepcopy

from typing import Callable, TypeVar

from hypothesis import given

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,

resto, vacia)

from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

# 1ª solución

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

def todosVerifican1(p: Callable[[A], bool], c: Cola[A]) -> bool:

if esVacia(c):

return True

pc = primero(c)

rc = resto(c)

return p(pc) and todosVerifican1(p, rc)

# 2ª solución

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

def todosVerifican2(p: Callable[[A], bool], c: Cola[A]) -> bool:

return all(p(x) for x in colaAlista(c))

# La función colaAlista está definida en el ejercicio

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

# https://bit.ly/3Xv0oIt

# 3ª solución

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

def todosVerifican3Aux(p: Callable[[A], bool], c: Cola[A]) -> bool:

if c.esVacia():

return True

pc = c.primero()

c.resto()

return p(pc) and todosVerifican3Aux(p, c)

def todosVerifican3(p: Callable[[A], bool], c: Cola[A]) -> bool:

_c = deepcopy(c)

return todosVerifican3Aux(p, _c)

# 4ª solución

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

def todosVerifican4Aux(p: Callable[[A], bool], c: Cola[A]) -> bool:

if c.esVacia():

return True

pc = c.primero()

c.resto()

return p(pc) and todosVerifican4Aux(p, c)

def todosVerifican4(p: Callable[[A], bool], c: Cola[A]) -> bool:

_c = deepcopy(c)

return todosVerifican4Aux(p, _c)

# 5ª solución

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

def todosVerifican5Aux(p: Callable[[A], bool], c: Cola[A]) -> bool:

while not c.esVacia():

if not p(c.primero()):

return False

c.resto()

return True

def todosVerifican5(p: Callable[[A], bool], c: Cola[A]) -> bool:

_c = deepcopy(c)

return todosVerifican5Aux(p, _c)

# Comprobación de equivalencia

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

# La propiedad es

@given(c=colaAleatoria())

def test_filtraPila(c: Cola[int]) -> None:

r = todosVerifican1(lambda x: x > 0, c)

assert todosVerifican2(lambda x: x > 0, c) == r

assert todosVerifican3(lambda x: x > 0, c) == r

assert todosVerifican4(lambda x: x > 0, c) == r

assert todosVerifican5(lambda x: x > 0, c) == r

# La comprobación es

# src> poetry run pytest -q todosVerifican.py

# 1 passed in 0.25s

TAD de las colas: Longitud de una cola

PorJosé A. Alonso 10-febrero-202324-enero-2023

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

   longitudCola :: Cola a -> Int

1	longitudCola :: Cola a -> Int

tal que longitudCola c es el número de elementos de la cola c. Por ejemplo,

   longitudCola (inserta 4 (inserta 2 (inserta 5 vacia))) == 3

1	longitudCola (inserta 4 (inserta 2 (inserta 5 vacia))) == 3

Soluciones

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

Soluciones en Haskell

import TAD.Cola (Cola, vacia, inserta, resto, esVacia)
import Transformaciones_colas_listas (colaAlista)
import Test.QuickCheck

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

longitudCola1 :: Cola a -> Int
longitudCola1 c
  | esVacia c = 0
  | otherwise = 1 + longitudCola1 rc
  where rc = resto c

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

longitudCola2 :: Cola a -> Int
longitudCola2 = length . colaAlista

-- La función colaAlista está definida en el ejercicio
-- "Transformaciones entre colas y listas" que se encuentra en
-- https://bit.ly/3Xv0oIt

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

-- La propiedad es
prop_longitudCola :: Cola Int -> Bool
prop_longitudCola c =
  longitudCola1 c == longitudCola2 c

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

import TAD.Cola (Cola, vacia, inserta, resto, esVacia)

import Transformaciones_colas_listas (colaAlista)

import Test.QuickCheck

-- 1ª solución

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

longitudCola1 :: Cola a -> Int

longitudCola1 c

| esVacia c = 0

| otherwise = 1 + longitudCola1 rc

where rc = resto c

-- 2ª solución

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

longitudCola2 :: Cola a -> Int

longitudCola2 = length . colaAlista

-- La función colaAlista está definida en el ejercicio

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

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

-- Comprobación de equivalencia

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

-- La propiedad es

prop_longitudCola :: Cola Int -> Bool

prop_longitudCola c =

longitudCola1 c == longitudCola2 c

-- La comprobación es

-- λ> quickCheck prop_longitudCola

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, resto,
                          vacia)
from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

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

def longitudCola1(c: Cola[A]) -> int:
    if esVacia(c):
        return 0
    return 1 + longitudCola1(resto(c))

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

def longitudCola2(c: Cola[A]) -> int:
    return len(colaAlista(c))

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

def longitudCola3Aux(c: Cola[A]) -> int:
    if c.esVacia():
        return 0
    c.resto()
    return 1 + longitudCola3Aux(c)

def longitudCola3(c: Cola[A]) -> int:
    _c = deepcopy(c)
    return longitudCola3Aux(_c)

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

def longitudCola4Aux(c: Cola[A]) -> int:
    r = 0
    while not esVacia(c):
        r = r + 1
        c = resto(c)
    return r

def longitudCola4(c: Cola[A]) -> int:
    _c = deepcopy(c)
    return longitudCola4Aux(_c)

# 5ª solución
# ===========

def longitudCola5Aux(c: Cola[A]) -> int:
    r = 0
    while not c.esVacia():
        r = r + 1
        c.resto()
    return r

def longitudCola5(c: Cola[A]) -> int:
    _c = deepcopy(c)
    return longitudCola5Aux(_c)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(c=colaAleatoria())
def test_longitudCola_(c: Cola[int]) -> None:
    r = longitudCola1(c)
    assert longitudCola2(c) == r
    assert longitudCola3(c) == r
    assert longitudCola4(c) == r
    assert longitudCola5(c) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, resto,

vacia)

from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

# 1ª solución

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

def longitudCola1(c: Cola[A]) -> int:

if esVacia(c):

return 0

return 1 + longitudCola1(resto(c))

# 2ª solución

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

def longitudCola2(c: Cola[A]) -> int:

return len(colaAlista(c))

# 3ª solución

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

def longitudCola3Aux(c: Cola[A]) -> int:

if c.esVacia():

return 0

c.resto()

return 1 + longitudCola3Aux(c)

def longitudCola3(c: Cola[A]) -> int:

_c = deepcopy(c)

return longitudCola3Aux(_c)

# 4ª solución

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

def longitudCola4Aux(c: Cola[A]) -> int:

r = 0

while not esVacia(c):

r = r + 1

c = resto(c)

return r

def longitudCola4(c: Cola[A]) -> int:

_c = deepcopy(c)

return longitudCola4Aux(_c)

# 5ª solución

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

def longitudCola5Aux(c: Cola[A]) -> int:

r = 0

while not c.esVacia():

r = r + 1

c.resto()

return r

def longitudCola5(c: Cola[A]) -> int:

_c = deepcopy(c)

return longitudCola5Aux(_c)

# Comprobación de equivalencia

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

# La propiedad es

@given(c=colaAleatoria())

def test_longitudCola_(c: Cola[int]) -> None:

r = longitudCola1(c)

assert longitudCola2(c) == r

assert longitudCola3(c) == r

assert longitudCola4(c) == r

assert longitudCola5(c) == r

# La comprobación es

# src> poetry run pytest -q longitudCola.py

# 1 passed in 0.28s

TAD de las colas: Último elemento

PorJosé A. Alonso 9-febrero-202324-enero-2023

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

   ultimoCola :: Cola a -> a

1	ultimoCola :: Cola a -> a

tal que ultimoCola c es el último elemento de la cola c. Por ejemplo,

   ultimoCola (inserta 3 (inserta 5 (inserta 2 vacia))) == 3
   ultimoCola (inserta 2 vacia)                         == 2

1 2	ultimoCola (inserta 3 (inserta 5 (inserta 2 vacia))) == 3 ultimoCola (inserta 2 vacia) == 2

Soluciones

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

Soluciones en Haskell

import TAD.Cola (Cola, vacia, inserta, primero, resto, esVacia)
import Transformaciones_colas_listas (colaAlista)
import Test.QuickCheck

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

ultimoCola :: Cola a -> a
ultimoCola c
  | esVacia c  = error "cola vacia"
  | esVacia rc = pc
  | otherwise  = ultimoCola rc
  where pc = primero c
        rc = resto c

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

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

ultimoCola2 :: Cola a -> a
ultimoCola2 c
  | esVacia c  = error "cola vacia"
  | otherwise  = last (colaAlista c)

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

-- La propiedad es
prop_ultimoCola :: Cola Int -> Property
prop_ultimoCola c =
  not (esVacia c) ==> ultimoCola c == ultimoCola2 c

-- La comprobación es
--    λ> quickCheck prop_ultimoCola
--    +++ OK, passed 100 tests; 16 discarded.

import TAD.Cola (Cola, vacia, inserta, primero, resto, esVacia)

import Transformaciones_colas_listas (colaAlista)

import Test.QuickCheck

-- 1ª solución

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

ultimoCola :: Cola a -> a

ultimoCola c

| esVacia c = error "cola vacia"

| esVacia rc = pc

| otherwise = ultimoCola rc

where pc = primero c

rc = resto c

-- 2ª solución

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

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

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

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

ultimoCola2 :: Cola a -> a

ultimoCola2 c

| esVacia c = error "cola vacia"

| otherwise = last (colaAlista c)

-- Comprobación de equivalencia

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

-- La propiedad es

prop_ultimoCola :: Cola Int -> Property

prop_ultimoCola c =

not (esVacia c) ==> ultimoCola c == ultimoCola2 c

-- La comprobación es

-- λ> quickCheck prop_ultimoCola

-- +++ OK, passed 100 tests; 16 discarded.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import assume, given

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,
                          resto, vacia)
from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

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

def ultimoCola(c: Cola[A]) -> A:
    if esVacia(c):
        raise ValueError("cola vacia")
    pc = primero(c)
    rc = resto(c)
    if esVacia(rc):
        return pc
    return ultimoCola(rc)

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

def ultimoCola2Aux(c: Cola[A]) -> A:
    if c.esVacia():
        raise ValueError("cola vacia")
    pc = primero(c)
    c.resto()
    if c.esVacia():
        return pc
    return ultimoCola2(c)

def ultimoCola2(c: Cola[A]) -> A:
    _c = deepcopy(c)
    return ultimoCola2Aux(_c)

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

def ultimoCola3(c: Cola[A]) -> A:
    if esVacia(c):
        raise ValueError("cola vacia")
    while not esVacia(resto(c)):
        c = resto(c)
    return primero(c)

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

def ultimoCola4Aux(c: Cola[A]) -> A:
    if c.esVacia():
        raise ValueError("cola vacia")
    r = primero(c)
    while not c.esVacia():
        c.resto()
        if not c.esVacia():
            r = primero(c)
    return r

def ultimoCola4(c: Cola[A]) -> A:
    _c = deepcopy(c)
    return ultimoCola4Aux(_c)

# 5ª solución
# ===========

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

def ultimoCola5(c: Cola[A]) -> A:
    if esVacia(c):
        raise ValueError("cola vacia")
    return colaAlista(c)[-1]

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(c=colaAleatoria())
def test_ultimoCola(c: Cola[int]) -> None:
    assume(not esVacia(c))
    r = ultimoCola(c)
    assert ultimoCola2(c) == r
    assert ultimoCola3(c) == r
    assert ultimoCola4(c) == r
    assert ultimoCola5(c) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import assume, given

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,

resto, vacia)

from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

# 1ª solución

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

def ultimoCola(c: Cola[A]) -> A:

if esVacia(c):

raise ValueError("cola vacia")

pc = primero(c)

rc = resto(c)

if esVacia(rc):

return pc

return ultimoCola(rc)

# 2ª solución

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

def ultimoCola2Aux(c: Cola[A]) -> A:

if c.esVacia():

raise ValueError("cola vacia")

pc = primero(c)

c.resto()

if c.esVacia():

return pc

return ultimoCola2(c)

def ultimoCola2(c: Cola[A]) -> A:

_c = deepcopy(c)

return ultimoCola2Aux(_c)

# 3ª solución

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

def ultimoCola3(c: Cola[A]) -> A:

if esVacia(c):

raise ValueError("cola vacia")

while not esVacia(resto(c)):

c = resto(c)

return primero(c)

# 4ª solución

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

def ultimoCola4Aux(c: Cola[A]) -> A:

if c.esVacia():

raise ValueError("cola vacia")

r = primero(c)

while not c.esVacia():

c.resto()

if not c.esVacia():

r = primero(c)

return r

def ultimoCola4(c: Cola[A]) -> A:

_c = deepcopy(c)

return ultimoCola4Aux(_c)

# 5ª solución

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

# Se usarán la función colaAlista del ejercicio

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

# https://bit.ly/3Xv0oIt

def ultimoCola5(c: Cola[A]) -> A:

if esVacia(c):

raise ValueError("cola vacia")

return colaAlista(c)[-1]

# Comprobación de equivalencia

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

# La propiedad es

@given(c=colaAleatoria())

def test_ultimoCola(c: Cola[int]) -> None:

assume(not esVacia(c))

r = ultimoCola(c)

assert ultimoCola2(c) == r

assert ultimoCola3(c) == r

assert ultimoCola4(c) == r

assert ultimoCola5(c) == r

# La comprobación es

# src> poetry run pytest -q ultimoCola.py

# 1 passed in 0.25s

TAD de las colas: Transformaciones entre colas y listas

PorJosé A. Alonso 8-febrero-202323-enero-2023

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

   listaAcola :: [a] -> Cola a
   colaAlista :: Cola a -> [a]

1 2	listaAcola :: [a] -> Cola a colaAlista :: Cola a -> [a]

tales que

listaAcola xs es la cola formada por los elementos de xs. Por ejemplo,

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

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

colaAlista c es la lista formada por los elementos de la cola c. Por ejemplo,

     λ> colaAlista (inserta 5 (inserta 2 (inserta 3 vacia)))
     [3, 2, 5]

1 2	λ> colaAlista (inserta 5 (inserta 2 (inserta 3 vacia))) [3, 2, 5]

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

   colaAlista (listaAcola xs) = xs
   listaAcola (colaAlista c)  = c

1 2	colaAlista (listaAcola xs) = xs listaAcola (colaAlista c) = c

Soluciones

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

Soluciones en Haskell

import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)
import Test.QuickCheck

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

listaAcola :: [a] -> Cola a
listaAcola ys = aux (reverse ys)
  where aux []     = vacia
        aux (x:xs) = inserta x (aux xs)

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

listaAcola2 :: [a] -> Cola a
listaAcola2 = aux . reverse
  where aux [] = vacia
        aux (x:xs) = inserta x (aux xs)

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

listaAcola3 :: [a] -> Cola a
listaAcola3 = aux . reverse
  where aux = foldr inserta vacia

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

listaAcola4 :: [a] -> Cola a
listaAcola4 xs = foldr inserta vacia (reverse xs)

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

listaAcola5 :: [a] -> Cola a
listaAcola5 = foldr inserta vacia . reverse

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

-- La propiedad es
prop_listaAcola :: [Int] -> Bool
prop_listaAcola xs =
  all (== listaAcola xs)
      [listaAcola2 xs,
       listaAcola3 xs,
       listaAcola4 xs,
       listaAcola5 xs]

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

-- Definición de colaAlista
-- ========================

colaAlista :: Cola a -> [a]
colaAlista c
  | esVacia c = []
  | otherwise = pc : colaAlista rc
  where pc = primero c
        rc = resto c

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

-- La primera propiedad es
prop_1_listaAcola :: [Int] -> Bool
prop_1_listaAcola xs =
  colaAlista (listaAcola xs) == xs

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

-- La segunda propiedad es
prop_2_listaAcola :: Cola Int -> Bool
prop_2_listaAcola c =
  listaAcola (colaAlista c) == c

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

import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)

import Test.QuickCheck

-- 1ª definición de listaAcola

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

listaAcola :: [a] -> Cola a

listaAcola ys = aux (reverse ys)

where aux [] = vacia

aux (x:xs) = inserta x (aux xs)

-- 2ª definición de listaAcola

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

listaAcola2 :: [a] -> Cola a

listaAcola2 = aux . reverse

where aux [] = vacia

aux (x:xs) = inserta x (aux xs)

-- 3ª definición de listaAcola

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

listaAcola3 :: [a] -> Cola a

listaAcola3 = aux . reverse

where aux = foldr inserta vacia

-- 4ª definición de listaAcola

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

listaAcola4 :: [a] -> Cola a

listaAcola4 xs = foldr inserta vacia (reverse xs)

-- 5ª definición de listaAcola

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

listaAcola5 :: [a] -> Cola a

listaAcola5 = foldr inserta vacia . reverse

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

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

-- La propiedad es

prop_listaAcola :: [Int] -> Bool

prop_listaAcola xs =

all (== listaAcola xs)

[listaAcola2 xs,

listaAcola3 xs,

listaAcola4 xs,

listaAcola5 xs]

-- La comprobación es

-- λ> quickCheck prop_listaAcola

-- +++ OK, passed 100 tests.

-- Definición de colaAlista

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

colaAlista :: Cola a -> [a]

colaAlista c

| esVacia c = []

| otherwise = pc : colaAlista rc

where pc = primero c

rc = resto c

-- Comprobación de las propiedades

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

-- La primera propiedad es

prop_1_listaAcola :: [Int] -> Bool

prop_1_listaAcola xs =

colaAlista (listaAcola xs) == xs

-- La comprobación es

-- λ> quickCheck prop_1_listaAcola

-- +++ OK, passed 100 tests.

-- La segunda propiedad es

prop_2_listaAcola :: Cola Int -> Bool

prop_2_listaAcola c =

listaAcola (colaAlista c) == c

-- La comprobación es

-- λ> quickCheck prop_2_listaAcola

-- +++ 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.cola import (Cola, inserta, primero, resto, esVacia, vacia,
                          colaAleatoria)

A = TypeVar('A')

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

def listaAcola(ys: list[A]) -> Cola[A]:
    def aux(xs: list[A]) -> Cola[A]:
        if not xs:
            return vacia()
        return inserta(xs[0], aux(xs[1:]))

    return aux(list(reversed(ys)))

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

def listaAcola2(xs: list[A]) -> Cola[A]:
    p: Cola[A] = Cola()
    for x in xs:
        p.inserta(x)
    return p

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

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

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

def colaAlista(c: Cola[A]) -> list[A]:
    if esVacia(c):
        return []
    pc = primero(c)
    rc = resto(c)
    return [pc] + colaAlista(rc)

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

def colaAlista2Aux(c: Cola[A]) -> list[A]:
    if c.esVacia():
        return []
    pc = c.primero()
    c.resto()
    return [pc] + colaAlista2Aux(c)

def colaAlista2(c: Cola[A]) -> list[A]:
    c1 = deepcopy(c)
    return colaAlista2Aux(c1)

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

def colaAlista3Aux(c: Cola[A]) -> list[A]:
    r = []
    while not c.esVacia():
        r.append(c.primero())
        c.resto()
    return r

def colaAlista3(c: Cola[A]) -> list[A]:
    c1 = deepcopy(c)
    return colaAlista3Aux(c1)

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

@given(p=colaAleatoria())
def test_colaAlista(p: Cola[int]) -> None:
    assert colaAlista(p) == colaAlista2(p)
    assert colaAlista(p) == colaAlista3(p)

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

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

# La segunda propiedad es
@given(c=colaAleatoria())
def test_2_listaAcola(c: Cola[int]) -> None:
    assert listaAcola(colaAlista(c)) == c

# La comprobación es
#      src> poetry run pytest -v transformaciones_colas_listas.py
#      test_listaAcola PASSED
#      test_colaAlista PASSED
#      test_1_listaAcola PASSED
#      test_2_listaAcola 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.cola import (Cola, inserta, primero, resto, esVacia, vacia,

colaAleatoria)

A = TypeVar('A')

# 1ª definición de listaAcola

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

def listaAcola(ys: list[A]) -> Cola[A]:

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

if not xs:

return vacia()

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

return aux(list(reversed(ys)))

# 2ª solución de listaAcola

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

def listaAcola2(xs: list[A]) -> Cola[A]:

p: Cola[A] = Cola()

for x in xs:

p.inserta(x)

return p

# Comprobación de equivalencia de las definiciones de listaAcola

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

# La propiedad es

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

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

assert listaAcola(xs) == listaAcola2(xs)

# 1ª definición de colaAlista

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

def colaAlista(c: Cola[A]) -> list[A]:

if esVacia(c):

return []

pc = primero(c)

rc = resto(c)

return [pc] + colaAlista(rc)

# 2ª definición de colaAlista

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

def colaAlista2Aux(c: Cola[A]) -> list[A]:

if c.esVacia():

return []

pc = c.primero()

c.resto()

return [pc] + colaAlista2Aux(c)

def colaAlista2(c: Cola[A]) -> list[A]:

c1 = deepcopy(c)

return colaAlista2Aux(c1)

# 3ª definición de colaAlista

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

def colaAlista3Aux(c: Cola[A]) -> list[A]:

r = []

while not c.esVacia():

r.append(c.primero())

c.resto()

return r

def colaAlista3(c: Cola[A]) -> list[A]:

c1 = deepcopy(c)

return colaAlista3Aux(c1)

# Comprobación de equivalencia de las definiciones de colaAlista

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

@given(p=colaAleatoria())

def test_colaAlista(p: Cola[int]) -> None:

assert colaAlista(p) == colaAlista2(p)

assert colaAlista(p) == colaAlista3(p)

# Comprobación de las propiedades

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

# La primera propiedad es

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

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

assert colaAlista(listaAcola(xs)) == xs

# La segunda propiedad es

@given(c=colaAleatoria())

def test_2_listaAcola(c: Cola[int]) -> None:

assert listaAcola(colaAlista(c)) == c

# La comprobación es

# src> poetry run pytest -v transformaciones_colas_listas.py

# test_listaAcola PASSED

# test_colaAlista PASSED

# test_1_listaAcola PASSED

# test_2_listaAcola PASSED

El tipo abstracto de datos de las colas

PorJosé A. Alonso 7-febrero-202330-enero-2023

1. El tipo abstracto de datos de las colas

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción se realiza por un extremo (el posterior o final) y la operación de extracción por el otro (el anterior o frente).

Las operaciones que definen a tipo abstracto de datos (TAD) de las colas (cuyos elementos son del tipo a) son las siguientes:

   vacia   :: Cola a
   inserta :: a -> Cola a -> Cola a
   primero :: Cola a -> a
   resto   :: Cola a -> Cola a
   esVacia :: Cola a -> Bool

vacia :: Cola a

inserta :: a -> Cola a -> Cola a

primero :: Cola a -> a

resto :: Cola a -> Cola a

esVacia :: Cola a -> Bool

tales que

vacia es la cola vacía.
(inserta x c) es la cola obtenida añadiendo x al final de c.
(primero c) es el primero de la cola c.
(resto c) es la cola obtenida eliminando el primero de c.
(esVacia c) se verifica si c es la cola vacía.

Las operaciones tienen que verificar las siguientes propiedades:

primero (inserta x vacia) == x
Si c es una cola no vacía, entonces primero (inserta x c) == primero c,
resto (inserta x vacia) == vacia
Si c es una cola no vacía, entonces resto (inserta x c) == inserta x (resto c)
esVacia vacia
not (esVacia (inserta x c))

2. Las colas en Haskell

2.1. El tipo abstracto de datos de las colas en Haskell

El TAD de las colas se encuentra en el módulo Cola.hs cuyo contenido es el siguiente:

module TAD.Cola
  (Cola,
   vacia,      -- Cola a
   inserta,    -- a -> Cola a -> Cola a
   primero,    -- Cola a -> a
   resto,      -- Cola a -> Cola a
   esVacia,    -- Cola a -> Bool
  ) where

import TAD.ColaConListas
-- import TAD.ColaConDosListas
-- import TAD.ColaConSucesiones

module TAD.Cola

(Cola,

vacia, -- Cola a

inserta, -- a -> Cola a -> Cola a

primero, -- Cola a -> a

resto, -- Cola a -> Cola a

esVacia, -- Cola a -> Bool

) where

import TAD.ColaConListas

-- import TAD.ColaConDosListas

-- import TAD.ColaConSucesiones

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos tres: una usando listas, otra usando pares de listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

2.2. Implementación de las colas mediante listas

La implementación se encuentra en el módulo ColaConListas.hs cuyo contenido es el siguiente:

{-# LANGUAGE FlexibleInstances #-}
{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.ColaConListas
  (Cola,
   vacia,   -- Cola a
   inserta, -- a -> Cola a -> Cola a
   primero, -- Cola a -> a
   resto,   -- Cola a -> Cola a
   esVacia, -- Cola a -> Bool
  ) where

import Test.QuickCheck

-- Colas como listas:
newtype Cola a = C [a]
  deriving Eq

-- (escribeCola c) es la cadena correspondiente a la cola c. Por
-- ejemplo,
--    escribeCola (inserta 5 (inserta 2 (inserta 3 vacia))) == "3 | 2 | 5"
escribeCola :: Show a => Cola a -> String
escribeCola (C [])     = "-"
escribeCola (C [x])    = show x
escribeCola (C (x:xs)) = show x ++ " | " ++ escribeCola (C xs)

-- Procedimiento de escritura de colas.
instance Show a => Show (Cola a) where
  show = escribeCola

-- Ejemplo de cola:
--    λ> inserta 5 (inserta 2 (inserta 3 vacia))
--    3 | 2 | 5

-- vacia es la cola vacía. Por ejemplo,
--    λ> vacia
--    -
vacia :: Cola a
vacia = C []

-- (inserta x c) es la cola obtenida añadiendo x al final de la cola
-- c. Por ejemplo,
--    λ> ej = inserta 2 (inserta 3 vacia)
--    λ> ej
--    3 | 2
--    λ> inserta 5 ej
--    3 | 2 | 5
inserta :: a -> Cola a -> Cola a
inserta x (C c) = C (c ++ [x])

-- (primero c) es el primer elemento de la cola c. Por ejemplo,
--    λ> primero (inserta 5 (inserta 2 (inserta 3 vacia)))
--    3
primero :: Cola a -> a
primero (C [])    = error "primero: cola vacia"
primero (C (x:_)) = x

-- (resto c) es la cola obtenida eliminando el primer elemento de la
-- cola c. Por ejemplo,
--    λ> resto (inserta 5 (inserta 2 (inserta 3 vacia)))
--    2 | 5
resto :: Cola a -> Cola a
resto (C (_:xs)) = C xs
resto (C [])     = error "resto: cola vacia"

-- (esVacia c) se verifica si c es la cola vacía. Por ejemplo,
--    esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False
--    esVacia vacia  == True
esVacia :: Cola a -> Bool
esVacia (C xs)  = null xs

-- Generador de colas                                          --
-- ==================

-- genCola es un generador de colas de enteros. Por ejemplo,
--    λ> sample genCola
--    -
--    -
--    -3 | 2
--    6 | 0 | 1
--    -5 | 0 | -5 | 0 | -4
--    2 | 9 | -6 | 9 | 0 | -1
--    -
--    11 | -5 | 5
--    -
--    16 | 6 | 15 | -3 | -9
--    11 | 6 | 15 | 13 | 20 | -7 | 11 | -5 | 13
genCola :: (Arbitrary a, Num a) => Gen (Cola a)
genCola = do
  xs <- listOf arbitrary
  return (foldr inserta vacia xs)

-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Cola a) where
  arbitrary = genCola

-- Propiedades de las colas
-- ========================

-- Las propiedades son
prop_colas1 :: Int -> Cola Int -> Bool
prop_colas1 x c =
  primero (inserta x vacia) == x &&
  resto (inserta x vacia) == vacia &&
  esVacia vacia &&
  not (esVacia (inserta x c))

prop_colas2 :: Int -> Cola Int -> Property
prop_colas2 x c =
  not (esVacia c) ==>
  primero (inserta x c) == primero c &&
  resto (inserta x c) == inserta x (resto c)

-- La comprobación es:
--    λ> quickCheck prop_colas1
--    +++ OK, passed 100 tests.
--    λ> quickCheck prop_colas2
--    +++ OK, passed 100 tests; 3 discarded.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

{-# LANGUAGE FlexibleInstances #-}

{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.ColaConListas

(Cola,

vacia, -- Cola a

inserta, -- a -> Cola a -> Cola a

primero, -- Cola a -> a

resto, -- Cola a -> Cola a

esVacia, -- Cola a -> Bool

) where

import Test.QuickCheck

-- Colas como listas:

newtype Cola a = C [a]

deriving Eq

-- (escribeCola c) es la cadena correspondiente a la cola c. Por

-- ejemplo,

-- escribeCola (inserta 5 (inserta 2 (inserta 3 vacia))) == "3 | 2 | 5"

escribeCola :: Show a => Cola a -> String

escribeCola (C []) = "-"

escribeCola (C [x]) = show x

escribeCola (C (x:xs)) = show x ++ " | " ++ escribeCola (C xs)

-- Procedimiento de escritura de colas.

instance Show a => Show (Cola a) where

show = escribeCola

-- Ejemplo de cola:

-- λ> inserta 5 (inserta 2 (inserta 3 vacia))

-- 3 | 2 | 5

-- vacia es la cola vacía. Por ejemplo,

-- λ> vacia

-- -

vacia :: Cola a

vacia = C []

-- (inserta x c) es la cola obtenida añadiendo x al final de la cola

-- c. Por ejemplo,

-- λ> ej = inserta 2 (inserta 3 vacia)

-- λ> ej

-- 3 | 2

-- λ> inserta 5 ej

-- 3 | 2 | 5

inserta :: a -> Cola a -> Cola a

inserta x (C c) = C (c ++ [x])

-- (primero c) es el primer elemento de la cola c. Por ejemplo,

-- λ> primero (inserta 5 (inserta 2 (inserta 3 vacia)))

-- 3

primero :: Cola a -> a

primero (C []) = error "primero: cola vacia"

primero (C (x:_)) = x

-- (resto c) es la cola obtenida eliminando el primer elemento de la

-- cola c. Por ejemplo,

-- λ> resto (inserta 5 (inserta 2 (inserta 3 vacia)))

-- 2 | 5

resto :: Cola a -> Cola a

resto (C (_:xs)) = C xs

resto (C []) = error "resto: cola vacia"

-- (esVacia c) se verifica si c es la cola vacía. Por ejemplo,

-- esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False

-- esVacia vacia == True

esVacia :: Cola a -> Bool

esVacia (C xs) = null xs

-- Generador de colas --

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

-- genCola es un generador de colas de enteros. Por ejemplo,

-- λ> sample genCola

-- -

-- -3 | 2

-- 6 | 0 | 1

-- -5 | 0 | -5 | 0 | -4

-- 2 | 9 | -6 | 9 | 0 | -1

-- -

-- 11 | -5 | 5

-- -

-- 16 | 6 | 15 | -3 | -9

-- 11 | 6 | 15 | 13 | 20 | -7 | 11 | -5 | 13

genCola :: (Arbitrary a, Num a) => Gen (Cola a)

genCola = do

xs <- listOf arbitrary

return (foldr inserta vacia xs)

-- El tipo pila es una instancia del arbitrario.

instance (Arbitrary a, Num a) => Arbitrary (Cola a) where

arbitrary = genCola

-- Propiedades de las colas

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

-- Las propiedades son

prop_colas1 :: Int -> Cola Int -> Bool

prop_colas1 x c =

primero (inserta x vacia) == x &&

resto (inserta x vacia) == vacia &&

esVacia vacia &&

not (esVacia (inserta x c))

prop_colas2 :: Int -> Cola Int -> Property

prop_colas2 x c =

not (esVacia c) ==>

primero (inserta x c) == primero c &&

resto (inserta x c) == inserta x (resto c)

-- La comprobación es:

-- λ> quickCheck prop_colas1

-- +++ OK, passed 100 tests.

-- λ> quickCheck prop_colas2

-- +++ OK, passed 100 tests; 3 discarded.

2.3. Implementación de las colas mediante pares de listas

En esta implementación, una cola c se representa mediante un par de listas (xs,ys) de modo que los elementos de c son, en ese orden, los elementos de la lista xs++(reverse ys).

Al dividir la lista en dos parte e invertir la segunda de ellas, esperamos hacer más eficiente las operaciones sobre las colas.

Impondremos también una restricción adicional sobre la representación: las colas serán representadas mediante pares (xs,ys) tales que si xs es vacía, entonces ys será también vacía. Esta restricción ha de ser conservada por los programas que crean colas.

La implementación se encuentra en el módulo ColaConDosListas.hs cuyo contenido es el siguiente:

module TAD.ColaConDosListas
  (Cola,
   vacia,      -- Cola a
   inserta,    -- a -> Cola a -> Cola a
   primero,    -- Cola a -> a
   resto,      -- Cola a -> Cola a
   esVacia,    -- Cola a -> Bool
  ) where

import Test.QuickCheck

-- Las colas como pares listas.
newtype Cola a = C ([a],[a])

-- (escribeCola p) es la cadena correspondiente a la cola p. Por
-- ejemplo,
--    λ> escribeCola (inserta 5 (inserta 2 (inserta 3 vacia)))
--    "3 | 2 | 5"
escribeCola :: Show a => Cola a -> String
escribeCola (C (xs,ys)) = aux (xs ++ reverse ys)
  where aux []     = "-"
        aux [z]    = show z
        aux (z:zs) = show z ++ " | " ++ aux zs

-- Procedimiento de escritura de colas.
instance Show a => Show (Cola a) where
  show = escribeCola

-- Ejemplo de cola:
--    λ> inserta 5 (inserta 2 (inserta 3 vacia))
--    3 | 2 | 5

-- vacia es la cola vacía. Por ejemplo,
--    λ>  vacia
--    -
vacia :: Cola a
vacia  = C ([],[])

-- (inserta x c) es la cola obtenida añadiendo x al final de la cola
-- c. Por ejemplo,
--    λ> inserta 5 (inserta 2 (inserta 3 vacia))
--    3 | 2 | 5
inserta :: a -> Cola a -> Cola a
inserta y (C (xs,ys)) = C (normaliza (xs,y:ys))

-- (normaliza p) es la cola obtenida al normalizar el par de listas
-- p. Por ejemplo,
--    normaliza ([],[2,5,3])   ==  ([3,5,2],[])
--    normaliza ([4],[2,5,3])  ==  ([4],[2,5,3])
normaliza :: ([a],[a]) -> ([a],[a])
normaliza ([], ys) = (reverse ys, [])
normaliza p        = p

-- (primero c) es el primer elemento de la cola c. Por ejemplo,
--    λ> primero (inserta 5 (inserta 2 (inserta 3 vacia)))
--    3
primero  :: Cola a -> a
primero (C (x:_,_)) = x
primero _           = error "primero: cola vacia"

-- (resto c) es la cola obtenida eliminando el primer elemento de la
-- cola c. Por ejemplo,
--    λ> resto (inserta 5 (inserta 2 (inserta 3 vacia)))
--    2 | 5
resto  :: Cola a -> Cola a
resto (C ([],[]))   = error "resto: cola vacia"
resto (C (_:xs,ys)) = C (normaliza (xs,ys))
resto (C ([],_:_))  = error "Imposible"

-- (esVacia c) se verifica si c es la cola vacía. Por ejemplo,
--    esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False
--    esVacia vacia == True
esVacia :: Cola a -> Bool
esVacia (C (xs,_)) = null xs

-- (valida c) se verifica si la cola c es válida; es decir, si
-- su primer elemento es vacío entonces también lo es el segundo. Por
-- ejemplo,
--    valida (C ([2],[5]))  ==  True
--    valida (C ([2],[]))   ==  True
--    valida (C ([],[5]))   ==  False
valida :: Cola a -> Bool
valida (C (xs,ys)) = not (null xs) || null ys

-- ---------------------------------------------------------------------
-- Igualdad de colas                                                  --
-- ---------------------------------------------------------------------

-- (elementos c) es la lista de los elementos de la cola c en el orden de
-- la cola. Por ejemplo,
--    λ> elementos (inserta 5 (inserta 2 (inserta 3 vacia)))
--    [3,2,5]
elementos :: Cola a -> [a]
elementos (C (xs,ys)) = xs ++ reverse ys

-- (igualColas c1 c2) se verifica si las colas c1 y c2 son iguales. Por
-- ejemplo,
--    igualColas (C ([3,2],[5,4,7])) (C ([3],[5,4,7,2]))   ==  True
--    igualColas (C ([3,2],[5,4,7])) (C ([],[5,4,7,2,3]))  ==  False
igualColas :: Eq a => Cola a -> Cola a -> Bool
igualColas c1 c2 =
  valida c1 &&
  valida c2 &&
  elementos c1 == elementos c2

instance Eq a => Eq (Cola a) where
  (==) = igualColas

-- Generador de colas                                          --
-- ==================

-- genCola es un generador de colas de enteros. Por ejemplo,
--    λ> sample genCola
--    -
--    -
--    -3 | 2
--    6 | 0 | 1
--    -5 | 0 | -5 | 0 | -4
--    2 | 9 | -6 | 9 | 0 | -1
--    -
--    11 | -5 | 5
--    -
--    16 | 6 | 15 | -3 | -9
--    11 | 6 | 15 | 13 | 20 | -7 | 11 | -5 | 13
genCola :: (Arbitrary a, Num a) => Gen (Cola a)
genCola = do
  xs <- listOf arbitrary
  return (foldr inserta vacia xs)

-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Cola a) where
  arbitrary = genCola

-- Propiedades de las colas
-- ========================

-- Las propiedades son
prop_colas1 :: Int -> Cola Int -> Bool
prop_colas1 x c =
  primero (inserta x vacia) == x &&
  resto (inserta x vacia) == vacia &&
  esVacia vacia &&
  not (esVacia (inserta x c))

prop_colas2 :: Int -> Cola Int -> Property
prop_colas2 x c =
  not (esVacia c) ==>
  primero (inserta x c) == primero c &&
  resto (inserta x c) == inserta x (resto c)

-- La comprobación es:
--    λ> quickCheck prop_colas1
--    +++ OK, passed 100 tests.
--    λ> quickCheck prop_colas2
--    +++ OK, passed 100 tests; 3 discarded.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

module TAD.ColaConDosListas

(Cola,

vacia, -- Cola a

inserta, -- a -> Cola a -> Cola a

primero, -- Cola a -> a

resto, -- Cola a -> Cola a

esVacia, -- Cola a -> Bool

) where

import Test.QuickCheck

-- Las colas como pares listas.

newtype Cola a = C ([a],[a])

-- (escribeCola p) es la cadena correspondiente a la cola p. Por

-- ejemplo,

-- λ> escribeCola (inserta 5 (inserta 2 (inserta 3 vacia)))

-- "3 | 2 | 5"

escribeCola :: Show a => Cola a -> String

escribeCola (C (xs,ys)) = aux (xs ++ reverse ys)

where aux [] = "-"

aux [z] = show z

aux (z:zs) = show z ++ " | " ++ aux zs

-- Procedimiento de escritura de colas.

instance Show a => Show (Cola a) where

show = escribeCola

-- Ejemplo de cola:

-- λ> inserta 5 (inserta 2 (inserta 3 vacia))

-- 3 | 2 | 5

-- vacia es la cola vacía. Por ejemplo,

-- λ> vacia

-- -

vacia :: Cola a

vacia = C ([],[])

-- (inserta x c) es la cola obtenida añadiendo x al final de la cola

-- c. Por ejemplo,

-- λ> inserta 5 (inserta 2 (inserta 3 vacia))

-- 3 | 2 | 5

inserta :: a -> Cola a -> Cola a

inserta y (C (xs,ys)) = C (normaliza (xs,y:ys))

-- (normaliza p) es la cola obtenida al normalizar el par de listas

-- p. Por ejemplo,

-- normaliza ([],[2,5,3]) == ([3,5,2],[])

-- normaliza ([4],[2,5,3]) == ([4],[2,5,3])

normaliza :: ([a],[a]) -> ([a],[a])

normaliza ([], ys) = (reverse ys, [])

normaliza p = p

-- (primero c) es el primer elemento de la cola c. Por ejemplo,

-- λ> primero (inserta 5 (inserta 2 (inserta 3 vacia)))

-- 3

primero :: Cola a -> a

primero (C (x:_,_)) = x

primero _ = error "primero: cola vacia"

-- (resto c) es la cola obtenida eliminando el primer elemento de la

-- cola c. Por ejemplo,

-- λ> resto (inserta 5 (inserta 2 (inserta 3 vacia)))

-- 2 | 5

resto :: Cola a -> Cola a

resto (C ([],[])) = error "resto: cola vacia"

resto (C (_:xs,ys)) = C (normaliza (xs,ys))

resto (C ([],_:_)) = error "Imposible"

-- (esVacia c) se verifica si c es la cola vacía. Por ejemplo,

-- esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False

-- esVacia vacia == True

esVacia :: Cola a -> Bool

esVacia (C (xs,_)) = null xs

-- (valida c) se verifica si la cola c es válida; es decir, si

-- su primer elemento es vacío entonces también lo es el segundo. Por

-- ejemplo,

-- valida (C ([2],[5])) == True

-- valida (C ([2],[])) == True

-- valida (C ([],[5])) == False

valida :: Cola a -> Bool

valida (C (xs,ys)) = not (null xs) || null ys

-- ---------------------------------------------------------------------

-- Igualdad de colas --

-- ---------------------------------------------------------------------

-- (elementos c) es la lista de los elementos de la cola c en el orden de

-- la cola. Por ejemplo,

-- λ> elementos (inserta 5 (inserta 2 (inserta 3 vacia)))

-- [3,2,5]

elementos :: Cola a -> [a]

elementos (C (xs,ys)) = xs ++ reverse ys

-- (igualColas c1 c2) se verifica si las colas c1 y c2 son iguales. Por

-- ejemplo,

-- igualColas (C ([3,2],[5,4,7])) (C ([3],[5,4,7,2])) == True

-- igualColas (C ([3,2],[5,4,7])) (C ([],[5,4,7,2,3])) == False

igualColas :: Eq a => Cola a -> Cola a -> Bool

igualColas c1 c2 =

valida c1 &&

valida c2 &&

elementos c1 == elementos c2

instance Eq a => Eq (Cola a) where

(==) = igualColas

-- Generador de colas --

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

-- genCola es un generador de colas de enteros. Por ejemplo,

-- λ> sample genCola

-- -

-- -3 | 2

-- 6 | 0 | 1

-- -5 | 0 | -5 | 0 | -4

-- 2 | 9 | -6 | 9 | 0 | -1

-- -

-- 11 | -5 | 5

-- -

-- 16 | 6 | 15 | -3 | -9

-- 11 | 6 | 15 | 13 | 20 | -7 | 11 | -5 | 13

genCola :: (Arbitrary a, Num a) => Gen (Cola a)

genCola = do

xs <- listOf arbitrary

return (foldr inserta vacia xs)

-- El tipo pila es una instancia del arbitrario.

instance (Arbitrary a, Num a) => Arbitrary (Cola a) where

arbitrary = genCola

-- Propiedades de las colas

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

-- Las propiedades son

prop_colas1 :: Int -> Cola Int -> Bool

prop_colas1 x c =

primero (inserta x vacia) == x &&

resto (inserta x vacia) == vacia &&

esVacia vacia &&

not (esVacia (inserta x c))

prop_colas2 :: Int -> Cola Int -> Property

prop_colas2 x c =

not (esVacia c) ==>

primero (inserta x c) == primero c &&

resto (inserta x c) == inserta x (resto c)

-- La comprobación es:

-- λ> quickCheck prop_colas1

-- +++ OK, passed 100 tests.

-- λ> quickCheck prop_colas2

-- +++ OK, passed 100 tests; 3 discarded.

2.4. Implementación de las colas mediante sucesiones

La implementación (que usa la librería Data.Sequence) se encuentra en el módulo ColaConSucesiones.hs cuyo contenido es el siguiente:

{-# LANGUAGE FlexibleInstances #-}
{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.ColaConSucesiones
  (Cola,
   vacia,   -- Cola a
   inserta, -- a -> Cola a -> Cola a
   primero, -- Cola a -> a
   resto,   -- Cola a -> Cola a
   esVacia, -- Cola a -> Bool
  ) where

import Data.Sequence as S
import Test.QuickCheck

-- Colas como sucesiones:
newtype Cola a = C (Seq a)
  deriving Eq

-- (escribeCola c) es la cadena correspondiente a la cola c. Por
-- ejemplo,
--    escribeCola (inserta 5 (inserta 2 (inserta 3 vacia))) == "3 | 2 | 5"
escribeCola :: Show a => Cola a -> String
escribeCola (C xs) = case viewl xs of
    EmptyL   -> "-"
    x :< xs' -> case viewl xs' of
        EmptyL -> show x
        _      -> show x ++ " | " ++ escribeCola (C xs')

-- Procedimiento de escritura de colas.
instance Show a => Show (Cola a) where
  show = escribeCola

-- Ejemplo de cola:
--    λ> inserta 5 (inserta 2 (inserta 3 vacia))
--    3 | 2 | 5

-- vacia es la cola vacía. Por ejemplo,
--    λ> vacia
--    C []
vacia :: Cola a
vacia = C empty

-- (inserta x c) es la cola obtenida añadiendo x al final de la cola
-- c. Por ejemplo,
--    λ> ej = inserta 2 (inserta 3 vacia)
--    λ> ej
--    3 | 2
--    λ> inserta 5 ej
--    3 | 2 | 5
inserta :: a -> Cola a -> Cola a
inserta x (C xs) = C (xs |> x )

-- (primero c) es el primer elemento de la cola c. Por ejemplo,
--    λ> primero (inserta 5 (inserta 2 (inserta 3 vacia)))
--    3
primero :: Cola a -> a
primero (C xs) = case viewl xs of
  EmptyL -> error "primero de la pila vacia"
  x :< _ -> x

-- (resto c) es la cola obtenida eliminando el primer elemento de la
-- cola c. Por ejemplo,
--    λ> resto (inserta 5 (inserta 2 (inserta 3 vacia)))
--    2 | 5
resto :: Cola a -> Cola a
resto (C xs) = case viewl xs of
  EmptyL   -> error "resto la pila vacia"
  _ :< xs' -> C xs'

-- (esVacia c) se verifica si c es la cola vacía. Por ejemplo,
--    esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False
--    esVacia vacia  == True
esVacia :: Cola a -> Bool
esVacia (C xs)  = S.null xs

-- Generador de colas                                          --
-- ==================

-- genCola es un generador de colas de enteros. Por ejemplo,
--    λ> sample genCola
--    -
--    2 | -2
--    0 | 0 | 0 | 4
--    -
--    2
--    -1 | -6 | 9
--    12 | -12 | -12 | 7 | -2 | -3 | 5 | -8 | -3 | -9 | -6
--    -11 | -5 | -7 | -8 | -10 | 8 | -9 | -7 | 6 | -12 | 8 | -9 | -1
--    -16 | -12
--    -17 | -17 | 1 | 2 | -15 | -15 | -13 | 8 | 13 | -12 | 15
--    -16 | -18
genCola :: (Arbitrary a, Num a) => Gen (Cola a)
genCola = do
  xs <- listOf arbitrary
  return (foldr inserta vacia xs)

-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Cola a) where
  arbitrary = genCola

-- Propiedades de las colas
-- ========================

-- Las propiedades son
prop_colas1 :: Int -> Cola Int -> Bool
prop_colas1 x c =
  primero (inserta x vacia) == x &&
  resto (inserta x vacia) == vacia &&
  esVacia vacia &&
  not (esVacia (inserta x c))

prop_colas2 :: Int -> Cola Int -> Property
prop_colas2 x c =
  not (esVacia c) ==>
  primero (inserta x c) == primero c &&
  resto (inserta x c) == inserta x (resto c)

-- La comprobación es:
--    λ> quickCheck prop_colas1
--    +++ OK, passed 100 tests.
--    λ> quickCheck prop_colas2
--    +++ OK, passed 100 tests; 9 discarded.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

{-# LANGUAGE FlexibleInstances #-}

{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.ColaConSucesiones

(Cola,

vacia, -- Cola a

inserta, -- a -> Cola a -> Cola a

primero, -- Cola a -> a

resto, -- Cola a -> Cola a

esVacia, -- Cola a -> Bool

) where

import Data.Sequence as S

import Test.QuickCheck

-- Colas como sucesiones:

newtype Cola a = C (Seq a)

deriving Eq

-- (escribeCola c) es la cadena correspondiente a la cola c. Por

-- ejemplo,

-- escribeCola (inserta 5 (inserta 2 (inserta 3 vacia))) == "3 | 2 | 5"

escribeCola :: Show a => Cola a -> String

escribeCola (C xs) = case viewl xs of

EmptyL -> "-"

x :< xs' -> case viewl xs' of

EmptyL -> show x

_ -> show x ++ " | " ++ escribeCola (C xs')

-- Procedimiento de escritura de colas.

instance Show a => Show (Cola a) where

show = escribeCola

-- Ejemplo de cola:

-- λ> inserta 5 (inserta 2 (inserta 3 vacia))

-- 3 | 2 | 5

-- vacia es la cola vacía. Por ejemplo,

-- λ> vacia

-- C []

vacia :: Cola a

vacia = C empty

-- (inserta x c) es la cola obtenida añadiendo x al final de la cola

-- c. Por ejemplo,

-- λ> ej = inserta 2 (inserta 3 vacia)

-- λ> ej

-- 3 | 2

-- λ> inserta 5 ej

-- 3 | 2 | 5

inserta :: a -> Cola a -> Cola a

inserta x (C xs) = C (xs |> x )

-- (primero c) es el primer elemento de la cola c. Por ejemplo,

-- λ> primero (inserta 5 (inserta 2 (inserta 3 vacia)))

-- 3

primero :: Cola a -> a

primero (C xs) = case viewl xs of

EmptyL -> error "primero de la pila vacia"

x :< _ -> x

-- (resto c) es la cola obtenida eliminando el primer elemento de la

-- cola c. Por ejemplo,

-- λ> resto (inserta 5 (inserta 2 (inserta 3 vacia)))

-- 2 | 5

resto :: Cola a -> Cola a

resto (C xs) = case viewl xs of

EmptyL -> error "resto la pila vacia"

_ :< xs' -> C xs'

-- (esVacia c) se verifica si c es la cola vacía. Por ejemplo,

-- esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False

-- esVacia vacia == True

esVacia :: Cola a -> Bool

esVacia (C xs) = S.null xs

-- Generador de colas --

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

-- genCola es un generador de colas de enteros. Por ejemplo,

-- λ> sample genCola

-- -

-- 2 | -2

-- 0 | 0 | 0 | 4

-- -

-- 2

-- -1 | -6 | 9

-- 12 | -12 | -12 | 7 | -2 | -3 | 5 | -8 | -3 | -9 | -6

-- -11 | -5 | -7 | -8 | -10 | 8 | -9 | -7 | 6 | -12 | 8 | -9 | -1

-- -16 | -12

-- -17 | -17 | 1 | 2 | -15 | -15 | -13 | 8 | 13 | -12 | 15

-- -16 | -18

genCola :: (Arbitrary a, Num a) => Gen (Cola a)

genCola = do

xs <- listOf arbitrary

return (foldr inserta vacia xs)

-- El tipo pila es una instancia del arbitrario.

instance (Arbitrary a, Num a) => Arbitrary (Cola a) where

arbitrary = genCola

-- Propiedades de las colas

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

-- Las propiedades son

prop_colas1 :: Int -> Cola Int -> Bool

prop_colas1 x c =

primero (inserta x vacia) == x &&

resto (inserta x vacia) == vacia &&

esVacia vacia &&

not (esVacia (inserta x c))

prop_colas2 :: Int -> Cola Int -> Property

prop_colas2 x c =

not (esVacia c) ==>

primero (inserta x c) == primero c &&

resto (inserta x c) == inserta x (resto c)

-- La comprobación es:

-- λ> quickCheck prop_colas1

-- +++ OK, passed 100 tests.

-- λ> quickCheck prop_colas2

-- +++ OK, passed 100 tests; 9 discarded.

3. Las colas en Python

3.1. El tipo abstracto de las colas en Python

La implementación se encuentra en el módulo cola.py cuyo contenido es el siguiente:

__all__ = [
    'Cola',
    'vacia',
    'inserta',
    'primero',
    'resto',
    'esVacia',
    'colaAleatoria'
]
from src.TAD.colaConListas import (Cola, colaAleatoria, esVacia, inserta,
                                   primero, resto, vacia)
# from src.TAD.colaConDosListas import (Cola, colaAleatoria, esVacia, inserta,
#                                       primero, resto, vacia)
# from src.TAD.colaConDeque import (Cola, vacia, inserta, primero, resto,
#                                   esVacia, colaAleatoria)

__all__ = [

'Cola',

'vacia',

'inserta',

'primero',

'resto',

'esVacia',

'colaAleatoria'

]

from src.TAD.colaConListas import (Cola, colaAleatoria, esVacia, inserta,

primero, resto, vacia)

# from src.TAD.colaConDosListas import (Cola, colaAleatoria, esVacia, inserta,

# primero, resto, vacia)

# from src.TAD.colaConDeque import (Cola, vacia, inserta, primero, resto,

# esVacia, colaAleatoria)

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos tres: una usando listas, otra usando pares de listas y otra usando deques. Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

3.2. Implementación de las colas mediante listas

La implementación se encuentra en el módulo colaConListas.py en el que se define la clase Cola con los siguientes métodos:

inserta(x) añade x al final de la cola.
primero() es el primero de la cola.
resto() elimina el primero de la cola.
esVacia() se verifica si la cola es vacía.

Por ejemplo,

   >>> c = Cola()
   >>> c
   -
   >>> c.inserta(5)
   >>> c.inserta(2)
   >>> c.inserta(3)
   >>> c.inserta(4)
   >>> c
   5 | 2 | 3 | 4
   >>> c.primero()
   5
   >>> c.resto()
   >>> c
   2 | 3 | 4
   >>> c.esVacia()
   False
   >>> c = Cola()
   >>> c.esVacia()
   True

>>> c = Cola()

>>> c

>>> c.inserta(5)

>>> c.inserta(2)

>>> c.inserta(3)

>>> c.inserta(4)

>>> c

5 | 2 | 3 | 4

>>> c.primero()

>>> c.resto()

>>> c

2 | 3 | 4

>>> c.esVacia()

False

>>> c = Cola()

>>> c.esVacia()

True

Además se definen las correspondientes funciones. Por ejemplo,

   >>> vacia()
   -
   >>> inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))
   5 | 2 | 3 | 4
   >>> primero(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))
   5
   >>> resto(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))
   2 | 3 | 4
   >>> esVacia(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))
   False
   >>> esVacia(vacia())
   True

>>> vacia()

>>> inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))

5 | 2 | 3 | 4

>>> primero(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))

>>> resto(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))

2 | 3 | 4

>>> esVacia(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))

False

>>> esVacia(vacia())

True

Finalmente, se define un generador aleatorio de colas y se comprueba que las colas cumplen las propiedades de su especificación.

__all__ = [
    'Cola',
    'vacia',
    'inserta',
    'primero',
    'resto',
    'esVacia',
    'colaAleatoria'
]

from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, TypeVar

from hypothesis import assume, given
from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las colas mediante listas
# ==================================

@dataclass
class Cola(Generic[A]):
    _elementos: list[A] = field(default_factory=list)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos de la cola separados por " | ".
        Si la cola está vacía, devuelve "-".
        """
        if not self._elementos:
            return '-'
        return ' | '.join(str(x) for x in self._elementos)

    def inserta(self, x: A) -> None:
        """
        Inserta el elemento x al final de la cola.
        """
        self._elementos.append(x)

    def esVacia(self) -> bool:
        """
        Comprueba si la cola está vacía.

        Devuelve True si la cola está vacía, False en caso contrario.
        """
        return not self._elementos

    def primero(self) -> A:
        """
        Devuelve el primer elemento de la cola.
        """
        return self._elementos[0]

    def resto(self) -> None:
        """
        Elimina el primer elemento de la cola
        """
        self._elementos.pop(0)

# Funciones del tipo de las listas
# ================================

def vacia() -> Cola[A]:
    """
    Crea y devuelve una cola vacía de tipo A.
    """
    c: Cola[A] = Cola()
    return c

def inserta(x: A, c: Cola[A]) -> Cola[A]:
    """
    Inserta un elemento x en la cola c y devuelve una nueva cola con
    el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux

def esVacia(c: Cola[A]) -> bool:
    """
    Devuelve True si la cola está vacía, False si no lo está.
    """
    return c.esVacia()

def primero(c: Cola[A]) -> A:
    """
    Devuelve el primer elemento de la cola c.
    """
    return c.primero()

def resto(c: Cola[A]) -> Cola[A]:
    """
    Elimina el primer elemento de la cola c y devuelve una copia de la
    cola resultante.
    """
    _aux = deepcopy(c)
    _aux.resto()
    return _aux

# Generador de colas
# ==================

def colaAleatoria() -> st.SearchStrategy[Cola[int]]:
    """
    Genera una estrategia de búsqueda para generar colas de enteros de
    forma aleatoria.

    Utiliza la librería Hypothesis para generar una lista de enteros y
    luego se convierte en una instancia de la clase cola.
    """
    return st.lists(st.integers()).map(Cola)

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

# Las propiedades son
@given(c=colaAleatoria(), x=st.integers())
def test_cola1(c: Cola[int], x: int) -> None:
    assert primero(inserta(x, vacia())) == x
    assert resto(inserta(x, vacia())) == vacia()
    assert esVacia(vacia())
    assert not esVacia(inserta(x, c))

@given(c=colaAleatoria(), x=st.integers())
def test_cola2(c: Cola[int], x: int) -> None:
    assume(not esVacia(c))
    assert primero(inserta(x, c)) == primero(c)
    assert resto(inserta(x, c)) == inserta(x, resto(c))

# La comprobación es
#    > poetry run pytest -q colaConListas.py
#    1 passed in 0.24s

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

__all__ = [

'Cola',

'vacia',

'inserta',

'primero',

'resto',

'esVacia',

'colaAleatoria'

]

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Generic, TypeVar

from hypothesis import assume, given

from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las colas mediante listas

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

@dataclass

class Cola(Generic[A]):

_elementos: list[A] = field(default_factory=list)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos de la cola separados por " | ".

Si la cola está vacía, devuelve "-".

"""

if not self._elementos:

return '-'

return ' | '.join(str(x) for x in self._elementos)

def inserta(self, x: A) -> None:

"""

Inserta el elemento x al final de la cola.

"""

self._elementos.append(x)

def esVacia(self) -> bool:

"""

Comprueba si la cola está vacía.

Devuelve True si la cola está vacía, False en caso contrario.

"""

return not self._elementos

def primero(self) -> A:

"""

Devuelve el primer elemento de la cola.

"""

return self._elementos[0]

def resto(self) -> None:

"""

Elimina el primer elemento de la cola

"""

self._elementos.pop(0)

# Funciones del tipo de las listas

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

def vacia() -> Cola[A]:

"""

Crea y devuelve una cola vacía de tipo A.

"""

c: Cola[A] = Cola()

return c

def inserta(x: A, c: Cola[A]) -> Cola[A]:

"""

Inserta un elemento x en la cola c y devuelve una nueva cola con

el elemento insertado.

"""

_aux = deepcopy(c)

_aux.inserta(x)

return _aux

def esVacia(c: Cola[A]) -> bool:

"""

Devuelve True si la cola está vacía, False si no lo está.

"""

return c.esVacia()

def primero(c: Cola[A]) -> A:

"""

Devuelve el primer elemento de la cola c.

"""

return c.primero()

def resto(c: Cola[A]) -> Cola[A]:

"""

Elimina el primer elemento de la cola c y devuelve una copia de la

cola resultante.

"""

_aux = deepcopy(c)

_aux.resto()

return _aux

# Generador de colas

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

def colaAleatoria() -> st.SearchStrategy[Cola[int]]:

"""

Genera una estrategia de búsqueda para generar colas de enteros de

forma aleatoria.

Utiliza la librería Hypothesis para generar una lista de enteros y

luego se convierte en una instancia de la clase cola.

"""

return st.lists(st.integers()).map(Cola)

# Comprobación de las propiedades de las colas

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

# Las propiedades son

@given(c=colaAleatoria(), x=st.integers())

def test_cola1(c: Cola[int], x: int) -> None:

assert primero(inserta(x, vacia())) == x

assert resto(inserta(x, vacia())) == vacia()

assert esVacia(vacia())

assert not esVacia(inserta(x, c))

@given(c=colaAleatoria(), x=st.integers())

def test_cola2(c: Cola[int], x: int) -> None:

assume(not esVacia(c))

assert primero(inserta(x, c)) == primero(c)

assert resto(inserta(x, c)) == inserta(x, resto(c))

# La comprobación es

# > poetry run pytest -q colaConListas.py

# 1 passed in 0.24s

3.3. Implementación de las colas mediante pares de listas

La implementación se encuentra en el módulo colaConDosListas.py cuyo contenido es

__all__ = [
    'Cola',
    'vacia',
    'inserta',
    'primero',
    'resto',
    'esVacia',
    'colaAleatoria'
]

from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, TypeVar

from hypothesis import assume, given
from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las colas mediante listas
# ==================================

@dataclass
class Cola(Generic[A]):
    _primera: list[A] = field(default_factory=list)
    _segunda: list[A] = field(default_factory=list)

    def _elementos(self) -> list[A]:
        """
        Devuelve una lista con los elementos de la cola en orden.
        """
        return self._primera + self._segunda[::-1]

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos de la cola separados por " | ".
        Si la cola está vacía, devuelve "-".
        """
        elementos = self._elementos()
        if not elementos:
            return "-"
        return " | ".join(map(str, elementos))

    def __eq__(self, c) -> bool:
        """
        Comprueba si la cola actual es igual a otra cola.
        Se considera que dos colas son iguales si tienen los mismos
        elementos en el mismo orden.

        Parámetro:
        - c (Cola): La cola con la que se va a comparar.

        Devuelve True si las dos colas son iguales, False en caso
        contrario.
        """
        return self._elementos() == c._elementos()

    def inserta(self, y: A) -> None:
        """
        Inserta el elemento y en la cola.
        """
        xs = self._primera
        ys = self._segunda
        # Si no hay elementos en la primera lista, se inserta en la segunda
        if not xs:
            ys.insert(0, y)
            # Se invierte la segunda lista y se asigna a la primera
            self._primera = ys[::-1]
            self._segunda = []
        else:
            # Si hay elementos en la primera lista, se inserta en la segunda
            ys.insert(0, y)

    def esVacia(self) -> bool:
        """
        Devuelve si la cola está vacía.
        """
        return not self._primera

    def primero(self) -> A:
        """
        Devuelve el primer elemento de la cola.
        """
        return self._primera[0]

    def resto(self) -> None:
        """
        Elimina el primer elemento de la cola.
        """
        xs = self._primera
        ys = self._segunda
        del xs[0]
        if not xs:
            self._primera = ys[::-1]
            self._segunda = []

# Funciones del tipo de las listas
# ================================

def vacia() -> Cola[A]:
    """
    Crea y devuelve una cola vacía de tipo A.
    """
    c: Cola[A] = Cola()
    return c

def inserta(x: A, c: Cola[A]) -> Cola[A]:
    """
    Inserta un elemento x en la cola c y devuelve una nueva cola con
    el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux

def esVacia(c: Cola[A]) -> bool:
    """
    Devuelve True si la cola está vacía, False si no lo está.
    """
    return c.esVacia()

def primero(c: Cola[A]) -> A:
    """
    Devuelve el primer elemento de la cola c.
    """
    return c.primero()

def resto(c: Cola[A]) -> Cola[A]:
    """
    Elimina el primer elemento de la cola c y devuelve una copia de la
    cola resultante.
    """
    _aux = deepcopy(c)
    _aux.resto()
    return _aux

# Generador de colas
# ==================

def colaAleatoria() -> st.SearchStrategy[Cola[int]]:
    """
    Genera una estrategia de búsqueda para generar colas de enteros de
    forma aleatoria.

    Utiliza la librería Hypothesis para generar una lista de enteros y
    luego se convierte en una instancia de la clase cola.
    """
    return st.lists(st.integers()).map(Cola)

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

# Las propiedades son
@given(c=colaAleatoria(), x=st.integers())
def test_cola1(c: Cola[int], x: int) -> None:
    assert primero(inserta(x, vacia())) == x
    assert resto(inserta(x, vacia())) == vacia()
    assert esVacia(vacia())
    assert not esVacia(inserta(x, c))

@given(c=colaAleatoria(), x=st.integers())
def test_cola2(c: Cola[int], x: int) -> None:
    assume(not esVacia(c))
    assert primero(inserta(x, c)) == primero(c)
    assert resto(inserta(x, c)) == inserta(x, resto(c))

# La comprobación es
#    > poetry run pytest -q colaConListas.py
#    2 passed in 0.40s

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

__all__ = [

'Cola',

'vacia',

'inserta',

'primero',

'resto',

'esVacia',

'colaAleatoria'

]

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Generic, TypeVar

from hypothesis import assume, given

from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las colas mediante listas

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

@dataclass

class Cola(Generic[A]):

_primera: list[A] = field(default_factory=list)

_segunda: list[A] = field(default_factory=list)

def _elementos(self) -> list[A]:

"""

Devuelve una lista con los elementos de la cola en orden.

"""

return self._primera + self._segunda[::-1]

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos de la cola separados por " | ".

Si la cola está vacía, devuelve "-".

"""

elementos = self._elementos()

if not elementos:

return "-"

return " | ".join(map(str, elementos))

def __eq__(self, c) -> bool:

"""

Comprueba si la cola actual es igual a otra cola.

Se considera que dos colas son iguales si tienen los mismos

elementos en el mismo orden.

Parámetro:

- c (Cola): La cola con la que se va a comparar.

Devuelve True si las dos colas son iguales, False en caso

contrario.

"""

return self._elementos() == c._elementos()

def inserta(self, y: A) -> None:

"""

Inserta el elemento y en la cola.

"""

xs = self._primera

ys = self._segunda

# Si no hay elementos en la primera lista, se inserta en la segunda

if not xs:

ys.insert(0, y)

# Se invierte la segunda lista y se asigna a la primera

self._primera = ys[::-1]

self._segunda = []

else:

# Si hay elementos en la primera lista, se inserta en la segunda

ys.insert(0, y)

def esVacia(self) -> bool:

"""

Devuelve si la cola está vacía.

"""

return not self._primera

def primero(self) -> A:

"""

Devuelve el primer elemento de la cola.

"""

return self._primera[0]

def resto(self) -> None:

"""

Elimina el primer elemento de la cola.

"""

xs = self._primera

ys = self._segunda

del xs[0]

if not xs:

self._primera = ys[::-1]

self._segunda = []

# Funciones del tipo de las listas

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

def vacia() -> Cola[A]:

"""

Crea y devuelve una cola vacía de tipo A.

"""

c: Cola[A] = Cola()

return c

def inserta(x: A, c: Cola[A]) -> Cola[A]:

"""

Inserta un elemento x en la cola c y devuelve una nueva cola con

el elemento insertado.

"""

_aux = deepcopy(c)

_aux.inserta(x)

return _aux

def esVacia(c: Cola[A]) -> bool:

"""

Devuelve True si la cola está vacía, False si no lo está.

"""

return c.esVacia()

def primero(c: Cola[A]) -> A:

"""

Devuelve el primer elemento de la cola c.

"""

return c.primero()

def resto(c: Cola[A]) -> Cola[A]:

"""

Elimina el primer elemento de la cola c y devuelve una copia de la

cola resultante.

"""

_aux = deepcopy(c)

_aux.resto()

return _aux

# Generador de colas

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

def colaAleatoria() -> st.SearchStrategy[Cola[int]]:

"""

Genera una estrategia de búsqueda para generar colas de enteros de

forma aleatoria.

Utiliza la librería Hypothesis para generar una lista de enteros y

luego se convierte en una instancia de la clase cola.

"""

return st.lists(st.integers()).map(Cola)

# Comprobación de las propiedades de las colas

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

# Las propiedades son

@given(c=colaAleatoria(), x=st.integers())

def test_cola1(c: Cola[int], x: int) -> None:

assert primero(inserta(x, vacia())) == x

assert resto(inserta(x, vacia())) == vacia()

assert esVacia(vacia())

assert not esVacia(inserta(x, c))

@given(c=colaAleatoria(), x=st.integers())

def test_cola2(c: Cola[int], x: int) -> None:

assume(not esVacia(c))

assert primero(inserta(x, c)) == primero(c)

assert resto(inserta(x, c)) == inserta(x, resto(c))

# La comprobación es

# > poetry run pytest -q colaConListas.py

# 2 passed in 0.40s

3.4. Implementación de las colas mediante deque

La implementación (que usa la librería deque) se encuentra en el módulo colaConDeque.py y su contenido es el siguiente:

__all__ = [
    'Pila',
    'vacia',
    'apila',
    'esVacia',
    'cima',
    'desapila',
    'pilaAleatoria'
]

from collections import deque
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las pilas mediante listas
# ==================================

@dataclass
class Pila(Generic[A]):
    _elementos: deque[A] = field(default_factory=deque)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos de la pila separados por " | ".
        Si la pila está vacía, devuelve "-".
        """
        if len(self._elementos) == 0:
            return '-'
        return ' | '.join(str(x) for x in self._elementos)

    def apila(self, x: A) -> None:
        """
        Agrega el elemento x al inicio de la pila.
        """
        self._elementos.appendleft(x)

    def esVacia(self) -> bool:
        """
        Verifica si la pila está vacía.

        Devuelve True si la pila está vacía, False en caso contrario.
        """
        return len(self._elementos) == 0

    def cima(self) -> A:
        """
        Devuelve el elemento en la cima de la pila.
        """
        return self._elementos[0]

    def desapila(self) -> None:
        """
        Elimina el elemento en la cima de la pila.
        """
        self._elementos.popleft()

# Funciones del tipo de las listas
# ================================

def vacia() -> Pila[A]:
    """
    Crea y devuelve una pila vacía de tipo A.
    """
    p: Pila[A] = Pila()
    return p

def apila(x: A, p: Pila[A]) -> Pila[A]:
    """
    Añade un elemento x al tope de la pila p y devuelve una copia de la
    pila modificada.
    """
    _aux = deepcopy(p)
    _aux.apila(x)
    return _aux

def esVacia(p: Pila[A]) -> bool:
    """
    Devuelve True si la pila está vacía, False si no lo está.
    """
    return p.esVacia()

def cima(p: Pila[A]) -> A:
    """
    Devuelve el elemento en la cima de la pila p.
    """
    return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:
    """
    Elimina el elemento en la cima de la pilla p y devuelve una copia de la
    pila resultante.
    """
    _aux = deepcopy(p)
    _aux.desapila()
    return _aux

# Generador de pilas
# ==================

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:
    """
    Genera una estrategia de búsqueda para generar pilas de enteros de
    forma aleatoria.

    Utiliza la librería Hypothesis para generar una lista de enteros y
    luego se convierte en una instancia de la clase pila.
    """
    def _creaPila(elementos: list[int]) -> Pila[int]:
        pila: Pila[int] = vacia()
        pila._elementos.extendleft(elementos)
        return pila
    return st.builds(_creaPila, st.lists(st.integers()))

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

# Las propiedades son
@given(p=pilaAleatoria(), x=st.integers())
def test_pila(p: Pila[int], x: int) -> None:
    assert cima(apila(x, p)) == x
    assert desapila(apila(x, p)) == p
    assert esVacia(vacia())
    assert not esVacia(apila(x, p))

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

__all__ = [

'Pila',

'vacia',

'apila',

'esVacia',

'cima',

'desapila',

'pilaAleatoria'

]

from collections import deque

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Generic, TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las pilas mediante listas

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

@dataclass

class Pila(Generic[A]):

_elementos: deque[A] = field(default_factory=deque)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos de la pila separados por " | ".

Si la pila está vacía, devuelve "-".

"""

if len(self._elementos) == 0:

return '-'

return ' | '.join(str(x) for x in self._elementos)

def apila(self, x: A) -> None:

"""

Agrega el elemento x al inicio de la pila.

"""

self._elementos.appendleft(x)

def esVacia(self) -> bool:

"""

Verifica si la pila está vacía.

Devuelve True si la pila está vacía, False en caso contrario.

"""

return len(self._elementos) == 0

def cima(self) -> A:

"""

Devuelve el elemento en la cima de la pila.

"""

return self._elementos[0]

def desapila(self) -> None:

"""

Elimina el elemento en la cima de la pila.

"""

self._elementos.popleft()

# Funciones del tipo de las listas

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

def vacia() -> Pila[A]:

"""

Crea y devuelve una pila vacía de tipo A.

"""

p: Pila[A] = Pila()

return p

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

"""

Añade un elemento x al tope de la pila p y devuelve una copia de la

pila modificada.

"""

_aux = deepcopy(p)

_aux.apila(x)

return _aux

def esVacia(p: Pila[A]) -> bool:

"""

Devuelve True si la pila está vacía, False si no lo está.

"""

return p.esVacia()

def cima(p: Pila[A]) -> A:

"""

Devuelve el elemento en la cima de la pila p.

"""

return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:

"""

Elimina el elemento en la cima de la pilla p y devuelve una copia de la

pila resultante.

"""

_aux = deepcopy(p)

_aux.desapila()

return _aux

# Generador de pilas

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

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:

"""

Genera una estrategia de búsqueda para generar pilas de enteros de

forma aleatoria.

Utiliza la librería Hypothesis para generar una lista de enteros y

luego se convierte en una instancia de la clase pila.

"""

def _creaPila(elementos: list[int]) -> Pila[int]:

pila: Pila[int] = vacia()

pila._elementos.extendleft(elementos)

return pila

return st.builds(_creaPila, st.lists(st.integers()))

# Comprobación de las propiedades de las pilas

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

# Las propiedades son

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

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

assert cima(apila(x, p)) == x

assert desapila(apila(x, p)) == p

assert esVacia(vacia())

assert not esVacia(apila(x, p))

# La comprobación es

# > poetry run pytest -q pilaConQueue.py

# 1 passed in 0.25s

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

PorJosé A. Alonso 3-febrero-202322-enero-2023

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

   nubPila :: Eq a => Pila a -> Pila a

1	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

1 2	λ> 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.

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

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

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.

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

# 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

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

TAD de las pilas: Ordenación de pilas por inserción

PorJosé A. Alonso 2-febrero-202322-enero-2023

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

   ordenaInserPila :: Ord a => Pila a -> Pila a

1	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

1 2	λ> 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.

Soluciones en Haskell

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.

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.

Soluciones en Python

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

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

TAD de las pilas: Reconocimiento de ordenación de pilas

PorJosé A. Alonso 1-febrero-202322-enero-2023

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

   ordenadaPila :: Ord a => Pila a -> Bool

1	ordenadaPila :: Ord a => Pila a -> Bool

tal que ordenadaPila p se verifica si los elementos de la pila p están ordenados en orden creciente. Por ejemplo,

   ordenadaPila (apila 1 (apila 5 (apila 6 vacia))) == True
   ordenadaPila (apila 1 (apila 0 (apila 6 vacia))) == False

1 2	ordenadaPila (apila 1 (apila 5 (apila 6 vacia))) == True ordenadaPila (apila 1 (apila 0 (apila 6 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
-- ===========

ordenadaPila :: Ord a => Pila a -> Bool
ordenadaPila p
  | esVacia p  = True
  | esVacia dp = True
  | otherwise  = cp <= cdp && ordenadaPila dp
  where cp  = cima p
        dp  = desapila p
        cdp = cima dp

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

ordenadaPila2 :: Ord a => Pila a -> Bool
ordenadaPila2 =
  ordenadaLista . reverse . pilaAlista

-- (ordenadaLista xs) se verifica si la lista xs está ordenada de menor
-- a mayor. Por ejemplo,
ordenadaLista :: Ord a => [a] -> Bool
ordenadaLista xs =
  and [x <= y | (x,y) <- zip xs (tail xs)]

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

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

-- La propiedad es
prop_ordenadaPila :: Pila Int -> Bool
prop_ordenadaPila p =
  ordenadaPila p == ordenadaPila2 p

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

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

import Transformaciones_pilas_listas (pilaAlista)

import Test.QuickCheck

-- 1ª solución

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

ordenadaPila :: Ord a => Pila a -> Bool

ordenadaPila p

| esVacia p = True

| esVacia dp = True

| otherwise = cp <= cdp && ordenadaPila dp

where cp = cima p

dp = desapila p

cdp = cima dp

-- 2ª solución

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

ordenadaPila2 :: Ord a => Pila a -> Bool

ordenadaPila2 =

ordenadaLista . reverse . pilaAlista

-- (ordenadaLista xs) se verifica si la lista xs está ordenada de menor

-- a mayor. Por ejemplo,

ordenadaLista :: Ord a => [a] -> Bool

ordenadaLista xs =

and [x <= y | (x,y) <- zip xs (tail xs)]

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

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

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

-- Comprobación de equivalencia

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

-- La propiedad es

prop_ordenadaPila :: Pila Int -> Bool

prop_ordenadaPila p =

ordenadaPila p == ordenadaPila2 p

-- La comprobación es

-- λ> quickCheck prop_ordenadaPila

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

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

A = TypeVar('A', int, float, str)

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

def ordenadaPila(p: Pila[A]) -> bool:
    if esVacia(p):
        return True
    cp = cima(p)
    dp = desapila(p)
    if esVacia(dp):
        return True
    cdp = cima(dp)
    return cp <= cdp and ordenadaPila(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

# ordenadaLista(xs, ys) se verifica si xs es una lista ordenada. Por
# ejemplo,
#    >>> ordenadaLista([2, 5, 8])
#    True
#    >>> ordenadalista([2, 8, 5])
#    False
def ordenadaLista(xs: list[A]) -> bool:
    return all((x <= y for (x, y) in zip(xs, xs[1:])))

def ordenadaPila2(p: Pila[A]) -> bool:
    return ordenadaLista(list(reversed(pilaAlista(p))))

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

def ordenadaPila3Aux(p: Pila[A]) -> bool:
    if p.esVacia():
        return True
    cp = p.cima()
    p.desapila()
    if p.esVacia():
        return True
    return cp <= p.cima() and ordenadaPila3Aux(p)

def ordenadaPila3(p: Pila[A]) -> bool:
    q = deepcopy(p)
    return ordenadaPila3Aux(q)

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

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

def ordenadaPila4(p: Pila[A]) -> bool:
    q = deepcopy(p)
    return ordenadaPila4Aux(q)

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

# La propiedad es
@given(p=pilaAleatoria())
def test_ordenadaPila(p: Pila[int]) -> None:
    r = ordenadaPila(p)
    assert ordenadaPila2(p) == r
    assert ordenadaPila3(p) == r
    assert ordenadaPila4(p) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

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

vacia)

from src.transformaciones_pilas_listas import pilaAlista

A = TypeVar('A', int, float, str)

# 1ª solución

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

def ordenadaPila(p: Pila[A]) -> bool:

if esVacia(p):

return True

cp = cima(p)

dp = desapila(p)

if esVacia(dp):

return True

cdp = cima(dp)

return cp <= cdp and ordenadaPila(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

# ordenadaLista(xs, ys) se verifica si xs es una lista ordenada. Por

# ejemplo,

# >>> ordenadaLista([2, 5, 8])

# True

# >>> ordenadalista([2, 8, 5])

# False

def ordenadaLista(xs: list[A]) -> bool:

return all((x <= y for (x, y) in zip(xs, xs[1:])))

def ordenadaPila2(p: Pila[A]) -> bool:

return ordenadaLista(list(reversed(pilaAlista(p))))

# 3ª solución

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

def ordenadaPila3Aux(p: Pila[A]) -> bool:

if p.esVacia():

return True

cp = p.cima()

p.desapila()

if p.esVacia():

return True

return cp <= p.cima() and ordenadaPila3Aux(p)

def ordenadaPila3(p: Pila[A]) -> bool:

q = deepcopy(p)

return ordenadaPila3Aux(q)

# 4ª solución

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

def ordenadaPila4Aux(p: Pila[A]) -> bool:

while not p.esVacia():

cp = p.cima()

p.desapila()

if not p.esVacia() and cp > p.cima():

return False

return True

def ordenadaPila4(p: Pila[A]) -> bool:

q = deepcopy(p)

return ordenadaPila4Aux(q)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(p=pilaAleatoria())

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

r = ordenadaPila(p)

assert ordenadaPila2(p) == r

assert ordenadaPila3(p) == r

assert ordenadaPila4(p) == r

# La comprobación es

# src> poetry run pytest -q ordenadaPila.py

# 1 passed in 0.31s

TAD de las pilas: Reconocimiento de subpilas

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

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

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

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

tal que subPila p1 p2 se verifica si p1 es una subpila de p2. Por ejemplo,

   λ> ej1 = apila 2 (apila 3 vacia)
   λ> ej2 = apila 7 (apila 2 (apila 3 (apila 5 vacia)))
   λ> ej3 = apila 2 (apila 7 (apila 3 (apila 5 vacia)))
   λ> subPila ej1 ej2
   True
   λ> subPila ej1 ej3
   False

λ> ej1 = apila 2 (apila 3 vacia)

λ> ej2 = apila 7 (apila 2 (apila 3 (apila 5 vacia)))

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

λ> subPila ej1 ej2

True

λ> subPila ej1 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 Transformaciones_pilas_listas (pilaAlista)
import PrefijoPila (prefijoPila)
import Data.List (isPrefixOf, tails)
import Test.QuickCheck

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

-- Se usará la función PrefijoPila del ejercicio
-- "Reconocimiento de prefijos de pilas" que se encuentra en
-- https://bit.ly/3Xqu7lo

subPila1 :: Eq a => Pila a -> Pila a -> Bool
subPila1 p1 p2
    | esVacia p1 = True
    | esVacia p2 = False
    | cp1 == cp2 = prefijoPila dp1 dp2 || subPila1 p1 dp2
    | otherwise  = subPila1 p1 dp2
    where cp1 = cima p1
          dp1 = desapila p1
          cp2 = cima p2
          dp2 = desapila 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

subPila2 :: Eq a => Pila a -> Pila a -> Bool
subPila2 p1 p2 =
  sublista (pilaAlista p1) (pilaAlista p2)

-- (sublista xs ys) se verifica si xs es una sublista de ys. Por
-- ejemplo,
--    sublista [3,2] [5,3,2,7]  ==  True
--    sublista [3,2] [5,3,7,2]  ==  False
sublista :: Eq a => [a] -> [a] -> Bool
sublista xs ys =
  any (xs `isPrefixOf`) (tails ys)

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

-- La propiedad es
prop_subPila :: Pila Int -> Pila Int -> Bool
prop_subPila p1 p2 =
  subPila1 p1 p2 == subPila2 p1 p2

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

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

import Transformaciones_pilas_listas (pilaAlista)

import PrefijoPila (prefijoPila)

import Data.List (isPrefixOf, tails)

import Test.QuickCheck

-- 1ª solución

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

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

-- "Reconocimiento de prefijos de pilas" que se encuentra en

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

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

subPila1 p1 p2

| esVacia p1 = True

| esVacia p2 = False

| cp1 == cp2 = prefijoPila dp1 dp2 || subPila1 p1 dp2

| otherwise = subPila1 p1 dp2

where cp1 = cima p1

dp1 = desapila p1

cp2 = cima p2

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

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

subPila2 p1 p2 =

sublista (pilaAlista p1) (pilaAlista p2)

-- (sublista xs ys) se verifica si xs es una sublista de ys. Por

-- ejemplo,

-- sublista [3,2] [5,3,2,7] == True

-- sublista [3,2] [5,3,7,2] == False

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

sublista xs ys =

any (xs `isPrefixOf`) (tails ys)

-- Comprobación de equivalencia

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

-- La propiedad es

prop_subPila :: Pila Int -> Pila Int -> Bool

prop_subPila p1 p2 =

subPila1 p1 p2 == subPila2 p1 p2

-- La comprobación es

-- λ> quickCheck prop_subPila

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.prefijoPila import prefijoPila
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 PrefijoPila del ejercicio
# "Reconocimiento de prefijos de pilas" que se encuentra en
# https://bit.ly/3Xqu7lo

def subPila1(p1: Pila[A], p2: Pila[A]) -> bool:
    if esVacia(p1):
        return True
    if esVacia(p2):
        return False
    cp1 = cima(p1)
    dp1 = desapila(p1)
    cp2 = cima(p2)
    dp2 = desapila(p2)
    if cp1 == cp2:
        return prefijoPila(dp1, dp2) or subPila1(p1, dp2)
    return subPila1(p1, dp2)

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

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

# sublista(xs, ys) se verifica si xs es una sublista de ys. Por
# ejemplo,
#    >>> sublista([3,2], [5,3,2,7])
#    True
#    >>> sublista([3,2], [5,3,7,2])
#    False
def sublista(xs: list[A], ys: list[A]) -> bool:
    return any(xs == ys[i:i+len(xs)] for i in range(len(ys) - len(xs) + 1))

def subPila2(p1: Pila[A], p2: Pila[A]) -> bool:
    return sublista(pilaAlista(p1), pilaAlista(p2))

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

def subPila3Aux(p1: Pila[A], p2: Pila[A]) -> bool:
    if p1.esVacia():
        return True
    if p2.esVacia():
        return False
    if p1.cima() != p2.cima():
        p2.desapila()
        return subPila3Aux(p1, p2)
    q1 = deepcopy(p1)
    p1.desapila()
    p2.desapila()
    return prefijoPila(p1, p2) or subPila3Aux(q1, p2)

def subPila3(p1: Pila[A], p2: Pila[A]) -> bool:
    q1 = deepcopy(p1)
    q2 = deepcopy(p2)
    return subPila3Aux(q1, q2)

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

# La propiedad es
@given(p1=pilaAleatoria(), p2=pilaAleatoria())
def test_subPila(p1: Pila[int], p2: Pila[int]) -> None:
    r = subPila1(p1, p2)
    assert subPila2(p1, p2) == r
    assert subPila3(p1, p2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.prefijoPila import prefijoPila

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 PrefijoPila del ejercicio

# "Reconocimiento de prefijos de pilas" que se encuentra en

# https://bit.ly/3Xqu7lo

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

if esVacia(p1):

return True

if esVacia(p2):

return False

cp1 = cima(p1)

dp1 = desapila(p1)

cp2 = cima(p2)

dp2 = desapila(p2)

if cp1 == cp2:

return prefijoPila(dp1, dp2) or subPila1(p1, dp2)

return subPila1(p1, dp2)

# 2ª solución

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

# Se usará la función pilaAlista del ejercicio

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

# https://bit.ly/3ZHewQ8

# sublista(xs, ys) se verifica si xs es una sublista de ys. Por

# ejemplo,

# >>> sublista([3,2], [5,3,2,7])

# True

# >>> sublista([3,2], [5,3,7,2])

# False

def sublista(xs: list[A], ys: list[A]) -> bool:

return any(xs == ys[i:i+len(xs)] for i in range(len(ys) - len(xs) + 1))

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

return sublista(pilaAlista(p1), pilaAlista(p2))

# 3ª solución

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

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

if p1.esVacia():

return True

if p2.esVacia():

return False

if p1.cima() != p2.cima():

p2.desapila()

return subPila3Aux(p1, p2)

q1 = deepcopy(p1)

p1.desapila()

p2.desapila()

return prefijoPila(p1, p2) or subPila3Aux(q1, p2)

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

q1 = deepcopy(p1)

q2 = deepcopy(p2)

return subPila3Aux(q1, q2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

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

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

r = subPila1(p1, p2)

assert subPila2(p1, p2) == r

assert subPila3(p1, p2) == r

# La comprobación es

# src> poetry run pytest -q subPila.py

# 1 passed in 0.32s

TAD de las pilas: Reconocimiento de prefijos de pilas

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

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

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

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

tal que prefijoPila p1 p2 se verifica si la pila p1 es justamente un prefijo de la pila p2. Por ejemplo,

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

λ> ej1 = apila 4 (apila 2 vacia)

λ> ej2 = apila 4 (apila 2 (apila 5 vacia))

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

λ> prefijoPila ej1 ej2

True

λ> prefijoPila ej1 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 Transformaciones_pilas_listas (pilaAlista)
import Data.List (isSuffixOf)
import Test.QuickCheck

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

prefijoPila :: Eq a => Pila a -> Pila a -> Bool
prefijoPila p1 p2
  | esVacia p1 = True
  | esVacia p2 = False
  | otherwise  = cp1 == cp2 && prefijoPila dp1 dp2
  where cp1 = cima p1
        dp1 = desapila p1
        cp2 = cima p2
        dp2 = desapila 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

prefijoPila2 :: Eq a => Pila a -> Pila a -> Bool
prefijoPila2 p1 p2 =
  pilaAlista p1 `isSuffixOf` pilaAlista p2

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

-- La propiedad es
prop_prefijoPila :: Pila Int -> Pila Int -> Bool
prop_prefijoPila p1 p2 =
  prefijoPila p1 p2 == prefijoPila2 p1 p2

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

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

import Transformaciones_pilas_listas (pilaAlista)

import Data.List (isSuffixOf)

import Test.QuickCheck

-- 1ª solución

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

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

prefijoPila p1 p2

| esVacia p1 = True

| esVacia p2 = False

| otherwise = cp1 == cp2 && prefijoPila dp1 dp2

where cp1 = cima p1

dp1 = desapila p1

cp2 = cima p2

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

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

prefijoPila2 p1 p2 =

pilaAlista p1 `isSuffixOf` pilaAlista p2

-- Comprobación de equivalencia

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

-- La propiedad es

prop_prefijoPila :: Pila Int -> Pila Int -> Bool

prop_prefijoPila p1 p2 =

prefijoPila p1 p2 == prefijoPila2 p1 p2

-- La comprobación es

-- λ> quickCheck prop_prefijoPila

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

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

# 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 esSufijoLista(xs: list[A], ys: list[A]) -> bool:
    if not xs:
        return True
    return xs == ys[-len(xs):]

def prefijoPila2(p1: Pila[A], p2: Pila[A]) -> bool:
    return esSufijoLista(pilaAlista(p1), pilaAlista(p2))

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

def prefijoPila3Aux(p1: Pila[A], p2: Pila[A]) -> bool:
    if p1.esVacia():
        return True
    if p2.esVacia():
        return False
    cp1 = p1.cima()
    p1.desapila()
    cp2 = p2.cima()
    p2.desapila()
    return cp1 == cp2 and prefijoPila3(p1, p2)

def prefijoPila3(p1: Pila[A], p2: Pila[A]) -> bool:
    q1 = deepcopy(p1)
    q2 = deepcopy(p2)
    return prefijoPila3Aux(q1, q2)

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

def prefijoPila4Aux(p1: Pila[A], p2: Pila[A]) -> bool:
    while not p2.esVacia() and not p1.esVacia():
        if p1.cima() != p2.cima():
            return False
        p1.desapila()
        p2.desapila()
    return p1.esVacia()

def prefijoPila4(p1: Pila[A], p2: Pila[A]) -> bool:
    q1 = deepcopy(p1)
    q2 = deepcopy(p2)
    return prefijoPila4Aux(q1, q2)

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

# La propiedad es
@given(p1=pilaAleatoria(), p2=pilaAleatoria())
def test_prefijoPila(p1: Pila[int], p2: Pila[int]) -> None:
    r = prefijoPila(p1, p2)
    assert prefijoPila2(p1, p2) == r
    assert prefijoPila3(p1, p2) == r
    assert prefijoPila4(p1, p2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

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

if esVacia(p1):

return True

if esVacia(p2):

return False

cp1 = cima(p1)

dp1 = desapila(p1)

cp2 = cima(p2)

dp2 = desapila(p2)

return cp1 == cp2 and prefijoPila(dp1, dp2)

# 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 esSufijoLista(xs: list[A], ys: list[A]) -> bool:

if not xs:

return True

return xs == ys[-len(xs):]

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

return esSufijoLista(pilaAlista(p1), pilaAlista(p2))

# 3ª solución

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

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

if p1.esVacia():

return True

if p2.esVacia():

return False

cp1 = p1.cima()

p1.desapila()

cp2 = p2.cima()

p2.desapila()

return cp1 == cp2 and prefijoPila3(p1, p2)

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

q1 = deepcopy(p1)

q2 = deepcopy(p2)

return prefijoPila3Aux(q1, q2)

# 4ª solución

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

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

while not p2.esVacia() and not p1.esVacia():

if p1.cima() != p2.cima():

return False

p1.desapila()

p2.desapila()

return p1.esVacia()

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

q1 = deepcopy(p1)

q2 = deepcopy(p2)

return prefijoPila4Aux(q1, q2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

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

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

r = prefijoPila(p1, p2)

assert prefijoPila2(p1, p2) == r

assert prefijoPila3(p1, p2) == r

assert prefijoPila4(p1, p2) == r

# La comprobación es

# src> poetry run pytest -q prefijoPila.py

# 1 passed in 0.32s

TAD de las pilas: Inclusión de pilas

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

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

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

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

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

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

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

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

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

El tipo abstracto de datos de las pilas

PorJosé A. Alonso 20-enero-202330-enero-2023

1. El tipo abstracto de datos de las pilas

Una pila es una estructura de datos, caracterizada por ser una secuencia de elementos en la que las operaciones de inserción y extracción se realizan por el mismo extremo.

Las operaciones que definen a tipo abstracto de datos (TAD) de las pilas (cuyos elementos son del tipo a) son las siguientes:

   vacia    :: Pila a
   apila    :: a -> Pila a -> Pila a
   cima     :: Pila a -> a
   desapila :: Pila a -> Pila a
   esVacia  :: Pila a -> Bool

vacia :: Pila a

apila :: a -> Pila a -> Pila a

cima :: Pila a -> a

desapila :: Pila a -> Pila a

esVacia :: Pila a -> Bool

tales que

vacia es la pila vacía.
(apila x p) es la pila obtenida añadiendo x al principio de p.
(cima p) es la cima de la pila p.
(desapila p) es la pila obtenida suprimiendo la cima de p.
(esVacia p) se verifica si p es la pila vacía.

Las operaciones tienen que verificar las siguientes propiedades:

cima(apila(x, p) == x
desapila(apila(x, p)) == p
esVacia(vacia)
not esVacia(apila(x, p))

2. Las pilas en Haskell

2.1. El tipo abstracto de datos de las pilas en Haskell

El TAD de las pilas se encuentra en el módulo Pila.hs cuyo contenido es el siguiente:

module TAD.Pila
  (Pila,
   vacia,      -- Pila a
   apila,      -- a -> Pila a -> Pila a
   cima,       -- Pila a -> a
   desapila,   -- Pila a -> Pila a
   esVacia,    -- Pila a -> Bool
   escribePila -- Show a => Pila a -> String
  ) where

import TAD.PilaConListas
-- import TAD.PilaConSucesiones

module TAD.Pila

(Pila,

vacia, -- Pila a

apila, -- a -> Pila a -> Pila a

cima, -- Pila a -> a

desapila, -- Pila a -> Pila a

esVacia, -- Pila a -> Bool

escribePila -- Show a => Pila a -> String

) where

import TAD.PilaConListas

-- import TAD.PilaConSucesiones

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos dos una usando listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

2.2. Implementación de las pilas mediante listas

La implementación se encuentra en el módulo PilaConListas.hs cuyo contenido es el siguiente:

module TAD.PilaConListas
  (Pila,
   vacia,      -- Pila a
   apila,      -- a -> Pila a -> Pila a
   cima,       -- Pila a -> a
   desapila,   -- Pila a -> Pila a
   esVacia,    -- Pila a -> Bool
   escribePila -- Show a => Pila a -> String
  ) where

import Test.QuickCheck

-- Representación de las pilas mediante listas.
newtype Pila a = P [a]
  deriving Eq

-- (escribePila p) es la cadena correspondiente a la pila p. Por
-- ejemplo,
--    escribePila (apila 5 (apila 2 (apila 3 vacia))) == "5 | 2 | 3"
escribePila :: Show a => Pila a -> String
escribePila (P [])     = "-"
escribePila (P [x])    = show x
escribePila (P (x:xs)) = show x ++ " | " ++ escribePila (P xs)

-- Procedimiento de escritura de pilas.
instance Show a => Show (Pila a) where
  show = escribePila

-- Ejemplo de pila:
--    λ> apila 1 (apila 2 (apila 3 vacia))
--    1 | 2 | 3

-- vacia es la pila vacía. Por ejemplo,
--    λ> vacia
--    -
vacia   :: Pila a
vacia = P []

-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por
-- ejemplo,
--    λ> apila 4 (apila 3 (apila 2 (apila 5 vacia)))
--    4 | 3 | 2 | 5
apila :: a -> Pila a -> Pila a
apila x (P xs) = P (x:xs)

-- (cima p) es la cima de la pila p. Por ejemplo,
--    λ> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia))))
--    4
cima :: Pila a -> a
cima (P [])    = error "cima de la pila vacia"
cima (P (x:_)) = x

-- (desapila p) es la pila obtenida suprimiendo la cima de la pila
-- p. Por ejemplo,
--    λ> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))
--    3 | 2 | 5
desapila :: Pila a -> Pila a
desapila (P [])     = error "desapila la pila vacia"
desapila (P (_:xs)) = P  xs

-- (esVacia p) se verifica si p es la pila vacía. Por ejemplo,
--    esVacia (apila 1 (apila 2 (apila 3 vacia))) ==  False
--    esVacia vacia                               ==  True
esVacia :: Pila a -> Bool
esVacia (P xs) = null xs

-- Generador de pilas                                          --
-- ==================

-- genPila es un generador de pilas. Por ejemplo,
--    λ> sample genPila
--    -
--    0|0|-
--    -
--    -6|4|-3|3|0|-
--    -
--    9|5|-1|-3|0|-8|-5|-7|2|-
--    -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-
--    2|-14|-5|2|-
--    5|9|-
--    -1|-14|5|-
--    6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-
genPila :: (Arbitrary a, Num a) => Gen (Pila a)
genPila = do
  xs <- listOf arbitrary
  return (foldr apila vacia xs)

-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Pila a) where
  arbitrary = genPila

-- Propiedades
-- ===========

-- Las propiedades son
prop_pilas :: Int -> Pila Int -> Bool
prop_pilas x p =
  cima (apila x p) == x &&
  desapila (apila x p) == p &&
  esVacia vacia &&
  not (esVacia (apila x p))

-- La comprobación e:
--    λ> quickCheck prop_pilas
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

module TAD.PilaConListas

(Pila,

vacia, -- Pila a

apila, -- a -> Pila a -> Pila a

cima, -- Pila a -> a

desapila, -- Pila a -> Pila a

esVacia, -- Pila a -> Bool

escribePila -- Show a => Pila a -> String

) where

import Test.QuickCheck

-- Representación de las pilas mediante listas.

newtype Pila a = P [a]

deriving Eq

-- (escribePila p) es la cadena correspondiente a la pila p. Por

-- ejemplo,

-- escribePila (apila 5 (apila 2 (apila 3 vacia))) == "5 | 2 | 3"

escribePila :: Show a => Pila a -> String

escribePila (P []) = "-"

escribePila (P [x]) = show x

escribePila (P (x:xs)) = show x ++ " | " ++ escribePila (P xs)

-- Procedimiento de escritura de pilas.

instance Show a => Show (Pila a) where

show = escribePila

-- Ejemplo de pila:

-- λ> apila 1 (apila 2 (apila 3 vacia))

-- 1 | 2 | 3

-- vacia es la pila vacía. Por ejemplo,

-- λ> vacia

-- -

vacia :: Pila a

vacia = P []

-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por

-- ejemplo,

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

-- 4 | 3 | 2 | 5

apila :: a -> Pila a -> Pila a

apila x (P xs) = P (x:xs)

-- (cima p) es la cima de la pila p. Por ejemplo,

-- λ> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia))))

-- 4

cima :: Pila a -> a

cima (P []) = error "cima de la pila vacia"

cima (P (x:_)) = x

-- (desapila p) es la pila obtenida suprimiendo la cima de la pila

-- p. Por ejemplo,

-- λ> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))

-- 3 | 2 | 5

desapila :: Pila a -> Pila a

desapila (P []) = error "desapila la pila vacia"

desapila (P (_:xs)) = P xs

-- (esVacia p) se verifica si p es la pila vacía. Por ejemplo,

-- esVacia (apila 1 (apila 2 (apila 3 vacia))) == False

-- esVacia vacia == True

esVacia :: Pila a -> Bool

esVacia (P xs) = null xs

-- Generador de pilas --

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

-- genPila es un generador de pilas. Por ejemplo,

-- λ> sample genPila

-- -

-- 0|0|-

-- -

-- -6|4|-3|3|0|-

-- -

-- 9|5|-1|-3|0|-8|-5|-7|2|-

-- -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-

-- 2|-14|-5|2|-

-- 5|9|-

-- -1|-14|5|-

-- 6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-

genPila :: (Arbitrary a, Num a) => Gen (Pila a)

genPila = do

xs <- listOf arbitrary

return (foldr apila vacia xs)

-- El tipo pila es una instancia del arbitrario.

instance (Arbitrary a, Num a) => Arbitrary (Pila a) where

arbitrary = genPila

-- Propiedades

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

-- Las propiedades son

prop_pilas :: Int -> Pila Int -> Bool

prop_pilas x p =

cima (apila x p) == x &&

desapila (apila x p) == p &&

esVacia vacia &&

not (esVacia (apila x p))

-- La comprobación e:

-- λ> quickCheck prop_pilas

-- +++ OK, passed 100 tests.

2.3. Implementación de las pilas mediante sucesiones

La implementación (que usa la librería Data.Sequence) se encuentra en el módulo PilaConSucesiones.hs cuyo contenido es el siguiente:

module TAD.PilaConSucesiones
  (Pila,
   vacia,      -- Pila a
   apila,      -- a -> Pila a -> Pila a
   cima,       -- Pila a -> a
   desapila,   -- Pila a -> Pila a
   esVacia,    -- Pila a -> Bool
   escribePila -- Show a => Pila a -> String
  ) where

import Data.Sequence as S
import Test.QuickCheck

-- Representación de las pilas mediante sucesiones.
newtype Pila a = P (Seq a)
  deriving Eq

-- (escribePila p) es la cadena correspondiente a la pila p. Por
-- ejemplo,
--    escribePila (apila 5 (apila 2 (apila 3 vacia))) == "5 | 2 | 3"
escribePila :: Show a => Pila a -> String
escribePila (P xs) = case viewl xs of
    EmptyL   -> "-"
    x :< xs' -> case viewl xs' of
        EmptyL -> show x
        _      -> show x ++ " | " ++ escribePila (P xs')

-- Procedimiento de escritura de pilas.
instance Show a => Show (Pila a) where
  show = escribePila

-- Ejemplo de pila:
--    λ> apila 1 (apila 2 (apila 3 vacia))
--    1 | 2 | 3

-- vacia es la pila vacía. Por ejemplo,
--    λ> vacia
--    -
vacia   :: Pila a
vacia = P empty

-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por
-- ejemplo,
--    λ> apila 4 (apila 3 (apila 2 (apila 5 vacia)))
--    5 | 2 | 3 | 4
apila :: a -> Pila a -> Pila a
apila x (P xs) = P (x <| xs)

-- (cima p) es la cima de la pila p. Por ejemplo,
--    λ> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia))))
--    4
cima :: Pila a -> a
cima (P xs) = case viewl xs of
  EmptyL -> error "cima de la pila vacia"
  x :< _ -> x

-- (desapila p) es la pila obtenida suprimiendo la cima de la pila
-- p. Por ejemplo,
--    λ> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))
--    3 | 2 | 5
desapila :: Pila a -> Pila a
desapila (P xs) = case viewl xs of
  EmptyL   -> error "desapila la pila vacia"
  _ :< xs' -> P xs'

-- (esVacia p) se verifica si p es la pila vacía. Por ejemplo,
--    esVacia (apila 1 (apila 2 (apila 3 vacia))) ==  False
--    esVacia vacia                               ==  True
esVacia :: Pila a -> Bool
esVacia (P xs) = S.null xs

-- Generador de pilas                                          --
-- ==================

-- genPila es un generador de pilas. Por ejemplo,
--    λ> sample genPila
--    -
--    0|0|-
--    -
--    -6|4|-3|3|0|-
--    -
--    9|5|-1|-3|0|-8|-5|-7|2|-
--    -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-
--    2|-14|-5|2|-
--    5|9|-
--    -1|-14|5|-
--    6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-
genPila :: (Arbitrary a, Num a) => Gen (Pila a)
genPila = do
  xs <- listOf arbitrary
  return (foldr apila vacia xs)

-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Pila a) where
  arbitrary = genPila

-- Propiedades
-- ===========

-- Las propiedades son
prop_pilas :: Int -> Pila Int -> Bool
prop_pilas x p =
  cima (apila x p) == x &&
  desapila (apila x p) == p &&
  esVacia vacia &&
  not (esVacia (apila x p))

-- La comprobación e:
--    λ> quickCheck prop_pilas
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

module TAD.PilaConSucesiones

(Pila,

vacia, -- Pila a

apila, -- a -> Pila a -> Pila a

cima, -- Pila a -> a

desapila, -- Pila a -> Pila a

esVacia, -- Pila a -> Bool

escribePila -- Show a => Pila a -> String

) where

import Data.Sequence as S

import Test.QuickCheck

-- Representación de las pilas mediante sucesiones.

newtype Pila a = P (Seq a)

deriving Eq

-- (escribePila p) es la cadena correspondiente a la pila p. Por

-- ejemplo,

-- escribePila (apila 5 (apila 2 (apila 3 vacia))) == "5 | 2 | 3"

escribePila :: Show a => Pila a -> String

escribePila (P xs) = case viewl xs of

EmptyL -> "-"

x :< xs' -> case viewl xs' of

EmptyL -> show x

_ -> show x ++ " | " ++ escribePila (P xs')

-- Procedimiento de escritura de pilas.

instance Show a => Show (Pila a) where

show = escribePila

-- Ejemplo de pila:

-- λ> apila 1 (apila 2 (apila 3 vacia))

-- 1 | 2 | 3

-- vacia es la pila vacía. Por ejemplo,

-- λ> vacia

-- -

vacia :: Pila a

vacia = P empty

-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por

-- ejemplo,

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

-- 5 | 2 | 3 | 4

apila :: a -> Pila a -> Pila a

apila x (P xs) = P (x <| xs)

-- (cima p) es la cima de la pila p. Por ejemplo,

-- λ> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia))))

-- 4

cima :: Pila a -> a

cima (P xs) = case viewl xs of

EmptyL -> error "cima de la pila vacia"

x :< _ -> x

-- (desapila p) es la pila obtenida suprimiendo la cima de la pila

-- p. Por ejemplo,

-- λ> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))

-- 3 | 2 | 5

desapila :: Pila a -> Pila a

desapila (P xs) = case viewl xs of

EmptyL -> error "desapila la pila vacia"

_ :< xs' -> P xs'

-- (esVacia p) se verifica si p es la pila vacía. Por ejemplo,

-- esVacia (apila 1 (apila 2 (apila 3 vacia))) == False

-- esVacia vacia == True

esVacia :: Pila a -> Bool

esVacia (P xs) = S.null xs

-- Generador de pilas --

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

-- genPila es un generador de pilas. Por ejemplo,

-- λ> sample genPila

-- -

-- 0|0|-

-- -

-- -6|4|-3|3|0|-

-- -

-- 9|5|-1|-3|0|-8|-5|-7|2|-

-- -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-

-- 2|-14|-5|2|-

-- 5|9|-

-- -1|-14|5|-

-- 6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-

genPila :: (Arbitrary a, Num a) => Gen (Pila a)

genPila = do

xs <- listOf arbitrary

return (foldr apila vacia xs)

-- El tipo pila es una instancia del arbitrario.

instance (Arbitrary a, Num a) => Arbitrary (Pila a) where

arbitrary = genPila

-- Propiedades

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

-- Las propiedades son

prop_pilas :: Int -> Pila Int -> Bool

prop_pilas x p =

cima (apila x p) == x &&

desapila (apila x p) == p &&

esVacia vacia &&

not (esVacia (apila x p))

-- La comprobación e:

-- λ> quickCheck prop_pilas

-- +++ OK, passed 100 tests.

3. Las pilas en Python

3.1. El tipo abstracto de las pilas en Python

La implementación se encuentra en el módulo pila.py cuyo contenido es el siguiente:

__all__ = [
    'Pila',
    'vacia',
    'apila',
    'esVacia',
    'cima',
    'desapila',
    'pilaAleatoria'
]
from src.TAD.pilaConListas import (Pila, vacia, apila, esVacia, cima,
                                   desapila, pilaAleatoria)
# from src.TAD.pilaConDeque import (Pila, vacia, apila, esVacia, cima,
#                                   desapila, pilaAleatoria)

__all__ = [

'Pila',

'vacia',

'apila',

'esVacia',

'cima',

'desapila',

'pilaAleatoria'

]

from src.TAD.pilaConListas import (Pila, vacia, apila, esVacia, cima,

desapila, pilaAleatoria)

# from src.TAD.pilaConDeque import (Pila, vacia, apila, esVacia, cima,

# desapila, pilaAleatoria)

3.2. Implementación de las pilas mediante listas

La implementación se encuentra en el módulo pilaConListas.py en el que se define la clase Pila con los siguientes métodos:

apila(x) añade x al principio de la pila.
cima() devuelve la cima de la pila.
desapila() elimina la cima de la pila.
esVacia() se verifica si la pila es vacía.

Por ejemplo,

   >>> p = Pila()
   >>> p
   -
   >>> p.apila(5)
   >>> p.apila(2)
   >>> p.apila(3)
   >>> p.apila(4)
   >>> p
   4 | 3 | 2 | 5
   >>> p.cima()
   4
   >>> p.desapila()
   >>> p
   3 | 2 | 5
   >>> p.esVacia()
   False
   >>> p = Pila()
   >>> p.esVacia()
   True

>>> p = Pila()

>>> p

>>> p.apila(5)

>>> p.apila(2)

>>> p.apila(3)

>>> p.apila(4)

>>> p

4 | 3 | 2 | 5

>>> p.cima()

>>> p.desapila()

>>> p

3 | 2 | 5

>>> p.esVacia()

False

>>> p = Pila()

>>> p.esVacia()

True

Además se definen las correspondientes funciones. Por ejemplo,

   >>> vacia()
   -
   >>> apila(4, apila(3, apila(2, apila(5, vacia()))))
   4 | 3 | 2 | 5
   >>> cima(apila(4, apila(3, apila(2, apila(5, vacia())))))
   4
   >>> desapila(apila(4, apila(3, apila(2, apila(5, vacia())))))
   3 | 2 | 5
   >>> esVacia(apila(4, apila(3, apila(2, apila(5, vacia())))))
   False
   >>> esVacia(vacia())
   True

>>> vacia()

>>> apila(4, apila(3, apila(2, apila(5, vacia()))))

4 | 3 | 2 | 5

>>> cima(apila(4, apila(3, apila(2, apila(5, vacia())))))

>>> desapila(apila(4, apila(3, apila(2, apila(5, vacia())))))

3 | 2 | 5

>>> esVacia(apila(4, apila(3, apila(2, apila(5, vacia())))))

False

>>> esVacia(vacia())

True

Finalmente, se define un generador aleatorio de pilas y se comprueba que las pilas cumplen las propiedades de su especificación.

__all__ = [
    'Pila',
    'vacia',
    'apila',
    'esVacia',
    'cima',
    'desapila',
    'pilaAleatoria'
]

from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las pilas mediante Listas
# ==================================

@dataclass
class Pila(Generic[A]):
    _elementos: list[A] = field(default_factory=list)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos de la pila separados por " | ".
        Si la pila está vacía, devuelve "-".
        """
        if len(self._elementos) == 0:
            return '-'
        return " | ".join(str(x) for x in self._elementos)

    def apila(self, x: A) -> None:
        """
        Agrega el elemento x al inicio de la pila.
        """
        self._elementos.insert(0, x)

    def esVacia(self) -> bool:
        """
        Verifica si la pila está vacía.

        Devuelve True si la pila está vacía, False en caso contrario.
        """
        return not self._elementos

    def cima(self) -> A:
        """
        Devuelve el elemento en la cima de la pila.
        """
        return self._elementos[0]

    def desapila(self) -> None:
        """
        Elimina el elemento en la cima de la pila.
        """
        self._elementos.pop(0)

# Funciones del tipo de las listas
# ================================

def vacia() -> Pila[A]:
    """
    Crea y devuelve una pila vacía de tipo A.
    """
    p: Pila[A] = Pila()
    return p

def apila(x: A, p: Pila[A]) -> Pila[A]:
    """
    Añade un elemento x al tope de la pila p y devuelve una copia de la
    pila modificada.
    """
    aux = deepcopy(p)
    aux.apila(x)
    return aux

def esVacia(p: Pila[A]) -> bool:
    """
    Devuelve True si la pila está vacía, False si no lo está.
    """
    return p.esVacia()

def cima(p: Pila[A]) -> A:
    """
    Devuelve el elemento en la cima de la pila p.
    """
    return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:
    """
    Elimina el elemento en la cima de la pilla p y devuelve una copia de la
    pila resultante.
    """
    aux = deepcopy(p)
    aux.desapila()
    return aux

# Generador de pilas
# ==================

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:
    """
    Genera una estrategia de búsqueda para generar pilas de enteros de
    forma aleatoria.

    Utiliza la librería Hypothesis para generar una lista de enteros y
    luego se convierte en una instancia de la clase pila.
    """
    return st.lists(st.integers()).map(Pila)

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

# Las propiedades son
@given(p=pilaAleatoria(), x=st.integers())
def test_pila(p: Pila[int], x: int) -> None:
    assert cima(apila(x, p)) == x
    assert desapila(apila(x, p)) == p
    assert esVacia(vacia())
    assert not esVacia(apila(x, p))

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

__all__ = [

'Pila',

'vacia',

'apila',

'esVacia',

'cima',

'desapila',

'pilaAleatoria'

]

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Generic, TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las pilas mediante Listas

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

@dataclass

class Pila(Generic[A]):

_elementos: list[A] = field(default_factory=list)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos de la pila separados por " | ".

Si la pila está vacía, devuelve "-".

"""

if len(self._elementos) == 0:

return '-'

return " | ".join(str(x) for x in self._elementos)

def apila(self, x: A) -> None:

"""

Agrega el elemento x al inicio de la pila.

"""

self._elementos.insert(0, x)

def esVacia(self) -> bool:

"""

Verifica si la pila está vacía.

Devuelve True si la pila está vacía, False en caso contrario.

"""

return not self._elementos

def cima(self) -> A:

"""

Devuelve el elemento en la cima de la pila.

"""

return self._elementos[0]

def desapila(self) -> None:

"""

Elimina el elemento en la cima de la pila.

"""

self._elementos.pop(0)

# Funciones del tipo de las listas

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

def vacia() -> Pila[A]:

"""

Crea y devuelve una pila vacía de tipo A.

"""

p: Pila[A] = Pila()

return p

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

"""

Añade un elemento x al tope de la pila p y devuelve una copia de la

pila modificada.

"""

aux = deepcopy(p)

aux.apila(x)

return aux

def esVacia(p: Pila[A]) -> bool:

"""

Devuelve True si la pila está vacía, False si no lo está.

"""

return p.esVacia()

def cima(p: Pila[A]) -> A:

"""

Devuelve el elemento en la cima de la pila p.

"""

return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:

"""

Elimina el elemento en la cima de la pilla p y devuelve una copia de la

pila resultante.

"""

aux = deepcopy(p)

aux.desapila()

return aux

# Generador de pilas

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

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:

"""

Genera una estrategia de búsqueda para generar pilas de enteros de

forma aleatoria.

Utiliza la librería Hypothesis para generar una lista de enteros y

luego se convierte en una instancia de la clase pila.

"""

return st.lists(st.integers()).map(Pila)

# Comprobación de las propiedades de las pilas

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

# Las propiedades son

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

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

assert cima(apila(x, p)) == x

assert desapila(apila(x, p)) == p

assert esVacia(vacia())

assert not esVacia(apila(x, p))

# La comprobación es

# > poetry run pytest -q pilaConListas.py

# 1 passed in 0.25s

3.3. Implementación de las pilas mediante deque

La implementación (que usa la librería deque) se encuentra en el módulo pilaConDeque.py y su contenido es el siguiente:

__all__ = [
    'Pila',
    'vacia',
    'apila',
    'esVacia',
    'cima',
    'desapila',
    'pilaAleatoria'
]

from collections import deque
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las pilas mediante listas
# ==================================

@dataclass
class Pila(Generic[A]):
    _elementos: deque[A] = field(default_factory=deque)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos de la pila separados por " | ".
        Si la pila está vacía, devuelve "-".
        """
        if len(self._elementos) == 0:
            return '-'
        return ' | '.join(str(x) for x in self._elementos)

    def apila(self, x: A) -> None:
        """
        Agrega el elemento x al inicio de la pila.
        """
        self._elementos.appendleft(x)

    def esVacia(self) -> bool:
        """
        Verifica si la pila está vacía.

        Devuelve True si la pila está vacía, False en caso contrario.
        """
        return len(self._elementos) == 0

    def cima(self) -> A:
        """
        Devuelve el elemento en la cima de la pila.
        """
        return self._elementos[0]

    def desapila(self) -> None:
        """
        Elimina el elemento en la cima de la pila.
        """
        self._elementos.popleft()

# Funciones del tipo de las listas
# ================================

def vacia() -> Pila[A]:
    """
    Crea y devuelve una pila vacía de tipo A.
    """
    p: Pila[A] = Pila()
    return p

def apila(x: A, p: Pila[A]) -> Pila[A]:
    """
    Añade un elemento x al tope de la pila p y devuelve una copia de la
    pila modificada.
    """
    _aux = deepcopy(p)
    _aux.apila(x)
    return _aux

def esVacia(p: Pila[A]) -> bool:
    """
    Devuelve True si la pila está vacía, False si no lo está.
    """
    return p.esVacia()

def cima(p: Pila[A]) -> A:
    """
    Devuelve el elemento en la cima de la pila p.
    """
    return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:
    """
    Elimina el elemento en la cima de la pilla p y devuelve una copia de la
    pila resultante.
    """
    _aux = deepcopy(p)
    _aux.desapila()
    return _aux

# Generador de pilas
# ==================

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:
    """
    Genera una estrategia de búsqueda para generar pilas de enteros de
    forma aleatoria.

    Utiliza la librería Hypothesis para generar una lista de enteros y
    luego se convierte en una instancia de la clase pila.
    """
    def _creaPila(elementos: list[int]) -> Pila[int]:
        pila: Pila[int] = vacia()
        pila._elementos.extendleft(elementos)
        return pila
    return st.builds(_creaPila, st.lists(st.integers()))

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

# Las propiedades son
@given(p=pilaAleatoria(), x=st.integers())
def test_pila(p: Pila[int], x: int) -> None:
    assert cima(apila(x, p)) == x
    assert desapila(apila(x, p)) == p
    assert esVacia(vacia())
    assert not esVacia(apila(x, p))

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

__all__ = [

'Pila',

'vacia',

'apila',

'esVacia',

'cima',

'desapila',

'pilaAleatoria'

]

from collections import deque

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Generic, TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar('A')

# Clase de las pilas mediante listas

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

@dataclass

class Pila(Generic[A]):

_elementos: deque[A] = field(default_factory=deque)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos de la pila separados por " | ".

Si la pila está vacía, devuelve "-".

"""

if len(self._elementos) == 0:

return '-'

return ' | '.join(str(x) for x in self._elementos)

def apila(self, x: A) -> None:

"""

Agrega el elemento x al inicio de la pila.

"""

self._elementos.appendleft(x)

def esVacia(self) -> bool:

"""

Verifica si la pila está vacía.

Devuelve True si la pila está vacía, False en caso contrario.

"""

return len(self._elementos) == 0

def cima(self) -> A:

"""

Devuelve el elemento en la cima de la pila.

"""

return self._elementos[0]

def desapila(self) -> None:

"""

Elimina el elemento en la cima de la pila.

"""

self._elementos.popleft()

# Funciones del tipo de las listas

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

def vacia() -> Pila[A]:

"""

Crea y devuelve una pila vacía de tipo A.

"""

p: Pila[A] = Pila()

return p

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

"""

Añade un elemento x al tope de la pila p y devuelve una copia de la

pila modificada.

"""

_aux = deepcopy(p)

_aux.apila(x)

return _aux

def esVacia(p: Pila[A]) -> bool:

"""

Devuelve True si la pila está vacía, False si no lo está.

"""

return p.esVacia()

def cima(p: Pila[A]) -> A:

"""

Devuelve el elemento en la cima de la pila p.

"""

return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:

"""

Elimina el elemento en la cima de la pilla p y devuelve una copia de la

pila resultante.

"""

_aux = deepcopy(p)

_aux.desapila()

return _aux

# Generador de pilas

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

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:

"""

Genera una estrategia de búsqueda para generar pilas de enteros de

forma aleatoria.

Utiliza la librería Hypothesis para generar una lista de enteros y

luego se convierte en una instancia de la clase pila.

"""

def _creaPila(elementos: list[int]) -> Pila[int]:

pila: Pila[int] = vacia()

pila._elementos.extendleft(elementos)

return pila

return st.builds(_creaPila, st.lists(st.integers()))

# Comprobación de las propiedades de las pilas

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

# Las propiedades son

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

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

assert cima(apila(x, p)) == x

assert desapila(apila(x, p)) == p

assert esVacia(vacia())

assert not esVacia(apila(x, p))

# La comprobación es

# > poetry run pytest -q pilaConQueue.py

# 1 passed in 0.25s

TAD de las colas: Todos los elementos verifican una propiedad

TAD de las colas: Longitud de una cola

TAD de las colas: Último elemento

TAD de las colas: Transformaciones entre colas y listas

El tipo abstracto de datos de las colas

1. El tipo abstracto de datos de las colas

2. Las colas en Haskell

2.1. El tipo abstracto de datos de las colas en Haskell

2.2. Implementación de las colas mediante listas

2.3. Implementación de las colas mediante pares de listas

2.4. Implementación de las colas mediante sucesiones

3. Las colas en Python

3.1. El tipo abstracto de las colas en Python

3.2. Implementación de las colas mediante listas

3.3. Implementación de las colas mediante pares de listas

3.4. Implementación de las colas mediante deque

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

TAD de las pilas: Ordenación de pilas por inserción

TAD de las pilas: Reconocimiento de ordenación de pilas

TAD de las pilas: Reconocimiento de subpilas

TAD de las pilas: Reconocimiento de prefijos de pilas

TAD de las pilas: Inclusión de pilas

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

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

TAD de las pilas: Transformaciones entre pilas y listas

El tipo abstracto de datos de las pilas

1. El tipo abstracto de datos de las pilas

2. Las pilas en Haskell

2.1. El tipo abstracto de datos de las pilas en Haskell

2.2. Implementación de las pilas mediante listas

2.3. Implementación de las pilas mediante sucesiones

3. Las pilas en Python

3.1. El tipo abstracto de las pilas en Python

3.2. Implementación de las pilas mediante listas

3.3. Implementación de las pilas mediante deque

Entradas recientes

Buscar

Correo electrónico