{"id":8021,"date":"2023-04-11T06:00:12","date_gmt":"2023-04-11T04:00:12","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8021"},"modified":"2023-03-23T13:00:07","modified_gmt":"2023-03-23T11:00:07","slug":"11-abr-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/11-abr-23\/","title":{"rendered":"Relaciones totales"},"content":{"rendered":"<p>Usando el <a href=\"https:\/\/bit.ly\/3IVVqOT\">tipo de las relaciones binarias<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   total :: Eq a => Rel a -> Bool\n<\/pre>\n<p>tal que <code>total r<\/code> se verifica si la relaci\u00f3n <code>r<\/code> es total; es decir, si para cualquier par x, y de elementos del universo de r, se tiene que x est\u00e1 relacionado con y o y est\u00e1 relacionado con x. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   total (R ([1,3],[(1,1),(3,1),(3,3)]))  ==  True\n   total (R ([1,3],[(1,1),(3,1)]))        ==  False\n   total (R ([1,3],[(1,1),(3,3)]))        ==  False\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 Relaciones_binarias (Rel(R))\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntotal :: Eq a => Rel a -> Bool\ntotal (R (u,g)) =\n  and [(x,y) `elem` g || (y,x) `elem` g | x <- u, y <- u]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ntotal2 :: Eq a => Rel a -> Bool\ntotal2 (R (u,g)) =\n  all (relacionados g) (producto u u)\n\n-- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo,\n--    \u03bb> producto [2,5] [1,4,6]\n--    [(2,1),(2,4),(2,6),(5,1),(5,4),(5,6)]\nproducto :: [a] -> [a] -> [(a,a)]\nproducto xs ys =\n  [(x,y) | x <- xs, y <- ys]\n\n-- (relacionados g (x,y)) se verifica si los elementos x e y est\u00e1n\n-- relacionados por la relaci\u00f3n de grafo g. Por ejemplo,\n--    relacionados [(2,3),(3,1)] (2,3)  ==  True\n--    relacionados [(2,3),(3,1)] (3,2)  ==  True\n--    relacionados [(2,3),(3,1)] (1,2)  ==  False\nrelacionados :: Eq a => [(a,a)] -> (a,a) -> Bool\nrelacionados g (x,y) =\n  (x,y) `elem` g || (y,x) `elem` g\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ntotal3 :: Eq a => Rel a -> Bool\ntotal3 (R (u,g)) = aux1 u\n  where aux1 []       = True\n        aux1 (x:xs)   = aux2 x u && aux1 xs\n        aux2 _ []     = True\n        aux2 x (y:ys) = relacionados g (x,y) && aux2 x ys\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_total :: Rel Int -> Bool\nprop_total r =\n  all (== total r)\n      [total2 r,\n       total3 r]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_total\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 typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.Relaciones_binarias import Rel, relacionArbitraria\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef total(r: Rel[A]) -> bool:\n    (u, g) = r\n    return all(((x, y) in g or (y, x) in g for x in u for y in u))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# producto(xs, ys) es el producto cartesiano de xs e ys. Por ejemplo,\n#    >>> producto([2, 5], [1, 4, 6])\n#    [(2, 1), (2, 4), (2, 6), (5, 1), (5, 4), (5, 6)]\ndef producto(xs: list[A], ys: list[A]) -> list[tuple[A,A]]:\n    return [(x, y) for x in xs for y in ys]\n\n# relacionados(g, (x, y)) se verifica si los elementos x e y est\u00e1n\n# relacionados por la relaci\u00f3n de grafo g. Por ejemplo,\n#    relacionados([(2, 3), (3, 1)], (2, 3))  ==  True\n#    relacionados([(2, 3), (3, 1)], (3, 2))  ==  True\n#    relacionados([(2, 3), (3, 1)], (1, 2))  ==  False\ndef relacionados(g: list[tuple[A,A]], p: tuple[A,A]) -> bool:\n    (x, y) = p\n    return (x, y) in g or (y, x) in g\n\ndef total2(r: Rel[A]) -> bool:\n    (u, g) = r\n    return all(relacionados(g, p) for p in producto(u, u))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef total3(r: Rel[A]) -> bool:\n    u, g = r\n    return all(relacionados(g, (x, y)) for x in u for y in u)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef total4(r: Rel[A]) -> bool:\n    (u, g) = r\n    def aux2(x: A, ys: list[A]) -> bool:\n        if not ys:\n            return True\n        return relacionados(g, (x, ys[0])) and aux2(x, ys[1:])\n\n    def aux1(xs: list[A]) -> bool:\n        if not xs:\n            return True\n        return aux2(xs[0], u) and aux1(xs[1:])\n\n    return aux1(u)\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef total5(r: Rel[A]) -> bool:\n    (u, g) = r\n    for x in u:\n        for y in u:\n            if not relacionados(g, (x, y)):\n                return False\n    return True\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=10))\ndef test_total(n: int) -> None:\n    r = relacionArbitraria(n)\n    res = total(r)\n    assert total2(r) == res\n    assert total3(r) == res\n    assert total4(r) == res\n    assert total5(r) == res\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q Relaciones_totales.py\n#    1 passed in 0.11s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Usando el tipo de las relaciones binarias, definir la funci\u00f3n total :: Eq a => Rel a -> Bool tal que total r se verifica si la relaci\u00f3n r es total; es decir, si para cualquier par x, y de elementos del universo de r, se tiene que x est\u00e1 relacionado con y o y&#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":[576],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8021"}],"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=8021"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8021\/revisions"}],"predecessor-version":[{"id":8023,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8021\/revisions\/8023"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8021"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8021"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8021"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}