TAD de las colas: Agrupación de colas
Utilizando el tipo abstracto de datos de las colas, definir la función
1 |
agrupaColas :: [Cola a] -> Cola a |
tal que agrupaColas [c1,c2,c3,...,cn]
es la cola formada mezclando las colas de la lista como sigue: mezcla c1
con c2
, el resultado con c3
, el resultado con c4
, y así sucesivamente. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 |
λ> ej1 = inserta 2 (inserta 5 vacia) λ> ej2 = inserta 3 (inserta 7 (inserta 4 vacia)) λ> ej3 = inserta 9 (inserta 0 (inserta 1 (inserta 6 vacia))) λ> agrupaColas [] - λ> agrupaColas [ej1] 5 | 2 λ> agrupaColas [ej1, ej2] 5 | 4 | 2 | 7 | 3 λ> agrupaColas [ej1, ej2, ej3] 5 | 6 | 4 | 1 | 2 | 0 | 7 | 9 | 3 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
import TAD.Cola (Cola, vacia, inserta) import IntercalaColas (intercalaColas) import Test.QuickCheck -- 1ª solución -- =========== agrupaColas1 :: [Cola a] -> Cola a agrupaColas1 [] = vacia agrupaColas1 [c] = c agrupaColas1 (c1:c2:colas) = agrupaColas1 ((intercalaColas c1 c2) : colas) -- La función intercalaColas está definida en el ejercicio -- "TAD de las colas: Intercalado de dos colas" que se encuentra en -- https://bit.ly/3XYyjsM -- 2ª solución -- =========== agrupaColas2 :: [Cola a] -> Cola a agrupaColas2 = foldl intercalaColas vacia -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_agrupaColas :: [Cola Int] -> Bool prop_agrupaColas cs = agrupaColas1 cs == agrupaColas2 cs -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=30}) prop_agrupaColas -- +++ OK, passed 100 tests. |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
from functools import reduce from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.TAD.cola import (Cola, colaAleatoria, inserta, vacia) from src.intercalaColas import intercalaColas A = TypeVar('A') # 1ª solución # =========== def agrupaColas1(cs: list[Cola[A]]) -> Cola[A]: if not cs: return vacia() if len(cs) == 1: return cs[0] return agrupaColas1([intercalaColas(cs[0], cs[1])] + cs[2:]) # La función intercalaColas está definida en el ejercicio # "TAD de las colas: Intercalado de dos colas" que se encuentra en # https://bit.ly/3XYyjsM # 2ª solución # =========== def agrupaColas2(cs: list[Cola[A]]) -> Cola[A]: return reduce(intercalaColas, cs, vacia()) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(colaAleatoria(), max_size=4)) def test_extiendeCola(cs: list[Cola[int]]) -> None: assert agrupaColas1(cs) == agrupaColas2(cs) # La comprobación es # src> poetry run pytest -q agrupaColas.py # 1 passed in 0.50s |