27-febrero-2023 – 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

Día: 27-febrero-2023

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

Entradas recientes

Buscar

Correo electrónico