Colas

TAD de las colas: Máximo elemento de una cola

PorJosé A. Alonso 27-febrero-202327-enero-2023

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

   maxCola :: Ord a => Cola a -> a

1	maxCola :: Ord a => Cola a -> a

tal que maxCola c sea el mayor de los elementos de la cola c. Por ejemplo,

   λ> maxCola (inserta 3 (inserta 5 (inserta 1 vacia)))
   5

1 2	λ> maxCola (inserta 3 (inserta 5 (inserta 1 vacia))) 5

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

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

maxCola1 :: Ord a => Cola a -> a
maxCola1 c
  | esVacia rc = pc
  | otherwise  = max pc (maxCola1 rc)
  where pc = primero c
        rc = resto c

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

maxCola2 :: Ord a => Cola a -> a
maxCola2 =
  maximum . 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_maxCola :: Cola Int -> Property
prop_maxCola c =
  not (esVacia c) ==> maxCola1 c == maxCola2 c

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

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

import Transformaciones_colas_listas (colaAlista)

import Test.QuickCheck

-- 1ª solución

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

maxCola1 :: Ord a => Cola a -> a

maxCola1 c

| esVacia rc = pc

| otherwise = max pc (maxCola1 rc)

where pc = primero c

rc = resto c

-- 2ª solución

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

maxCola2 :: Ord a => Cola a -> a

maxCola2 =

maximum . 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_maxCola :: Cola Int -> Property

prop_maxCola c =

not (esVacia c) ==> maxCola1 c == maxCola2 c

-- La comprobación es

-- λ> quickCheck prop_maxCola

-- +++ 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', int, float, str)

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

def maxCola1(c: Cola[A]) -> A:
    pc = primero(c)
    rc = resto(c)
    if esVacia(rc):
        return pc
    return max(pc, maxCola1(rc))

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

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

def maxCola2(c: Cola[A]) -> A:
    return max(colaAlista(c))

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

def maxCola3Aux(c: Cola[A]) -> A:
    pc = c.primero()
    c.resto()
    if esVacia(c):
        return pc
    return max(pc, maxCola3Aux(c))

def maxCola3(c: Cola[A]) -> A:
    _c = deepcopy(c)
    return maxCola3Aux(_c)

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

def maxCola4Aux(c: Cola[A]) -> A:
    r = c.primero()
    while not esVacia(c):
        pc = c.primero()
        if pc > r:
            r = pc
        c.resto()
    return r

def maxCola4(c: Cola[A]) -> A:
    _c = deepcopy(c)
    return maxCola4Aux(_c)

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

# La propiedad es
@given(c=colaAleatoria())
def test_maxCola(c: Cola[int]) -> None:
    assume(not esVacia(c))
    r = maxCola1(c)
    assert maxCola2(c) == r
    assert maxCola3(c) == r
    assert maxCola4(c) == r

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

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', int, float, str)

# 1ª solución

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

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

pc = primero(c)

rc = resto(c)

if esVacia(rc):

return pc

return max(pc, maxCola1(rc))

# 2ª solución

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

# Se usará la función colaAlista del ejercicio

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

# https://bit.ly/3ZHewQ8

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

return max(colaAlista(c))

# 3ª solución

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

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

pc = c.primero()

c.resto()

if esVacia(c):

return pc

return max(pc, maxCola3Aux(c))

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

_c = deepcopy(c)

return maxCola3Aux(_c)

# 4ª solución

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

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

r = c.primero()

while not esVacia(c):

pc = c.primero()

if pc > r:

r = pc

c.resto()

return r

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

_c = deepcopy(c)

return maxCola4Aux(_c)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(c=colaAleatoria())

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

assume(not esVacia(c))

r = maxCola1(c)

assert maxCola2(c) == r

assert maxCola3(c) == r

assert maxCola4(c) == r

# La comprobación es

# src> poetry run pytest -q maxCola.py

# 1 passed in 0.30s

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

PorJosé A. Alonso 24-febrero-202327-enero-2023

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

   ordenadaCola :: Ord a => Cola a -> Bool

1	ordenadaCola :: Ord a => Cola a -> Bool

tal que ordenadaCola c se verifica si los elementos de la cola c están ordenados en orden creciente. Por ejemplo,

   ordenadaCola (inserta 6 (inserta 5 (inserta 1 vacia))) == True
   ordenadaCola (inserta 1 (inserta 0 (inserta 6 vacia))) == False

1 2	ordenadaCola (inserta 6 (inserta 5 (inserta 1 vacia))) == True ordenadaCola (inserta 1 (inserta 0 (inserta 6 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, esVacia, primero, resto)
import Transformaciones_colas_listas (colaAlista)
import Test.QuickCheck

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

ordenadaCola :: Ord a => Cola a -> Bool
ordenadaCola c
  | esVacia c  = True
  | esVacia rc = True
  | otherwise  = pc <= prc && ordenadaCola rc
  where pc  = primero c
        rc  = resto c
        prc = primero rc

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

ordenadaCola2 :: Ord a => Cola a -> Bool
ordenadaCola2 =
  ordenadaLista . colaAlista

-- (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)]

-- 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_ordenadaCola :: Cola Int -> Bool
prop_ordenadaCola c =
  ordenadaCola c == ordenadaCola2 c

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

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

import Transformaciones_colas_listas (colaAlista)

import Test.QuickCheck

-- 1ª solución

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

ordenadaCola :: Ord a => Cola a -> Bool

ordenadaCola c

| esVacia c = True

| esVacia rc = True

| otherwise = pc <= prc && ordenadaCola rc

where pc = primero c

rc = resto c

prc = primero rc

-- 2ª solución

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

ordenadaCola2 :: Ord a => Cola a -> Bool

ordenadaCola2 =

ordenadaLista . colaAlista

-- (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)]

-- 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_ordenadaCola :: Cola Int -> Bool

prop_ordenadaCola c =

ordenadaCola c == ordenadaCola2 c

-- La comprobación es

-- λ> quickCheck prop_ordenadaCola

-- +++ 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, primero,
                          resto, vacia)
from src.transformaciones_colas_listas import colaAlista

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

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

def ordenadaCola(c: Cola[A]) -> bool:
    if esVacia(c):
        return True
    pc = primero(c)
    rc = resto(c)
    if esVacia(rc):
        return True
    prc = primero(rc)
    return pc <= prc and ordenadaCola(rc)

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

# 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 ordenadaCola2(p: Cola[A]) -> bool:
    return ordenadaLista(colaAlista(p))

# 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 ordenadaCola3Aux(c: Cola[A]) -> bool:
    if c.esVacia():
        return True
    pc = c.primero()
    c.resto()
    if c.esVacia():
        return True
    return pc <= c.primero() and ordenadaCola3Aux(c)

def ordenadaCola3(c: Cola[A]) -> bool:
    _c = deepcopy(c)
    return ordenadaCola3Aux(_c)

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

def ordenadaCola4Aux(c: Cola[A]) -> bool:
    while not c.esVacia():
        pc = c.primero()
        c.resto()
        if not c.esVacia() and pc > c.primero():
            return False
    return True

def ordenadaCola4(c: Cola[A]) -> bool:
    _c = deepcopy(c)
    return ordenadaCola4Aux(_c)

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

# La propiedad es
@given(p=colaAleatoria())
def test_ordenadaCola(p: Cola[int]) -> None:
    r = ordenadaCola(p)
    assert ordenadaCola2(p) == r
    assert ordenadaCola3(p) == r
    assert ordenadaCola4(p) == r

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

from copy import deepcopy

from typing import 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', int, float, str)

# 1ª solución

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

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

if esVacia(c):

return True

pc = primero(c)

rc = resto(c)

if esVacia(rc):

return True

prc = primero(rc)

return pc <= prc and ordenadaCola(rc)

# 2ª solución

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

# 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 ordenadaCola2(p: Cola[A]) -> bool:

return ordenadaLista(colaAlista(p))

# 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 ordenadaCola3Aux(c: Cola[A]) -> bool:

if c.esVacia():

return True

pc = c.primero()

c.resto()

if c.esVacia():

return True

return pc <= c.primero() and ordenadaCola3Aux(c)

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

_c = deepcopy(c)

return ordenadaCola3Aux(_c)

# 4ª solución

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

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

while not c.esVacia():

pc = c.primero()

c.resto()

if not c.esVacia() and pc > c.primero():

return False

return True

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

_c = deepcopy(c)

return ordenadaCola4Aux(_c)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(p=colaAleatoria())

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

r = ordenadaCola(p)

assert ordenadaCola2(p) == r

assert ordenadaCola3(p) == r

assert ordenadaCola4(p) == r

# La comprobación es

# src> poetry run pytest -q ordenadaCola.py

# 1 passed in 0.27s

TAD de las colas: Reconocimiento de subcolas

PorJosé A. Alonso 23-febrero-202327-enero-2023

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

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

1	subCola :: Eq a => Cola a -> Cola a -> Bool

tal que subCola c1 c2 se verifica si c1 es una subcola de c2. Por ejemplo,

   λ> ej1 = inserta 2 (inserta 3 vacia)
   λ> ej2 = inserta 7 (inserta 2 (inserta 3 (inserta 5 vacia)))
   λ> ej3 = inserta 2 (inserta 7 (inserta 3 (inserta 5 vacia)))
   λ> subCola ej1 ej2
   True
   λ> subCola ej1 ej3
   False

λ> ej1 = inserta 2 (inserta 3 vacia)

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

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

λ> subCola ej1 ej2

True

λ> subCola ej1 ej3

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, esVacia, primero, resto)
import Transformaciones_colas_listas (colaAlista)
import PrefijoCola (prefijoCola)
import Data.List (isPrefixOf, tails)
import Test.QuickCheck

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

subCola1 :: Eq a => Cola a -> Cola a -> Bool
subCola1 c1 c2
    | esVacia c1 = True
    | esVacia c2 = False
    | pc1 == pc2 = prefijoCola rc1 rc2 || subCola1 c1 rc2
    | otherwise  = subCola1 c1 rc2
    where pc1 = primero c1
          rc1 = resto c1
          pc2 = primero c2
          rc2 = resto c2

-- La función PrefijoCola está definida en el ejercicio
-- "Reconocimiento de prefijos de colas" que se encuentra en
-- https://bit.ly/3HaK20x

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

subCola2 :: Eq a => Cola a -> Cola a -> Bool
subCola2 c1 c2 =
  sublista (colaAlista c1) (colaAlista c2)

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

-- (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_subCola :: Cola Int -> Cola Int -> Bool
prop_subCola c1 c2 =
  subCola1 c1 c2 == subCola2 c1 c2

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

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

import Transformaciones_colas_listas (colaAlista)

import PrefijoCola (prefijoCola)

import Data.List (isPrefixOf, tails)

import Test.QuickCheck

-- 1ª solución

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

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

subCola1 c1 c2

| esVacia c1 = True

| esVacia c2 = False

| pc1 == pc2 = prefijoCola rc1 rc2 || subCola1 c1 rc2

| otherwise = subCola1 c1 rc2

where pc1 = primero c1

rc1 = resto c1

pc2 = primero c2

rc2 = resto c2

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

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

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

-- 2ª solución

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

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

subCola2 c1 c2 =

sublista (colaAlista c1) (colaAlista c2)

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

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

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

-- (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_subCola :: Cola Int -> Cola Int -> Bool

prop_subCola c1 c2 =

subCola1 c1 c2 == subCola2 c1 c2

-- La comprobación es

-- λ> quickCheck prop_subCola

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.prefijoCola import prefijoCola
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 subCola1(c1: Cola[A], c2: Cola[A]) -> bool:
    if esVacia(c1):
        return True
    if esVacia(c2):
        return False
    pc1 = primero(c1)
    rc1 = resto(c1)
    pc2 = primero(c2)
    rc2 = resto(c2)
    if pc1 == pc2:
        return prefijoCola(rc1, rc2) or subCola1(c1, rc2)
    return subCola1(c1, rc2)

# La función prefijoCola está definida en el ejercicio
# "Reconocimiento de prefijos de colas" que se encuentra en
# https://bit.ly/3HaK20x

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

# 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 subCola2(c1: Cola[A], c2: Cola[A]) -> bool:
    return sublista(colaAlista(c1), colaAlista(c2))

# 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 subCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    if c1.esVacia():
        return True
    if c2.esVacia():
        return False
    if c1.primero() != c2.primero():
        c2.resto()
        return subCola3Aux(c1, c2)
    q1 = deepcopy(c1)
    c1.resto()
    c2.resto()
    return prefijoCola(c1, c2) or subCola3Aux(q1, c2)

def subCola3(c1: Cola[A], c2: Cola[A]) -> bool:
    q1 = deepcopy(c1)
    q2 = deepcopy(c2)
    return subCola3Aux(q1, q2)

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

# La propiedad es
@given(c1=colaAleatoria(), c2=colaAleatoria())
def test_subCola(c1: Cola[int], c2: Cola[int]) -> None:
    r = subCola1(c1, c2)
    assert subCola2(c1, c2) == r
    assert subCola3(c1, c2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.prefijoCola import prefijoCola

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 subCola1(c1: Cola[A], c2: Cola[A]) -> bool:

if esVacia(c1):

return True

if esVacia(c2):

return False

pc1 = primero(c1)

rc1 = resto(c1)

pc2 = primero(c2)

rc2 = resto(c2)

if pc1 == pc2:

return prefijoCola(rc1, rc2) or subCola1(c1, rc2)

return subCola1(c1, rc2)

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

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

# https://bit.ly/3HaK20x

# 2ª solución

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

# 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 subCola2(c1: Cola[A], c2: Cola[A]) -> bool:

return sublista(colaAlista(c1), colaAlista(c2))

# 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 subCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:

if c1.esVacia():

return True

if c2.esVacia():

return False

if c1.primero() != c2.primero():

c2.resto()

return subCola3Aux(c1, c2)

q1 = deepcopy(c1)

c1.resto()

c2.resto()

return prefijoCola(c1, c2) or subCola3Aux(q1, c2)

def subCola3(c1: Cola[A], c2: Cola[A]) -> bool:

q1 = deepcopy(c1)

q2 = deepcopy(c2)

return subCola3Aux(q1, q2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(c1=colaAleatoria(), c2=colaAleatoria())

def test_subCola(c1: Cola[int], c2: Cola[int]) -> None:

r = subCola1(c1, c2)

assert subCola2(c1, c2) == r

assert subCola3(c1, c2) == r

# La comprobación es

# src> poetry run pytest -q subCola.py

# 1 passed in 0.31s

TAD de las colas: Reconocimiento de prefijos de colas

PorJosé A. Alonso 22-febrero-202327-enero-2023

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

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

1	prefijoCola :: Eq a => Cola a -> Cola a -> Bool

tal que prefijoCola c1 c2 se verifica si la cola c1 es justamente un prefijo de la cola c2. Por ejemplo,

   λ> ej1 = inserta 4 (inserta 2 vacia)
   λ> ej2 = inserta 5 (inserta 4 (inserta 2 vacia))
   λ> ej3 = inserta 5 (inserta 2 (inserta 4 vacia))
   λ> prefijoCola ej1 ej2
   True
   λ> prefijoCola ej1 ej3
   False

λ> ej1 = inserta 4 (inserta 2 vacia)

λ> ej2 = inserta 5 (inserta 4 (inserta 2 vacia))

λ> ej3 = inserta 5 (inserta 2 (inserta 4 vacia))

λ> prefijoCola ej1 ej2

True

λ> prefijoCola ej1 ej3

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, esVacia, primero, resto)
import Transformaciones_colas_listas (colaAlista)
import Data.List (isPrefixOf)
import Test.QuickCheck

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

prefijoCola :: Eq a => Cola a -> Cola a -> Bool
prefijoCola c1 c2
  | esVacia c1 = True
  | esVacia c2 = False
  | otherwise  = primero c1 == primero c2 &&
                 prefijoCola (resto c1) (resto c2)

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

prefijoCola2 :: Eq a => Cola a -> Cola a -> Bool
prefijoCola2 c1 c2 =
  colaAlista c1 `isPrefixOf` colaAlista c2

-- 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_prefijoCola :: Cola Int -> Cola Int -> Bool
prop_prefijoCola c1 c2 =
  prefijoCola c1 c2 == prefijoCola2 c1 c2

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

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

import Transformaciones_colas_listas (colaAlista)

import Data.List (isPrefixOf)

import Test.QuickCheck

-- 1ª solución

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

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

prefijoCola c1 c2

| esVacia c1 = True

| esVacia c2 = False

| otherwise = primero c1 == primero c2 &&

prefijoCola (resto c1) (resto c2)

-- 2ª solución

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

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

prefijoCola2 c1 c2 =

colaAlista c1 `isPrefixOf` colaAlista c2

-- 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_prefijoCola :: Cola Int -> Cola Int -> Bool

prop_prefijoCola c1 c2 =

prefijoCola c1 c2 == prefijoCola2 c1 c2

-- La comprobación es

-- λ> quickCheck prop_prefijoCola

-- +++ 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, primero,
                          resto, vacia)
from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

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

def prefijoCola(c1: Cola[A], c2: Cola[A]) -> bool:
    if esVacia(c1):
        return True
    if esVacia(c2):
        return False
    return primero(c1) == primero(c2) and prefijoCola(resto(c1), resto(c2))

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

def esPrefijoLista(xs: list[A], ys: list[A]) -> bool:
    return ys[:len(xs)] == xs

def prefijoCola2(c1: Cola[A], c2: Cola[A]) -> bool:
    return esPrefijoLista(colaAlista(c1), colaAlista(c2))

# 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 prefijoCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    if c1.esVacia():
        return True
    if c2.esVacia():
        return False
    cc1 = c1.primero()
    c1.resto()
    cc2 = c2.primero()
    c2.resto()
    return cc1 == cc2 and prefijoCola3(c1, c2)

def prefijoCola3(c1: Cola[A], c2: Cola[A]) -> bool:
    q1 = deepcopy(c1)
    q2 = deepcopy(c2)
    return prefijoCola3Aux(q1, q2)

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

def prefijoCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    while not c2.esVacia() and not c1.esVacia():
        if c1.primero() != c2.primero():
            return False
        c1.resto()
        c2.resto()
    return c1.esVacia()

def prefijoCola4(c1: Cola[A], c2: Cola[A]) -> bool:
    q1 = deepcopy(c1)
    q2 = deepcopy(c2)
    return prefijoCola4Aux(q1, q2)

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

# La propiedad es
@given(c1=colaAleatoria(), c2=colaAleatoria())
def test_prefijoCola(c1: Cola[int], c2: Cola[int]) -> None:
    r = prefijoCola(c1, c2)
    assert prefijoCola2(c1, c2) == r
    assert prefijoCola3(c1, c2) == r
    assert prefijoCola4(c1, c2) == r

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

from copy import deepcopy

from typing import 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 prefijoCola(c1: Cola[A], c2: Cola[A]) -> bool:

if esVacia(c1):

return True

if esVacia(c2):

return False

return primero(c1) == primero(c2) and prefijoCola(resto(c1), resto(c2))

# 2ª solución

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

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

return ys[:len(xs)] == xs

def prefijoCola2(c1: Cola[A], c2: Cola[A]) -> bool:

return esPrefijoLista(colaAlista(c1), colaAlista(c2))

# 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 prefijoCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:

if c1.esVacia():

return True

if c2.esVacia():

return False

cc1 = c1.primero()

c1.resto()

cc2 = c2.primero()

c2.resto()

return cc1 == cc2 and prefijoCola3(c1, c2)

def prefijoCola3(c1: Cola[A], c2: Cola[A]) -> bool:

q1 = deepcopy(c1)

q2 = deepcopy(c2)

return prefijoCola3Aux(q1, q2)

# 4ª solución

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

def prefijoCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool:

while not c2.esVacia() and not c1.esVacia():

if c1.primero() != c2.primero():

return False

c1.resto()

c2.resto()

return c1.esVacia()

def prefijoCola4(c1: Cola[A], c2: Cola[A]) -> bool:

q1 = deepcopy(c1)

q2 = deepcopy(c2)

return prefijoCola4Aux(q1, q2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(c1=colaAleatoria(), c2=colaAleatoria())

def test_prefijoCola(c1: Cola[int], c2: Cola[int]) -> None:

r = prefijoCola(c1, c2)

assert prefijoCola2(c1, c2) == r

assert prefijoCola3(c1, c2) == r

assert prefijoCola4(c1, c2) == r

# La comprobación es

# src> poetry run pytest -q prefijoCola.py

# 1 passed in 0.29s

TAD de las colas: Inclusión de colas

PorJosé A. Alonso 21-febrero-202327-enero-2023

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

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

1	contenidaCola :: Eq a => Cola a -> Cola a -> Bool

tal que contenidaCola c1 c2 se verifica si todos los elementos de la cola c1 son elementos de la cola c2. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 2 vacia)
   λ> ej2 = inserta 3 (inserta 4 vacia)
   λ> ej3 = inserta 5 (inserta 2 (inserta 3 vacia))
   λ> contenidaCola ej1 ej3
   True
   λ> contenidaCola ej2 ej3
   False

λ> ej1 = inserta 3 (inserta 2 vacia)

λ> ej2 = inserta 3 (inserta 4 vacia)

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

λ> contenidaCola ej1 ej3

True

λ> contenidaCola ej2 ej3

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, esVacia, primero, resto)
import PerteneceCola (perteneceCola)
import Transformaciones_colas_listas (colaAlista)
import Test.QuickCheck

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

contenidaCola1 :: Eq a => Cola a -> Cola a -> Bool
contenidaCola1 c1 c2
  | esVacia c1 = True
  | otherwise  = perteneceCola (primero c1) c2 &&
                 contenidaCola1 (resto c1) c2

-- La función perteneceCola está definida en el ejercicio
-- "TAD de las colas: Pertenencia a una cola" que se encuentra en
-- https://bit.ly/3RcVgqb

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

contenidaCola2 :: Eq a => Cola a -> Cola a -> Bool
contenidaCola2 c1 c2 =
  contenidaLista (colaAlista c1) (colaAlista c2)

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

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

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

-- La propiedad es
prop_contenidaCola :: Cola Int -> Cola Int -> Bool
prop_contenidaCola c1 c2 =
  contenidaCola1 c1 c2 == contenidaCola2 c1 c2

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

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

import PerteneceCola (perteneceCola)

import Transformaciones_colas_listas (colaAlista)

import Test.QuickCheck

-- 1ª solución

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

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

contenidaCola1 c1 c2

| esVacia c1 = True

| otherwise = perteneceCola (primero c1) c2 &&

contenidaCola1 (resto c1) c2

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

-- "TAD de las colas: Pertenencia a una cola" que se encuentra en

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

-- 2ª solución

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

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

contenidaCola2 c1 c2 =

contenidaLista (colaAlista c1) (colaAlista c2)

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

-- "TAD de las colas: Transformaciones entre colas y listas" que se

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

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

contenidaLista xs ys =

all (`elem` ys) xs

-- Comprobación de equivalencia

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

-- La propiedad es

prop_contenidaCola :: Cola Int -> Cola Int -> Bool

prop_contenidaCola c1 c2 =

contenidaCola1 c1 c2 == contenidaCola2 c1 c2

-- La comprobación es

-- λ> quickCheck prop_contenidaCola

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.perteneceCola import perteneceCola
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 contenidaCola1(c1: Cola[A], c2: Cola[A]) -> bool:
    if esVacia(c1):
        return True
    return perteneceCola(primero(c1), c2) and contenidaCola1(resto(c1), c2)

# L función perteneceCola está definida en el ejercicio
# "Pertenencia a una cola" que se encuentra en
# https://bit.ly/3RcVgqb

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

def contenidaCola2(c1: Cola[A], c2: Cola[A]) -> bool:
    return set(colaAlista(c1)) <= set(colaAlista(c2))

# 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 contenidaCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    if c1.esVacia():
        return True
    pc1 = c1.primero()
    c1.resto()
    return perteneceCola(pc1, c2) and contenidaCola1(c1, c2)

def contenidaCola3(c1: Cola[A], c2: Cola[A]) -> bool:
    _c1 = deepcopy(c1)
    return contenidaCola3Aux(_c1, c2)

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

def contenidaCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    while not c1.esVacia():
        pc1 = c1.primero()
        c1.resto()
        if not perteneceCola(pc1, c2):
            return False
    return True

def contenidaCola4(c1: Cola[A], c2: Cola[A]) -> bool:
    _c1 = deepcopy(c1)
    return contenidaCola4Aux(_c1, c2)

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

# La propiedad es
@given(c1=colaAleatoria(), c2=colaAleatoria())
def test_contenidaCola(c1: Cola[int], c2: Cola[int]) -> None:
    r = contenidaCola1(c1, c2)
    assert contenidaCola2(c1, c2) == r
    assert contenidaCola3(c1, c2) == r
    assert contenidaCola4(c1, c2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.perteneceCola import perteneceCola

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 contenidaCola1(c1: Cola[A], c2: Cola[A]) -> bool:

if esVacia(c1):

return True

return perteneceCola(primero(c1), c2) and contenidaCola1(resto(c1), c2)

# L función perteneceCola está definida en el ejercicio

# "Pertenencia a una cola" que se encuentra en

# https://bit.ly/3RcVgqb

# 2ª solución

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

def contenidaCola2(c1: Cola[A], c2: Cola[A]) -> bool:

return set(colaAlista(c1)) <= set(colaAlista(c2))

# 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 contenidaCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:

if c1.esVacia():

return True

pc1 = c1.primero()

c1.resto()

return perteneceCola(pc1, c2) and contenidaCola1(c1, c2)

def contenidaCola3(c1: Cola[A], c2: Cola[A]) -> bool:

_c1 = deepcopy(c1)

return contenidaCola3Aux(_c1, c2)

# 4ª solución

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

def contenidaCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool:

while not c1.esVacia():

pc1 = c1.primero()

c1.resto()

if not perteneceCola(pc1, c2):

return False

return True

def contenidaCola4(c1: Cola[A], c2: Cola[A]) -> bool:

_c1 = deepcopy(c1)

return contenidaCola4Aux(_c1, c2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(c1=colaAleatoria(), c2=colaAleatoria())

def test_contenidaCola(c1: Cola[int], c2: Cola[int]) -> None:

r = contenidaCola1(c1, c2)

assert contenidaCola2(c1, c2) == r

assert contenidaCola3(c1, c2) == r

assert contenidaCola4(c1, c2) == r

# La comprobación es

# src> poetry run pytest -q contenidaCola.py

# 1 passed in 0.44s

TAD de las colas: Pertenencia a una cola

PorJosé A. Alonso 20-febrero-202327-enero-2023

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

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

1	perteneceCola :: Eq a => a -> Cola a -> Bool

tal que perteneceCola x c se verifica si x es un elemento de la cola c. Por ejemplo,

   perteneceCola 2 (inserta 5 (inserta 2 (inserta 3 vacia))) == True
   perteneceCola 4 (inserta 5 (inserta 2 (inserta 3 vacia))) == False

1 2	perteneceCola 2 (inserta 5 (inserta 2 (inserta 3 vacia))) == True perteneceCola 4 (inserta 5 (inserta 2 (inserta 3 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
import Test.QuickCheck

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

perteneceCola :: Eq a => a -> Cola a -> Bool
perteneceCola x c
  | esVacia c = False
  | otherwise = x == primero(c) || perteneceCola x (resto c)

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

perteneceCola2 :: Eq a => a -> Cola a -> Bool
perteneceCola2 x c =
  x `elem` 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_perteneceCola :: Int -> Cola Int -> Bool
prop_perteneceCola x p =
  perteneceCola x p == perteneceCola2 x p

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

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

import Transformaciones_colas_listas colaAlista

import Test.QuickCheck

-- 1ª solución

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

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

perteneceCola x c

| esVacia c = False

| otherwise = x == primero(c) || perteneceCola x (resto c)

-- 2ª solución

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

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

perteneceCola2 x c =

x `elem` 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_perteneceCola :: Int -> Cola Int -> Bool

prop_perteneceCola x p =

perteneceCola x p == perteneceCola2 x p

-- La comprobación es

-- λ> quickCheck prop_perteneceCola

-- +++ 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, vacia, inserta, primero, resto, esVacia,
                          colaAleatoria)
from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

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

def perteneceCola(x: A, c: Cola[A]) -> bool:
    if esVacia(c):
        return False
    return x == primero(c) or perteneceCola(x, resto(c))

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

def perteneceCola2(x: A, c: Cola[A]) -> bool:
    return x in colaAlista(c)

# Las 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 perteneceCola3Aux(x: A, c: Cola[A]) -> bool:
    if c.esVacia():
        return False
    pc = c.primero()
    c.resto()
    return x == pc or perteneceCola3Aux(x, c)

def perteneceCola3(x: A, c: Cola[A]) -> bool:
    c1 = deepcopy(c)
    return perteneceCola3Aux(x, c1)

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

def perteneceCola4Aux(x: A, c: Cola[A]) -> bool:
    while not c.esVacia():
        pc = c.primero()
        c.resto()
        if x == pc:
            return True
    return False

def perteneceCola4(x: A, c: Cola[A]) -> bool:
    c1 = deepcopy(c)
    return perteneceCola4Aux(x, c1)

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

# La propiedad es
@given(x=st.integers(), c=colaAleatoria())
def test_perteneceCola(x: int, c: Cola[int]) -> None:
    r = perteneceCola(x, c)
    assert perteneceCola2(x, c) == r
    assert perteneceCola3(x, c) == r
    assert perteneceCola4(x, c) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

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

colaAleatoria)

from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

# 1ª solución

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

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

if esVacia(c):

return False

return x == primero(c) or perteneceCola(x, resto(c))

# 2ª solución

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

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

return x in colaAlista(c)

# Las 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 perteneceCola3Aux(x: A, c: Cola[A]) -> bool:

if c.esVacia():

return False

pc = c.primero()

c.resto()

return x == pc or perteneceCola3Aux(x, c)

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

c1 = deepcopy(c)

return perteneceCola3Aux(x, c1)

# 4ª solución

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

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

while not c.esVacia():

pc = c.primero()

c.resto()

if x == pc:

return True

return False

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

c1 = deepcopy(c)

return perteneceCola4Aux(x, c1)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

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

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

r = perteneceCola(x, c)

assert perteneceCola2(x, c) == r

assert perteneceCola3(x, c) == r

assert perteneceCola4(x, c) == r

# La comprobación es

# src> poetry run pytest -q perteneceCola.py

# 1 passed in 0.25s

TAD de las colas: Agrupación de colas

PorJosé A. Alonso 17-febrero-202327-enero-2023

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

   agrupaColas :: [Cola a] -> Cola a

1	agrupaColas :: [Cola a] -> Cola a

tal que agrupaColas [c1,c2,c3,...,cn] es la cola formada mezclando las colas de la lista como sigue: mezcla c1 con c2, el resultado con c3, el resultado con c4, y así sucesivamente. Por ejemplo,

   λ> ej1 = inserta 2 (inserta 5 vacia)
   λ> ej2 = inserta 3 (inserta 7 (inserta 4 vacia))
   λ> ej3 = inserta 9 (inserta 0 (inserta 1 (inserta 6 vacia)))
   λ> agrupaColas []
   -
   λ> agrupaColas [ej1]
   5 | 2
   λ> agrupaColas [ej1, ej2]
   5 | 4 | 2 | 7 | 3
   λ> agrupaColas [ej1, ej2, ej3]
   5 | 6 | 4 | 1 | 2 | 0 | 7 | 9 | 3

λ> ej1 = inserta 2 (inserta 5 vacia)

λ> ej2 = inserta 3 (inserta 7 (inserta 4 vacia))

λ> ej3 = inserta 9 (inserta 0 (inserta 1 (inserta 6 vacia)))

λ> agrupaColas []

λ> agrupaColas [ej1]

5 | 2

λ> agrupaColas [ej1, ej2]

5 | 4 | 2 | 7 | 3

λ> agrupaColas [ej1, ej2, ej3]

5 | 6 | 4 | 1 | 2 | 0 | 7 | 9 | 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)
import IntercalaColas (intercalaColas)
import Test.QuickCheck

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

agrupaColas1 :: [Cola a] -> Cola a
agrupaColas1 []            = vacia
agrupaColas1 [c]           = c
agrupaColas1 (c1:c2:colas) = agrupaColas1 ((intercalaColas c1 c2) : colas)

-- La función intercalaColas está definida en el ejercicio
-- "TAD de las colas: Intercalado de dos colas" que se encuentra en
-- https://bit.ly/3XYyjsM

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

agrupaColas2 :: [Cola a] -> Cola a
agrupaColas2 = foldl intercalaColas vacia

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

-- La propiedad es
prop_agrupaColas :: [Cola Int] -> Bool
prop_agrupaColas cs =
  agrupaColas1 cs == agrupaColas2 cs

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=30}) prop_agrupaColas
--    +++ OK, passed 100 tests.

import TAD.Cola (Cola, vacia, inserta)

import IntercalaColas (intercalaColas)

import Test.QuickCheck

-- 1ª solución

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

agrupaColas1 :: [Cola a] -> Cola a

agrupaColas1 [] = vacia

agrupaColas1 [c] = c

agrupaColas1 (c1:c2:colas) = agrupaColas1 ((intercalaColas c1 c2) : colas)

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

-- "TAD de las colas: Intercalado de dos colas" que se encuentra en

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

-- 2ª solución

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

agrupaColas2 :: [Cola a] -> Cola a

agrupaColas2 = foldl intercalaColas vacia

-- Comprobación de equivalencia

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

-- La propiedad es

prop_agrupaColas :: [Cola Int] -> Bool

prop_agrupaColas cs =

agrupaColas1 cs == agrupaColas2 cs

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=30}) prop_agrupaColas

-- +++ OK, passed 100 tests.

Soluciones en Python

from functools import reduce
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.TAD.cola import (Cola, colaAleatoria, inserta, vacia)
from src.intercalaColas import intercalaColas

A = TypeVar('A')

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

def agrupaColas1(cs: list[Cola[A]]) -> Cola[A]:
    if not cs:
        return vacia()
    if len(cs) == 1:
        return cs[0]
    return agrupaColas1([intercalaColas(cs[0], cs[1])] + cs[2:])

# La función intercalaColas está definida en el ejercicio
# "TAD de las colas: Intercalado de dos colas" que se encuentra en
# https://bit.ly/3XYyjsM

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

def agrupaColas2(cs: list[Cola[A]]) -> Cola[A]:
    return reduce(intercalaColas, cs, vacia())

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

# La propiedad es
@given(st.lists(colaAleatoria(), max_size=4))
def test_extiendeCola(cs: list[Cola[int]]) -> None:
    assert agrupaColas1(cs) == agrupaColas2(cs)

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

from functools import reduce

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.TAD.cola import (Cola, colaAleatoria, inserta, vacia)

from src.intercalaColas import intercalaColas

A = TypeVar('A')

# 1ª solución

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

def agrupaColas1(cs: list[Cola[A]]) -> Cola[A]:

if not cs:

return vacia()

if len(cs) == 1:

return cs[0]

return agrupaColas1([intercalaColas(cs[0], cs[1])] + cs[2:])

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

# "TAD de las colas: Intercalado de dos colas" que se encuentra en

# https://bit.ly/3XYyjsM

# 2ª solución

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

def agrupaColas2(cs: list[Cola[A]]) -> Cola[A]:

return reduce(intercalaColas, cs, vacia())

# Comprobación de equivalencia

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

# La propiedad es

@given(st.lists(colaAleatoria(), max_size=4))

def test_extiendeCola(cs: list[Cola[int]]) -> None:

assert agrupaColas1(cs) == agrupaColas2(cs)

# La comprobación es

# src> poetry run pytest -q agrupaColas.py

# 1 passed in 0.50s

TAD de las colas: Intercalado de dos colas

PorJosé A. Alonso 16-febrero-202326-enero-2023

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

   intercalaColas :: Cola a -> Cola a -> Cola a

1	intercalaColas :: Cola a -> Cola a -> Cola a

tal que intercalaColas c1 c2 es la cola formada por los elementos de c1 y c2 colocados en una cola, de forma alternativa, empezando por los elementos de c1. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 5 vacia)
   λ> ej2 = inserta 0 (inserta 7 (inserta 4 (inserta 9 vacia)))
   λ> intercalaColas ej1 ej2
   5 | 9 | 3 | 4 | 7 | 0
   λ> intercalaColas ej2 ej1
   9 | 5 | 4 | 3 | 7 | 0

λ> ej1 = inserta 3 (inserta 5 vacia)

λ> ej2 = inserta 0 (inserta 7 (inserta 4 (inserta 9 vacia)))

λ> intercalaColas ej1 ej2

5 | 9 | 3 | 4 | 7 | 0

λ> intercalaColas ej2 ej1

9 | 5 | 4 | 3 | 7 | 0

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

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

intercalaColas :: Cola a -> Cola a -> Cola a
intercalaColas c1 c2
  | esVacia c1 = c2
  | esVacia c2 = c1
  | otherwise  = extiendeCola (inserta pc2 (inserta pc1 vacia))
                              (intercalaColas rc1 rc2)
  where pc1 = primero c1
        rc1 = resto c1
        pc2 = primero c2
        rc2 = resto c2

-- La función extiendeCola está definida en el ejercicio
-- "TAD de las colas: Extensión de colas" que se encuentra en
-- https://bit.ly/3XIJJ4m

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

intercalaColas2 :: Cola a -> Cola a -> Cola a
intercalaColas2 c1 c2 = aux c1 c2 vacia
  where
    aux d1 d2 c
      | esVacia d1 = extiendeCola c d2
      | esVacia d2 = extiendeCola c d1
      | otherwise  = aux rd1 rd2 (inserta pd2 (inserta pd1 c))
      where pd1 = primero d1
            rd1 = resto d1
            pd2 = primero d2
            rd2 = resto d2

-- 3ª solución
-- ===========

intercalaColas3 :: Cola a -> Cola a -> Cola a
intercalaColas3 c1 c2 =
  listaAcola (intercalaListas (colaAlista c1) (colaAlista c2))

-- (intercalaListas xs ys) es la lista obtenida intercalando los
-- elementos de xs e ys. Por ejemplo,
intercalaListas :: [a] -> [a] -> [a]
intercalaListas []     ys     = ys
intercalaListas xs     []     = xs
intercalaListas (x:xs) (y:ys) = x : y : intercalaListas xs ys

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

-- La propiedad es
prop_intercalaColas :: Cola Int -> Cola Int -> Bool
prop_intercalaColas c1 c2 =
  all (== intercalaColas c1 c2)
      [intercalaColas2 c1 c2,
       intercalaColas2 c1 c2]

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

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

import Transformaciones_colas_listas (colaAlista, listaAcola)

import ExtiendeCola (extiendeCola)

import Test.QuickCheck

-- 1ª solución

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

intercalaColas :: Cola a -> Cola a -> Cola a

intercalaColas c1 c2

| esVacia c1 = c2

| esVacia c2 = c1

| otherwise = extiendeCola (inserta pc2 (inserta pc1 vacia))

(intercalaColas rc1 rc2)

where pc1 = primero c1

rc1 = resto c1

pc2 = primero c2

rc2 = resto c2

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

-- "TAD de las colas: Extensión de colas" que se encuentra en

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

-- 2ª solución

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

intercalaColas2 :: Cola a -> Cola a -> Cola a

intercalaColas2 c1 c2 = aux c1 c2 vacia

where

aux d1 d2 c

| esVacia d1 = extiendeCola c d2

| esVacia d2 = extiendeCola c d1

| otherwise = aux rd1 rd2 (inserta pd2 (inserta pd1 c))

where pd1 = primero d1

rd1 = resto d1

pd2 = primero d2

rd2 = resto d2

-- 3ª solución

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

intercalaColas3 :: Cola a -> Cola a -> Cola a

intercalaColas3 c1 c2 =

listaAcola (intercalaListas (colaAlista c1) (colaAlista c2))

-- (intercalaListas xs ys) es la lista obtenida intercalando los

-- elementos de xs e ys. Por ejemplo,

intercalaListas :: [a] -> [a] -> [a]

intercalaListas [] ys = ys

intercalaListas xs [] = xs

intercalaListas (x:xs) (y:ys) = x : y : intercalaListas xs ys

-- Comprobación de equivalencia

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

-- La propiedad es

prop_intercalaColas :: Cola Int -> Cola Int -> Bool

prop_intercalaColas c1 c2 =

all (== intercalaColas c1 c2)

[intercalaColas2 c1 c2,

intercalaColas2 c1 c2]

-- La comprobación es

-- λ> quickCheck prop_intercalaColas

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

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

A = TypeVar('A')

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

def intercalaColas(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    if esVacia(c1):
        return c2
    if esVacia(c2):
        return c1
    pc1 = primero(c1)
    rc1 = resto(c1)
    pc2 = primero(c2)
    rc2 = resto(c2)
    return extiendeCola(inserta(pc2, inserta(pc1, vacia())),
                        intercalaColas(rc1, rc2))

# La función extiendeCola está definida en el ejercicio
# "TAD de las colas: Extensión de colas" que se encuentra en
# https://bit.ly/3XIJJ4m

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

def intercalaColas2(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    def aux(d1: Cola[A], d2: Cola[A], d3: Cola[A]) -> Cola[A]:
        if esVacia(d1):
            return extiendeCola(d3, d2)
        if esVacia(d2):
            return extiendeCola(d3, d1)
        pd1 = primero(d1)
        rd1 = resto(d1)
        pd2 = primero(d2)
        rd2 = resto(d2)
        return aux(rd1, rd2, inserta(pd2, inserta(pd1, d3)))

    return aux(c1, c2, vacia())

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

# intercalaListas(xs, ys) es la lista obtenida intercalando los
# elementos de xs e ys. Por ejemplo,
def intercalaListas(xs: list[A], ys: list[A]) -> list[A]:
    if not xs:
        return ys
    if not ys:
        return xs
    return [xs[0], ys[0]] + intercalaListas(xs[1:], ys[1:])

def intercalaColas3(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    return listaAcola(intercalaListas(colaAlista(c1), colaAlista(c2)))

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

def intercalaColas4Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    if c1.esVacia():
        return c2
    if c2.esVacia():
        return c1
    pc1 = c1.primero()
    c1.resto()
    pc2 = c2.primero()
    c2.resto()
    return extiendeCola(inserta(pc2, inserta(pc1, vacia())),
                        intercalaColas4Aux(c1, c2))

def intercalaColas4(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    _c1 = deepcopy(c1)
    _c2 = deepcopy(c2)
    return intercalaColas4Aux(_c1, _c2)

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

def intercalaColas5Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    r: Cola[A] = vacia()
    while not esVacia(c1) and not esVacia(c2):
        pc1 = primero(c1)
        c1.resto()
        pc2 = primero(c2)
        c2.resto()
        r = inserta(pc2, inserta(pc1, r))
    if esVacia(c1):
        return extiendeCola(r, c2)
    return extiendeCola(r, c1)

def intercalaColas5(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    _c1 = deepcopy(c1)
    _c2 = deepcopy(c2)
    return intercalaColas5Aux(_c1, _c2)

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

# La propiedad es
@given(c1=colaAleatoria(), c2=colaAleatoria())
def test_extiendeCola(c1: Cola[int], c2: Cola[int]) -> None:
    r = intercalaColas(c1, c2)
    assert intercalaColas2(c1, c2) == r
    assert intercalaColas3(c1, c2) == r
    assert intercalaColas4(c1, c2) == r
    assert intercalaColas5(c1, c2) == r

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.extiendeCola import extiendeCola

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

resto, vacia)

from src.transformaciones_colas_listas import colaAlista, listaAcola

A = TypeVar('A')

# 1ª solución

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

def intercalaColas(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

if esVacia(c1):

return c2

if esVacia(c2):

return c1

pc1 = primero(c1)

rc1 = resto(c1)

pc2 = primero(c2)

rc2 = resto(c2)

return extiendeCola(inserta(pc2, inserta(pc1, vacia())),

intercalaColas(rc1, rc2))

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

# "TAD de las colas: Extensión de colas" que se encuentra en

# https://bit.ly/3XIJJ4m

# 2ª solución

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

def intercalaColas2(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

def aux(d1: Cola[A], d2: Cola[A], d3: Cola[A]) -> Cola[A]:

if esVacia(d1):

return extiendeCola(d3, d2)

if esVacia(d2):

return extiendeCola(d3, d1)

pd1 = primero(d1)

rd1 = resto(d1)

pd2 = primero(d2)

rd2 = resto(d2)

return aux(rd1, rd2, inserta(pd2, inserta(pd1, d3)))

return aux(c1, c2, vacia())

# 3ª solución

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

# intercalaListas(xs, ys) es la lista obtenida intercalando los

# elementos de xs e ys. Por ejemplo,

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

if not xs:

return ys

if not ys:

return xs

return [xs[0], ys[0]] + intercalaListas(xs[1:], ys[1:])

def intercalaColas3(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

return listaAcola(intercalaListas(colaAlista(c1), colaAlista(c2)))

# 4ª solución

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

def intercalaColas4Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

if c1.esVacia():

return c2

if c2.esVacia():

return c1

pc1 = c1.primero()

c1.resto()

pc2 = c2.primero()

c2.resto()

return extiendeCola(inserta(pc2, inserta(pc1, vacia())),

intercalaColas4Aux(c1, c2))

def intercalaColas4(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

_c1 = deepcopy(c1)

_c2 = deepcopy(c2)

return intercalaColas4Aux(_c1, _c2)

# 5ª solución

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

def intercalaColas5Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

r: Cola[A] = vacia()

while not esVacia(c1) and not esVacia(c2):

pc1 = primero(c1)

c1.resto()

pc2 = primero(c2)

c2.resto()

r = inserta(pc2, inserta(pc1, r))

if esVacia(c1):

return extiendeCola(r, c2)

return extiendeCola(r, c1)

def intercalaColas5(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

_c1 = deepcopy(c1)

_c2 = deepcopy(c2)

return intercalaColas5Aux(_c1, _c2)

# Comprobación de equivalencia

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

# La propiedad es

@given(c1=colaAleatoria(), c2=colaAleatoria())

def test_extiendeCola(c1: Cola[int], c2: Cola[int]) -> None:

r = intercalaColas(c1, c2)

assert intercalaColas2(c1, c2) == r

assert intercalaColas3(c1, c2) == r

assert intercalaColas4(c1, c2) == r

assert intercalaColas5(c1, c2) == r

# La comprobación es

# src> poetry run pytest -q intercalaColas.py

# 1 passed in 0.47s

TAD de las colas: Extensión de colas

PorJosé A. Alonso 15-febrero-202325-enero-2023

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

   extiendeCola :: Cola a -> Cola a -> Cola a

1	extiendeCola :: Cola a -> Cola a -> Cola a

tal que extiendeCola c1 c2 es la cola que resulta de poner los elementos de la cola c2 a continuación de los de la cola de c1. Por
ejemplo,

   λ> ej1 = inserta 3 (inserta 2 vacia)
   λ> ej2 = inserta 5 (inserta 3 (inserta 4 vacia))
   λ> ej1
   2 | 3
   λ> ej2
   4 | 3 | 5
   λ> extiendeCola ej1 ej2
   2 | 3 | 4 | 3 | 5
   λ> extiendeCola ej2 ej1
   4 | 3 | 5 | 2 | 3

λ> ej1 = inserta 3 (inserta 2 vacia)

λ> ej2 = inserta 5 (inserta 3 (inserta 4 vacia))

λ> ej1

2 | 3

λ> ej2

4 | 3 | 5

λ> extiendeCola ej1 ej2

2 | 3 | 4 | 3 | 5

λ> extiendeCola ej2 ej1

4 | 3 | 5 | 2 | 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, primero, resto, esVacia)
import Transformaciones_colas_listas (colaAlista, listaAcola)
import Test.QuickCheck

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

extiendeCola :: Cola a -> Cola a -> Cola a
extiendeCola c1 c2
  | esVacia c2 = c1
  | otherwise  = extiendeCola (inserta pc2 c1) rq2
  where pc2 = primero c2
        rq2 = resto c2

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

extiendeCola2 :: Cola a -> Cola a -> Cola a
extiendeCola2 c1 c2 =
  listaAcola (colaAlista c1 ++ colaAlista c2)

-- Las funciones colaAlista y listaAcola están definidas en el ejercicio
-- "Transformaciones entre colas y listas" que se encuentra en
-- https://bit.ly/3Xv0oIt

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

-- La propiedad es
prop_extiendeCola :: Cola Int -> Cola Int -> Bool
prop_extiendeCola p c =
  extiendeCola p c == extiendeCola2 p c

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

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

import Transformaciones_colas_listas (colaAlista, listaAcola)

import Test.QuickCheck

-- 1ª solución

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

extiendeCola :: Cola a -> Cola a -> Cola a

extiendeCola c1 c2

| esVacia c2 = c1

| otherwise = extiendeCola (inserta pc2 c1) rq2

where pc2 = primero c2

rq2 = resto c2

-- 2ª solución

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

extiendeCola2 :: Cola a -> Cola a -> Cola a

extiendeCola2 c1 c2 =

listaAcola (colaAlista c1 ++ colaAlista c2)

-- Las funciones colaAlista y listaAcola están definidas en el ejercicio

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

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

-- Comprobación de equivalencia

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

-- La propiedad es

prop_extiendeCola :: Cola Int -> Cola Int -> Bool

prop_extiendeCola p c =

extiendeCola p c == extiendeCola2 p c

-- La comprobación es

-- λ> quickCheck prop_extiendeCola

-- +++ 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, primero,
                          resto, vacia)
from src.transformaciones_colas_listas import colaAlista, listaAcola

A = TypeVar('A')

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

def extiendeCola(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    if esVacia(c2):
        return c1
    pc2 = primero(c2)
    rc2 = resto(c2)
    return extiendeCola(inserta(pc2, c1), rc2)

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

def extiendeCola2(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    return listaAcola(colaAlista(c1) + colaAlista(c2))

# Las funciones colaAlista y listaAcola están definidas en el ejercicio
# "Transformaciones entre colas y listas" que se encuentra en
# https://bit.ly/3Xv0oIt

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

def extiendeCola3Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    if c2.esVacia():
        return c1
    pc2 = c2.primero()
    c2.resto()
    return extiendeCola(inserta(pc2, c1), c2)

def extiendeCola3(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    _c2 = deepcopy(c2)
    return extiendeCola3Aux(c1, _c2)

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

def extiendeCola4Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    r = c1
    while not esVacia(c2):
        r = inserta(primero(c2), r)
        c2 = resto(c2)
    return r

def extiendeCola4(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    _c2 = deepcopy(c2)
    return extiendeCola4Aux(c1, _c2)

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

def extiendeCola5Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    r = c1
    while not c2.esVacia():
        r.inserta(primero(c2))
        c2.resto()
    return r

def extiendeCola5(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    _c1 = deepcopy(c1)
    _c2 = deepcopy(c2)
    return extiendeCola5Aux(_c1, _c2)

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

# La propiedad es
@given(c1=colaAleatoria(), c2=colaAleatoria())
def test_extiendeCola(c1: Cola[int], c2: Cola[int]) -> None:
    r = extiendeCola(c1, c2)
    assert extiendeCola2(c1, c2) == r
    assert extiendeCola3(c1, c2) == r
    assert extiendeCola4(c1, c2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

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

resto, vacia)

from src.transformaciones_colas_listas import colaAlista, listaAcola

A = TypeVar('A')

# 1ª solución

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

def extiendeCola(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

if esVacia(c2):

return c1

pc2 = primero(c2)

rc2 = resto(c2)

return extiendeCola(inserta(pc2, c1), rc2)

# 2ª solución

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

def extiendeCola2(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

return listaAcola(colaAlista(c1) + colaAlista(c2))

# Las funciones colaAlista y listaAcola están definidas en el ejercicio

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

# https://bit.ly/3Xv0oIt

# 3ª solución

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

def extiendeCola3Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

if c2.esVacia():

return c1

pc2 = c2.primero()

c2.resto()

return extiendeCola(inserta(pc2, c1), c2)

def extiendeCola3(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

_c2 = deepcopy(c2)

return extiendeCola3Aux(c1, _c2)

# 4ª solución

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

def extiendeCola4Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

r = c1

while not esVacia(c2):

r = inserta(primero(c2), r)

c2 = resto(c2)

return r

def extiendeCola4(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

_c2 = deepcopy(c2)

return extiendeCola4Aux(c1, _c2)

# 5ª solución

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

def extiendeCola5Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

r = c1

while not c2.esVacia():

r.inserta(primero(c2))

c2.resto()

return r

def extiendeCola5(c1: Cola[A], c2: Cola[A]) -> Cola[A]:

_c1 = deepcopy(c1)

_c2 = deepcopy(c2)

return extiendeCola5Aux(_c1, _c2)

# Comprobación de equivalencia

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

# La propiedad es

@given(c1=colaAleatoria(), c2=colaAleatoria())

def test_extiendeCola(c1: Cola[int], c2: Cola[int]) -> None:

r = extiendeCola(c1, c2)

assert extiendeCola2(c1, c2) == r

assert extiendeCola3(c1, c2) == r

assert extiendeCola4(c1, c2) == r

# La comprobación es

# src> poetry run pytest -q extiendeCola.py

# 1 passed in 0.32s

TAD de las colas: Alguno de los elementos verifican una propiedad

PorJosé A. Alonso 14-febrero-202325-enero-2023

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

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

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

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

   algunoVerifica (< 0) (inserta 3 (inserta (-2) vacia)) == True
   algunoVerifica (< 0) (inserta 3 (inserta 2 vacia))    == False

1 2	algunoVerifica (< 0) (inserta 3 (inserta (-2) vacia)) == True algunoVerifica (< 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
-- ===========

algunoVerifica1 :: (a -> Bool) -> Cola a -> Bool
algunoVerifica1 p c
  | esVacia c = False
  | otherwise = p pc || algunoVerifica1 p rc
  where pc = primero c
        rc = resto c

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

algunoVerifica2 :: (a -> Bool) -> Cola a -> Bool
algunoVerifica2 p c =
  any 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_algunoVerifica :: (Int -> Bool) -> [Int] -> Bool
prop_algunoVerifica p xs =
  algunoVerifica1 p c == algunoVerifica2 p c
  where c = listaAcola xs

-- La comprobación es
--    λ> quickCheck' prop_algunoVerifica
--    +++ 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

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

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

algunoVerifica1 p c

| esVacia c = False

| otherwise = p pc || algunoVerifica1 p rc

where pc = primero c

rc = resto c

-- 2ª solución

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

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

algunoVerifica2 p c =

any 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_algunoVerifica :: (Int -> Bool) -> [Int] -> Bool

prop_algunoVerifica p xs =

algunoVerifica1 p c == algunoVerifica2 p c

where c = listaAcola xs

-- La comprobación es

-- λ> quickCheck' prop_algunoVerifica

-- +++ 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 algunoVerifica1(p: Callable[[A], bool], c: Cola[A]) -> bool:
    if esVacia(c):
        return False
    pc = primero(c)
    rc = resto(c)
    return p(pc) or algunoVerifica1(p, rc)

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

def algunoVerifica2(p: Callable[[A], bool], c: Cola[A]) -> bool:
    return any(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 algunoVerifica3Aux(p: Callable[[A], bool], c: Cola[A]) -> bool:
    if c.esVacia():
        return False
    pc = c.primero()
    c.resto()
    return p(pc) or algunoVerifica3Aux(p, c)

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

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

def algunoVerifica4Aux(p: Callable[[A], bool], c: Cola[A]) -> bool:
    if c.esVacia():
        return False
    pc = c.primero()
    c.resto()
    return p(pc) or algunoVerifica4Aux(p, c)

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

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

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

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

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

# La propiedad es
@given(c=colaAleatoria())
def test_filtraPila(c: Cola[int]) -> None:
    r = algunoVerifica1(lambda x: x > 0, c)
    assert algunoVerifica2(lambda x: x > 0, c) == r
    assert algunoVerifica3(lambda x: x > 0, c) == r
    assert algunoVerifica4(lambda x: x > 0, c) == r
    assert algunoVerifica5(lambda x: x > 0, c) == r

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

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 algunoVerifica1(p: Callable[[A], bool], c: Cola[A]) -> bool:

if esVacia(c):

return False

pc = primero(c)

rc = resto(c)

return p(pc) or algunoVerifica1(p, rc)

# 2ª solución

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

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

return any(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 algunoVerifica3Aux(p: Callable[[A], bool], c: Cola[A]) -> bool:

if c.esVacia():

return False

pc = c.primero()

c.resto()

return p(pc) or algunoVerifica3Aux(p, c)

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

_c = deepcopy(c)

return algunoVerifica3Aux(p, _c)

# 4ª solución

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

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

if c.esVacia():

return False

pc = c.primero()

c.resto()

return p(pc) or algunoVerifica4Aux(p, c)

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

_c = deepcopy(c)

return algunoVerifica4Aux(p, _c)

# 5ª solución

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

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

while not c.esVacia():

if p(c.primero()):

return True

c.resto()

return False

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

_c = deepcopy(c)

return algunoVerifica5Aux(p, _c)

# Comprobación de equivalencia

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

# La propiedad es

@given(c=colaAleatoria())

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

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

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

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

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

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

# La comprobación es

# src> poetry run pytest -q algunoVerifica.py

# 1 passed in 0.31s

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

El pasatiempo de Ulises

PorJosé A. Alonso 22-mayo-201726-marzo-2022

Ulises, en sus ratos libres, juega a un pasatiempo que consiste en, dada una serie de números naturales positivos en una cola, sacar un elemento y, si es distinto de 1, volver a meter el mayor de sus divisores propios. Si el número que saca es el 1, entonces lo deja fuera y no mete ningún otro. El pasatiempo continúa hasta que la cola queda vacía.

Por ejemplo, a partir de una cola con los números 10, 20 y 30, el pasatiempo se desarrollaría como sigue:

  C [30,20,10]
  C [20,10,15]
  C [10,15,10]
  C [15,10,5]
  C [10,5,5]
  C [5,5,5]
  C [5,5,1]
  C [5,1,1]
  C [1,1,1]
  C [1,1]
  C [1]
  C []

C [30,20,10]

C [20,10,15]

C [10,15,10]

C [15,10,5]

C [10,5,5]

C [5,5,5]

C [5,5,1]

C [5,1,1]

C [1,1,1]

C [1,1]

C [1]

C []

Definir la función

   numeroPasos :: Cola Int -> Int

1	numeroPasos :: Cola Int -> Int

tal que (numeroPasos c) es el número de veces que Ulises saca algún número de la cola c al utilizarla en su pasatiempo. Por ejemplo,

   numeroPasos (foldr inserta vacia [30])        ==  4
   numeroPasos (foldr inserta vacia [20])        ==  4
   numeroPasos (foldr inserta vacia [10])        ==  3
   numeroPasos (foldr inserta vacia [10,20,30])  ==  11

numeroPasos (foldr inserta vacia [30]) == 4

numeroPasos (foldr inserta vacia [20]) == 4

numeroPasos (foldr inserta vacia [10]) == 3

numeroPasos (foldr inserta vacia [10,20,30]) == 11

Soluciones

[schedule expon=’2017-05-29′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 29 de mayo.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2017-05-29′ at=»06:00″]

import I1M.Cola
import Data.Numbers.Primes (primeFactors)

numeroPasos :: Cola Int -> Int
numeroPasos c
    | esVacia c = 0
    | pc == 1   = 1 + numeroPasos rc
    | otherwise = 1 + numeroPasos (inserta (mayorDivisorPropio pc) rc)
    where pc = primero c
          rc = resto c

-- 1ª definición de mayorDivisorPropio
mayorDivisorPropio1 :: Int -> Int
mayorDivisorPropio1 n = 
    head [x | x <- [n-1,n-2..], n `mod` x == 0]

-- 2ª definición de mayorDivisorPropio
mayorDivisorPropio2 :: Int -> Int
mayorDivisorPropio2 n =
    n `div` head (primeFactors n)

-- Comparación de eficiencia:
--    ghci> sum (map mayorDivisorPropio1 [2..3000])
--    1485659
--    (3.91 secs, 618,271,360 bytes)
--    ghci> sum (map mayorDivisorPropio2 [2..3000])
--    1485659
--    (0.04 secs, 22,726,600 bytes)

import I1M.Cola

import Data.Numbers.Primes (primeFactors)

numeroPasos :: Cola Int -> Int

numeroPasos c

| esVacia c = 0

| pc == 1 = 1 + numeroPasos rc

| otherwise = 1 + numeroPasos (inserta (mayorDivisorPropio pc) rc)

where pc = primero c

rc = resto c

-- 1ª definición de mayorDivisorPropio

mayorDivisorPropio1 :: Int -> Int

mayorDivisorPropio1 n =

head [x | x <- [n-1,n-2..], n `mod` x == 0]

-- 2ª definición de mayorDivisorPropio

mayorDivisorPropio2 :: Int -> Int

mayorDivisorPropio2 n =

n `div` head (primeFactors n)

-- Comparación de eficiencia:

-- ghci> sum (map mayorDivisorPropio1 [2..3000])

-- 1485659

-- (3.91 secs, 618,271,360 bytes)

-- ghci> sum (map mayorDivisorPropio2 [2..3000])

-- 1485659

-- (0.04 secs, 22,726,600 bytes)

[/schedule]

TAD de las colas: Máximo elemento de una cola

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

TAD de las colas: Reconocimiento de subcolas

TAD de las colas: Reconocimiento de prefijos de colas

TAD de las colas: Inclusión de colas

TAD de las colas: Pertenencia a una cola

TAD de las colas: Agrupación de colas

TAD de las colas: Intercalado de dos colas

TAD de las colas: Extensión de colas

TAD de las colas: Alguno de los elementos verifican una propiedad

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

El pasatiempo de Ulises

Soluciones

Entradas recientes

Buscar

Correo electrónico