febrero 2023 – Página 3

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

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, inserta, primero, resto, esVacia, vacia,
                          colaAleatoria)

A = TypeVar('A')

# 1ª definición de listaAcola
# ===========================

def listaAcola(ys: list[A]) -> Cola[A]:
    def aux(xs: list[A]) -> Cola[A]:
        if not xs:
            return vacia()
        return inserta(xs[0], aux(xs[1:]))

    return aux(list(reversed(ys)))

# 2ª solución de listaAcola
# =========================

def listaAcola2(xs: list[A]) -> Cola[A]:
    p: Cola[A] = Cola()
    for x in xs:
        p.inserta(x)
    return p

# Comprobación de equivalencia de las definiciones de listaAcola
# ==============================================================

# La propiedad es
@given(st.lists(st.integers()))
def test_listaAcola(xs: list[int]) -> None:
    assert listaAcola(xs) == listaAcola2(xs)

# 1ª definición de colaAlista
# ===========================

def colaAlista(c: Cola[A]) -> list[A]:
    if esVacia(c):
        return []
    pc = primero(c)
    rc = resto(c)
    return [pc] + colaAlista(rc)

# 2ª definición de colaAlista
# ===========================

def colaAlista2Aux(c: Cola[A]) -> list[A]:
    if c.esVacia():
        return []
    pc = c.primero()
    c.resto()
    return [pc] + colaAlista2Aux(c)

def colaAlista2(c: Cola[A]) -> list[A]:
    c1 = deepcopy(c)
    return colaAlista2Aux(c1)

# 3ª definición de colaAlista
# ===========================

def colaAlista3Aux(c: Cola[A]) -> list[A]:
    r = []
    while not c.esVacia():
        r.append(c.primero())
        c.resto()
    return r

def colaAlista3(c: Cola[A]) -> list[A]:
    c1 = deepcopy(c)
    return colaAlista3Aux(c1)

# Comprobación de equivalencia de las definiciones de colaAlista
# ==============================================================

@given(p=colaAleatoria())
def test_colaAlista(p: Cola[int]) -> None:
    assert colaAlista(p) == colaAlista2(p)
    assert colaAlista(p) == colaAlista3(p)

# Comprobación de las propiedades
# ===============================

# La primera propiedad es
@given(st.lists(st.integers()))
def test_1_listaAcola(xs: list[int]) -> None:
    assert colaAlista(listaAcola(xs)) == xs

# La segunda propiedad es
@given(c=colaAleatoria())
def test_2_listaAcola(c: Cola[int]) -> None:
    assert listaAcola(colaAlista(c)) == c

# La comprobación es
#      src> poetry run pytest -v transformaciones_colas_listas.py
#      test_listaAcola PASSED
#      test_colaAlista PASSED
#      test_1_listaAcola PASSED
#      test_2_listaAcola PASSED

100

101

102

103

104

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.TAD.cola import (Cola, inserta, primero, resto, esVacia, vacia,

colaAleatoria)

A = TypeVar('A')

# 1ª definición de listaAcola

# ===========================

def listaAcola(ys: list[A]) -> Cola[A]:

def aux(xs: list[A]) -> Cola[A]:

if not xs:

return vacia()

return inserta(xs[0], aux(xs[1:]))

return aux(list(reversed(ys)))

# 2ª solución de listaAcola

# =========================

def listaAcola2(xs: list[A]) -> Cola[A]:

p: Cola[A] = Cola()

for x in xs:

p.inserta(x)

return p

# Comprobación de equivalencia de las definiciones de listaAcola

# ==============================================================

# La propiedad es

@given(st.lists(st.integers()))

def test_listaAcola(xs: list[int]) -> None:

assert listaAcola(xs) == listaAcola2(xs)

# 1ª definición de colaAlista

# ===========================

def colaAlista(c: Cola[A]) -> list[A]:

if esVacia(c):

return []

pc = primero(c)

rc = resto(c)

return [pc] + colaAlista(rc)

# 2ª definición de colaAlista

# ===========================

def colaAlista2Aux(c: Cola[A]) -> list[A]:

if c.esVacia():

return []

pc = c.primero()

c.resto()

return [pc] + colaAlista2Aux(c)

def colaAlista2(c: Cola[A]) -> list[A]:

c1 = deepcopy(c)

return colaAlista2Aux(c1)

# 3ª definición de colaAlista

# ===========================

def colaAlista3Aux(c: Cola[A]) -> list[A]:

r = []

while not c.esVacia():

r.append(c.primero())

c.resto()

return r

def colaAlista3(c: Cola[A]) -> list[A]:

c1 = deepcopy(c)

return colaAlista3Aux(c1)

# Comprobación de equivalencia de las definiciones de colaAlista

# ==============================================================

@given(p=colaAleatoria())

def test_colaAlista(p: Cola[int]) -> None:

assert colaAlista(p) == colaAlista2(p)

assert colaAlista(p) == colaAlista3(p)

# Comprobación de las propiedades

# ===============================

# La primera propiedad es

@given(st.lists(st.integers()))

def test_1_listaAcola(xs: list[int]) -> None:

assert colaAlista(listaAcola(xs)) == xs

# La segunda propiedad es

@given(c=colaAleatoria())

def test_2_listaAcola(c: Cola[int]) -> None:

assert listaAcola(colaAlista(c)) == c

# La comprobación es

# src> poetry run pytest -v transformaciones_colas_listas.py

# test_listaAcola PASSED

# test_colaAlista PASSED

# test_1_listaAcola PASSED

# test_2_listaAcola PASSED

Meses: febrero 2023

TAD de las colas: Alguno de los elementos verifican una propiedad

TAD de las colas: Todos los elementos verifican una propiedad

TAD de las colas: Longitud de una cola

TAD de las colas: Último elemento

TAD de las colas: Transformaciones entre colas y listas

Entradas recientes

Buscar

Correo electrónico