PFH: La semana en Exercitium (11 de febrero de 2023)

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

1. TAD de las pilas: Máximo elemento de una pila
2. El tipo abstracto de datos de las colas
3. TAD de las colas: Transformaciones entre colas y listas
4. TAD de las colas: Último elemento
5. TAD de las colas: Longitud de una cola

A continuación se muestran las soluciones.

1. TAD de las pilas: Máximo elemento de una pila

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

   maxPila :: Ord a => Pila a -> a

1	maxPila :: Ord a => Pila a -> a

tal que maxPila p sea el mayor de los elementos de la pila p. Por ejemplo,

   λ> maxPila (apila 3 (apila 5 (apila 1 vacia)))
   5

1 2	λ> maxPila (apila 3 (apila 5 (apila 1 vacia))) 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 (pilaAlista)
import Test.QuickCheck

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

maxPila1 :: Ord a => Pila a -> a
maxPila1 p
  | esVacia dp = cp
  | otherwise  = max cp (maxPila1 dp)
  where cp = cima p
        dp = desapila p

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

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

maxPila2 :: Ord a => Pila a -> a
maxPila2 =
  maximum . pilaAlista

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

-- La propiedad es
prop_maxPila :: Pila Int -> Property
prop_maxPila p =
  not (esVacia p) ==> maxPila1 p == maxPila2 p

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

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

import Transformaciones_pilas_listas (pilaAlista)

import Test.QuickCheck

-- 1ª solución

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

maxPila1 :: Ord a => Pila a -> a

maxPila1 p

| esVacia dp = cp

| otherwise = max cp (maxPila1 dp)

where cp = cima p

dp = desapila p

-- 2ª solución

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

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

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

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

maxPila2 :: Ord a => Pila a -> a

maxPila2 =

maximum . pilaAlista

-- Comprobación de equivalencia

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

-- La propiedad es

prop_maxPila :: Pila Int -> Property

prop_maxPila p =

not (esVacia p) ==> maxPila1 p == maxPila2 p

-- La comprobación es

-- λ> quickCheck prop_maxPila

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

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import assume, 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 maxPila1(p: Pila[A]) -> A:
    cp = cima(p)
    dp = desapila(p)
    if esVacia(dp):
        return cp
    return max(cp, maxPila1(dp))

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

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

def maxPila2(p: Pila[A]) -> A:
    return max(pilaAlista(p))

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

def maxPila3Aux(p: Pila[A]) -> A:
    cp = p.cima()
    p.desapila()
    if esVacia(p):
        return cp
    return max(cp, maxPila3Aux(p))

def maxPila3(p: Pila[A]) -> A:
    q = deepcopy(p)
    return maxPila3Aux(q)

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

def maxPila4Aux(p: Pila[A]) -> A:
    r = p.cima()
    while not esVacia(p):
        cp = p.cima()
        if cp > r:
            r = cp
        p.desapila()
    return r

def maxPila4(p: Pila[A]) -> A:
    q = deepcopy(p)
    return maxPila4Aux(q)

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

# La propiedad es
@given(p=pilaAleatoria())
def test_maxPila(p: Pila[int]) -> None:
    assume(not esVacia(p))
    r = maxPila1(p)
    assert maxPila2(p) == r
    assert maxPila3(p) == r
    assert maxPila4(p) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import assume, 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 maxPila1(p: Pila[A]) -> A:

cp = cima(p)

dp = desapila(p)

if esVacia(dp):

return cp

return max(cp, maxPila1(dp))

# 2ª solución

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

# Se usará la función pilaAlista del ejercicio

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

# https://bit.ly/3ZHewQ8

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

return max(pilaAlista(p))

# 3ª solución

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

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

cp = p.cima()

p.desapila()

if esVacia(p):

return cp

return max(cp, maxPila3Aux(p))

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

q = deepcopy(p)

return maxPila3Aux(q)

# 4ª solución

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

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

r = p.cima()

while not esVacia(p):

cp = p.cima()

if cp > r:

r = cp

p.desapila()

return r

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

q = deepcopy(p)

return maxPila4Aux(q)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(p=pilaAleatoria())

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

assume(not esVacia(p))

r = maxPila1(p)

assert maxPila2(p) == r

assert maxPila3(p) == r

assert maxPila4(p) == r

# La comprobación es

# src> poetry run pytest -q maxPila.py

# 1 passed in 0.25s

2. El tipo abstracto de datos de las colas

2.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.2. Las colas en Haskell

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

2.3. Las colas en Python

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

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

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

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

3. TAD de las colas: Transformaciones entre colas y listas

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

4. TAD de las colas: Último elemento

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

5. TAD de las colas: Longitud de una cola

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

1. TAD de las pilas: Máximo elemento de una pila

2. El tipo abstracto de datos de las colas

2.1. El tipo abstracto de datos de las colas

2.2. Las colas en Haskell

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

2.2.2. Implementación de las colas mediante listas

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

2.2.4. Implementación de las colas mediante sucesiones

2.3. Las colas en Python

2.3.1. El tipo abstracto de las colas en Python

2.3.2. Implementación de las colas mediante listas

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

2.3.4. Implementación de las colas mediante deque

3. TAD de las colas: Transformaciones entre colas y listas

4. TAD de las colas: Último elemento

5. TAD de las colas: Longitud de una cola

Se puede imprimir o compartir con