Concatenación de una lista de listas
Definir, por recursión, la función
|
1 |
conc :: [[a]] -> [a] |
tal que conc xss es la concenación de las listas de xss. Por ejemplo,
|
1 |
conc [[1,3],[2,4,6],[1,9]] == [1,3,2,4,6,1,9] |
Comprobar con QuickCheck que la longitud de conc xss es la suma de las longitudes de los elementos de xss.
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
-- 1ª solución -- =========== conc1 :: [[a]] -> [a] conc1 xss = [x | xs <- xss, x <- xs] -- 2ª solución -- =========== conc2 :: [[a]] -> [a] conc2 [] = [] conc2 (xs:xss) = xs ++ conc2 xss -- 3ª solución -- =========== conc3 :: [[a]] -> [a] conc3 = foldr (++) [] -- 4ª solución -- =========== conc4 :: [[a]] -> [a] conc4 = concat -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_conc :: [[Int]] -> Bool prop_conc xss = all (== conc1 xss) [conc2 xss, conc3 xss, conc4 xss] -- La comprobación es -- λ> quickCheck prop_conc -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (conc1 [[1..n] | n <- [1..5000]]) -- 12502500 -- (2.72 secs, 1,802,391,200 bytes) -- λ> length (conc2 [[1..n] | n <- [1..5000]]) -- 12502500 -- (0.27 secs, 1,602,351,160 bytes) -- λ> length (conc3 [[1..n] | n <- [1..5000]]) -- 12502500 -- (0.28 secs, 1,602,071,192 bytes) -- λ> length (conc4 [[1..n] | n <- [1..5000]]) -- 12502500 -- (0.26 secs, 1,602,071,184 bytes) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_long_conc :: [[Int]] -> Bool prop_long_conc xss = length (conc1 xss) == sum (map length xss) -- La comprobación es -- λ> quickCheck prop_long_conc -- +++ 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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
from functools import reduce from operator import concat from sys import setrecursionlimit from timeit import Timer, default_timer from typing import Any, TypeVar from hypothesis import given from hypothesis import strategies as st setrecursionlimit(10**6) A = TypeVar('A') # 1ª solución # =========== def conc1(xss: list[list[A]]) -> list[A]: return [x for xs in xss for x in xs] # 2ª solución # =========== def conc2(xss: list[list[A]]) -> list[A]: if not xss: return [] return xss[0] + conc2(xss[1:]) # 3ª solución # =========== def conc3(xss: Any) -> Any: return reduce(concat, xss) # 4ª solución # =========== def conc4(xss: list[list[A]]) -> list[A]: r = [] for xs in xss: for x in xs: r.append(x) return r # La propiedad es @given(st.lists(st.lists(st.integers()), min_size=1)) def test_conc(xss: list[list[int]]) -> None: r = conc1(xss) assert conc2(xss) == r assert conc3(xss) == r assert conc4(xss) == r # La comprobación es # src> poetry run pytest -q contenacion_de_una_lista_de_listas.py # 1 passed in 0.63s # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('conc1([list(range(n)) for n in range(1500)])') # 0.04 segundos # >>> tiempo('conc2([list(range(n)) for n in range(1500)])') # 6.28 segundos # >>> tiempo('conc3([list(range(n)) for n in range(1500)])') # 2.55 segundos # >>> tiempo('conc4([list(range(n)) for n in range(1500)])') # 0.09 segundos # # >>> tiempo('conc1([list(range(n)) for n in range(10000)])') # 2.01 segundos # >>> tiempo('conc4([list(range(n)) for n in range(10000)])') # 2.90 segundos # # Comprobación de la propiedad # ============================ # La propiedad es @given(st.lists(st.lists(st.integers()), min_size=1)) def test_long_conc(xss: list[list[int]]) -> None: assert len(conc1(xss)) == sum(map(len, xss)) # prop_long_conc :: [[Int]] -> Bool # prop_long_conc xss = # length (conc1 xss) == sum (map length xss) # # La comprobación es # λ> quickCheck prop_long_conc # +++ OK, passed 100 tests. |