La semana en Exercitium (18 de febrero de 2023)

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas sobre el tipo abstracto de las colas:

1. Todos los elementos de la cola verifican una propiedad
2. Algún elemento de la cola verifica una propiedad
3. Extensión de colas
4. Intercalado de dos colas
5. Agrupación de colas

A continuación se muestran las soluciones.

1. Todos los elementos verifican una propiedad

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

2. Algún elemento de la cola verifica una propiedad

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

3. Extensión de colas

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

4. Intercalado de dos colas

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

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

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

5. Agrupación de colas

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

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

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

1. Todos los elementos verifican una propiedad

2. Algún elemento de la cola verifica una propiedad

3. Extensión de colas

4. Intercalado de dos colas

5. Agrupación de colas

Se puede imprimir o compartir con