{"id":7525,"date":"2022-11-21T06:00:08","date_gmt":"2022-11-21T04:00:08","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7525"},"modified":"2023-04-14T17:06:21","modified_gmt":"2023-04-14T15:06:21","slug":"21-nov-22","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/21-nov-22\/","title":{"rendered":"Aplica seg\u00fan propiedad"},"content":{"rendered":"<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   filtraAplica :: (a -> b) -> (a -> Bool) -> [a] -> [b]\n<\/pre>\n<p>tal que <code>filtraAplica f p xs<\/code> es la lista obtenida aplic\u00e1ndole a los elementos de <code>xs<\/code> que cumplen el predicado <code>p<\/code> la funci\u00f3n <code>f<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   filtraAplica (4+) (<3) [1..7]  ==  [5,6]\n<\/pre>\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\">\nimport Test.QuickCheck.HigherOrder (quickCheck')\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nfiltraAplica1 :: (a -> b) -> (a -> Bool) -> [a] -> [b]\nfiltraAplica1 f p xs = [f x | x <- xs, p x]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nfiltraAplica2 :: (a -> b) -> (a -> Bool) -> [a] -> [b]\nfiltraAplica2 f p xs = map f (filter p xs)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nfiltraAplica3 :: (a -> b) -> (a -> Bool) -> [a] -> [b]\nfiltraAplica3 _ _ [] = []\nfiltraAplica3 f p (x:xs) | p x       = f x : filtraAplica3 f p xs\n                         | otherwise = filtraAplica3 f p xs\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nfiltraAplica4 :: (a -> b) -> (a -> Bool) -> [a] -> [b]\nfiltraAplica4 f p = foldr g []\n  where g x y | p x       = f x : y\n              | otherwise = y\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nfiltraAplica5 :: (a -> b) -> (a -> Bool) -> [a] -> [b]\nfiltraAplica5 f p =\n  foldr (\\x y -> if p x then f x : y else y) []\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_filtraAplica :: (Int -> Int) -> (Int -> Bool) -> [Int] -> Bool\nprop_filtraAplica f p xs =\n  all (== filtraAplica1 f p xs)\n      [filtraAplica2 f p xs,\n       filtraAplica3 f p xs,\n       filtraAplica4 f p xs,\n       filtraAplica5 f p xs]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck' prop_filtraAplica\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> sum (filtraAplica1 id even [1..5*10^6])\n--    6250002500000\n--    (2.92 secs, 1,644,678,696 bytes)\n--    \u03bb> sum (filtraAplica2 id even [1..5*10^6])\n--    6250002500000\n--    (1.17 secs, 1,463,662,848 bytes)\n--    \u03bb> sum (filtraAplica3 id even [1..5*10^6])\n--    6250002500000\n--    (3.18 secs, 1,964,678,640 bytes)\n--    \u03bb> sum (filtraAplica4 id even [1..5*10^6])\n--    6250002500000\n--    (2.64 secs, 1,924,678,752 bytes)\n--    \u03bb> sum (filtraAplica5 id even [1..5*10^6])\n--    6250002500000\n--    (2.61 secs, 1,824,678,712 bytes)\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 sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import Callable, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nsetrecursionlimit(10**6)\n\nA = TypeVar('A')\nB = TypeVar('B')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef filtraAplica1(f: Callable[[A], B],\n                  p: Callable[[A], bool],\n                  xs: list[A]) -> list[B]:\n    return [f(x) for x in xs if p(x)]\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef filtraAplica2(f: Callable[[A], B],\n                  p: Callable[[A], bool],\n                  xs: list[A]) -> list[B]:\n    return list(map(f, filter(p, xs)))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef filtraAplica3(f: Callable[[A], B],\n                  p: Callable[[A], bool],\n                  xs: list[A]) -> list[B]:\n    if not xs:\n        return []\n    if p(xs[0]):\n        return [f(xs[0])] + filtraAplica3(f, p, xs[1:])\n    return filtraAplica3(f, p, xs[1:])\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef filtraAplica4(f: Callable[[A], B],\n                  p: Callable[[A], bool],\n                  xs: list[A]) -> list[B]:\n    def g(ys: list[B], x: A) -> list[B]:\n        if p(x):\n            return ys + [f(x)]\n        return ys\n\n    return reduce(g, xs, [])\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef filtraAplica5(f: Callable[[A], B],\n                  p: Callable[[A], bool],\n                  xs: list[A]) -> list[B]:\n    r = []\n    for x in xs:\n        if p(x):\n            r.append(f(x))\n    return r\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.lists(st.integers()))\ndef test_filtraAplica(xs: list[int]) -> None:\n    def f(x: int) -> int:\n        return x + 4\n    def p(x: int) -> bool:\n        return x < 3\n    r = filtraAplica1(f, p, xs)\n    assert filtraAplica2(f, p, xs) == r\n    assert filtraAplica3(f, p, xs) == r\n    assert filtraAplica4(f, p, xs) == r\n    assert filtraAplica5(f, p, xs) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q aplica_segun_propiedad.py\n#    1 passed in 0.25s\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('filtraAplica1(lambda x: x, lambda x: x % 2 == 0, range(10**5))')\n#    0.02 segundos\n#    >>> tiempo('filtraAplica2(lambda x: x, lambda x: x % 2 == 0, range(10**5))')\n#    0.01 segundos\n#    >>> tiempo('filtraAplica3(lambda x: x, lambda x: x % 2 == 0, range(10**5))')\n#    Process Python violaci\u00f3n de segmento (core dumped)\n#    >>> tiempo('filtraAplica4(lambda x: x, lambda x: x % 2 == 0, range(10**5))')\n#    4.07 segundos\n#    >>> tiempo('filtraAplica5(lambda x: x, lambda x: x % 2 == 0, range(10**5))')\n#    0.01 segundos\n#\n#    >>> tiempo('filtraAplica1(lambda x: x, lambda x: x % 2 == 0, range(10**7))')\n#    1.66 segundos\n#    >>> tiempo('filtraAplica2(lambda x: x, lambda x: x % 2 == 0, range(10**7))')\n#    1.00 segundos\n#    >>> tiempo('filtraAplica5(lambda x: x, lambda x: x % 2 == 0, range(10**7))')\n#    1.21 segundos\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir la funci\u00f3n filtraAplica :: (a -> b) -> (a -> Bool) -> [a] -> [b] tal que filtraAplica f p xs es la lista obtenida aplic\u00e1ndole a los elementos de xs que cumplen el predicado p la funci\u00f3n f. Por ejemplo, filtraAplica (4+) ( sum (filtraAplica1 id even [1..5*10^6]) &#8212; 6250002500000 &#8212; (2.92 secs,&#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\/7525"}],"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=7525"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7525\/revisions"}],"predecessor-version":[{"id":8051,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7525\/revisions\/8051"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7525"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7525"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7525"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}