Colas – Exercitium

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