{"id":7521,"date":"2022-11-18T06:00:25","date_gmt":"2022-11-18T04:00:25","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7521"},"modified":"2022-12-14T11:37:52","modified_gmt":"2022-12-14T09:37:52","slug":"18-nov-22","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/18-nov-22\/","title":{"rendered":"Concatenaci\u00f3n de una lista de listas"},"content":{"rendered":"<p>Definir, por recursi\u00f3n, la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   conc :: [[a]] -> [a]\n<\/pre>\n<p>tal que <code>conc xss<\/code> es la concenaci\u00f3n de las listas de <code>xss<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   conc [[1,3],[2,4,6],[1,9]]  ==  [1,3,2,4,6,1,9]\n<\/pre>\n<p>Comprobar con QuickCheck que la longitud de <code>conc xss<\/code> es la suma de las longitudes de los elementos de <code>xss<\/code>.<\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nconc1 :: [[a]] -> [a]\nconc1 xss = [x | xs <- xss, x <- xs]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nconc2 :: [[a]] -> [a]\nconc2 []       = []\nconc2 (xs:xss) = xs ++ conc2 xss\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nconc3 :: [[a]] -> [a]\nconc3 = foldr (++) []\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nconc4 :: [[a]] -> [a]\nconc4 = concat\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_conc :: [[Int]] -> Bool\nprop_conc xss =\n  all (== conc1 xss)\n      [conc2 xss,\n       conc3 xss,\n       conc4 xss]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_conc\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (conc1 [[1..n] | n <- [1..5000]])\n--    12502500\n--    (2.72 secs, 1,802,391,200 bytes)\n--    \u03bb> length (conc2 [[1..n] | n <- [1..5000]])\n--    12502500\n--    (0.27 secs, 1,602,351,160 bytes)\n--    \u03bb> length (conc3 [[1..n] | n <- [1..5000]])\n--    12502500\n--    (0.28 secs, 1,602,071,192 bytes)\n--    \u03bb> length (conc4 [[1..n] | n <- [1..5000]])\n--    12502500\n--    (0.26 secs, 1,602,071,184 bytes)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_long_conc :: [[Int]] -> Bool\nprop_long_conc xss =\n  length (conc1 xss) == sum (map length xss)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_long_conc\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom functools import reduce\nfrom operator import concat\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import Any, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nsetrecursionlimit(10**6)\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef conc1(xss: list[list[A]]) -> list[A]:\n    return [x for xs in xss for x in xs]\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef conc2(xss: list[list[A]]) -> list[A]:\n    if not xss:\n        return []\n    return xss[0] + conc2(xss[1:])\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef conc3(xss: Any) -> Any:\n    return reduce(concat, xss)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef conc4(xss: list[list[A]]) -> list[A]:\n    r = []\n    for xs in xss:\n        for x in xs:\n            r.append(x)\n    return r\n\n# La propiedad es\n@given(st.lists(st.lists(st.integers()), min_size=1))\ndef test_conc(xss: list[list[int]]) -> None:\n    r = conc1(xss)\n    assert conc2(xss) == r\n    assert conc3(xss) == r\n    assert conc4(xss) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q contenacion_de_una_lista_de_listas.py\n#    1 passed in 0.63s\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('conc1([list(range(n)) for n in range(1500)])')\n#    0.04 segundos\n#    >>> tiempo('conc2([list(range(n)) for n in range(1500)])')\n#    6.28 segundos\n#    >>> tiempo('conc3([list(range(n)) for n in range(1500)])')\n#    2.55 segundos\n#    >>> tiempo('conc4([list(range(n)) for n in range(1500)])')\n#    0.09 segundos\n#\n#    >>> tiempo('conc1([list(range(n)) for n in range(10000)])')\n#    2.01 segundos\n#    >>> tiempo('conc4([list(range(n)) for n in range(10000)])')\n#    2.90 segundos\n#\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# La propiedad es\n@given(st.lists(st.lists(st.integers()), min_size=1))\ndef test_long_conc(xss: list[list[int]]) -> None:\n    assert len(conc1(xss)) == sum(map(len, xss))\n\n# prop_long_conc :: [[Int]] -> Bool\n# prop_long_conc xss =\n#   length (conc1 xss) == sum (map length xss)\n#\n# La comprobaci\u00f3n es\n#    \u03bb> quickCheck prop_long_conc\n#    +++ OK, passed 100 tests.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir, por recursi\u00f3n, la funci\u00f3n conc :: [[a]] -> [a] tal que conc xss es la concenaci\u00f3n de las listas de xss. Por ejemplo, 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\u00f3n se muestran las soluciones&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7521"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=7521"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7521\/revisions"}],"predecessor-version":[{"id":7645,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7521\/revisions\/7645"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7521"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7521"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7521"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}