TAD de las colas - Reconocimiento de prefijos de colas

José A. Alonso

22-02-2023

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

   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

Soluciones

Se usará la función colaAlista 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, 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

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

# 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