TAD de las colas - Extensión de colas

José A. Alonso

15-02-2023

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

   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

Soluciones

Se usarán las funciones colaAlista y listaAcola del ejercicio Transformaciones entre colas y listas.

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)

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

# 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