Utilizando el tipo abstracto de datos de las colas, definir las funciones
listaAcola :: [a] -> Cola a
colaAlista :: Cola a -> [a] |
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 |
λ> 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] |
λ> 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 |
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 |
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
Se puede imprimir o compartir con
La función listaAcola puede ser definida de la siguiente manera:
Y la función colaAlista puede ser definida de la siguiente manera: