{"id":7114,"date":"2022-07-05T06:00:28","date_gmt":"2022-07-05T04:00:28","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7114"},"modified":"2022-07-06T10:49:35","modified_gmt":"2022-07-06T08:49:35","slug":"union-e-interseccion-general-de-conjuntos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/union-e-interseccion-general-de-conjuntos\/","title":{"rendered":"Uni\u00f3n e intersecci\u00f3n general de conjuntos"},"content":{"rendered":"<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   unionGeneral        :: Eq a => [[a]] -> [a]\n   interseccionGeneral :: Eq a => [[a]] -> [a]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(unionGeneral xs) es la uni\u00f3n de los conjuntos de la lista de conjuntos xs (es decir, el conjunto de los elementos que pertenecen a alguno de los elementos de xs). Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     unionGeneral []                    ==  []\n     unionGeneral [[1]]                 ==  [1]\n     unionGeneral [[1],[1,2],[2,3]]     ==  [1,2,3]\n     unionGeneral ([[x] | x <- [1..9]]) ==  [1,2,3,4,5,6,7,8,9]\n<\/pre>\n<ul>\n<li>(interseccionGeneral xs) es la intersecci\u00f3n de los conjuntos de la lista de conjuntos xs (es decir, el conjunto de los elementos que pertenecen a todos los elementos de xs). Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     interseccionGeneral [[1]]                      ==  [1]\n     interseccionGeneral [[2],[1,2],[2,3]]          ==  [2]\n     interseccionGeneral [[2,7,5],[1,5,2],[5,2,3]]  ==  [2,5]\n     interseccionGeneral ([[x] | x <- [1..9]])      ==  []\n     interseccionGeneral (replicate (10^6) [1..5])  ==  [1,2,3,4,5]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (foldl', foldl1', intersect, nub, union)\nimport Test.QuickCheck (NonEmptyList (NonEmpty), quickCheck)\n\n-- 1\u00aa definici\u00f3n de unionGeneral\n-- =============================\n\nunionGeneral1 :: Eq a => [[a]] -> [a]\nunionGeneral1 []     = []\nunionGeneral1 (x:xs) = x `union` unionGeneral1 xs \n\n-- 2\u00aa definici\u00f3n de unionGeneral\n-- =============================\n\nunionGeneral2 :: Eq a => [[a]] -> [a]\nunionGeneral2 = foldr union []\n\n-- 3\u00aa definici\u00f3n de unionGeneral\n-- =============================\n\nunionGeneral3 :: Eq a => [[a]] -> [a]\nunionGeneral3 = foldl' union []\n\n-- Comprobaci\u00f3n de equivalencia de unionGeneral\n-- ============================================\n\n-- La propiedad es\nprop_unionGeneral :: [[Int]] -> Bool\nprop_unionGeneral xss =\n  all (== unionGeneral1 xss')\n      [unionGeneral2 xss',\n       unionGeneral3 xss']\n  where xss' = nub (map nub xss)\n  \n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_unionGeneral\n--    +++ OK, passed 100 tests.\n--    (0.85 secs, 1,017,807,600 bytes)\n\n-- Comparaci\u00f3n de eficiencia de unionGeneral\n-- =========================================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (unionGeneral1 ([[x] | x <- [1..10^3]]))\n--    1000\n--    (1.56 secs, 107,478,456 bytes)\n--    \u03bb> length (unionGeneral2 ([[x] | x <- [1..10^3]]))\n--    1000\n--    (1.50 secs, 107,406,560 bytes)\n--    \u03bb> length (unionGeneral3 ([[x] | x <- [1..10^3]]))\n--    1000\n--    (0.07 secs, 92,874,024 bytes)\n\n-- 1\u00aa definici\u00f3n de interseccionGeneral\n-- ====================================\n\ninterseccionGeneral1 :: Eq a => [[a]] -> [a]\ninterseccionGeneral1 [x]    = x\ninterseccionGeneral1 (x:xs) = x `intersect` interseccionGeneral1 xs \n\n-- 2\u00aa definici\u00f3n de interseccionGeneral\n-- ====================================\n\ninterseccionGeneral2 :: Eq a => [[a]] -> [a]\ninterseccionGeneral2 = foldr1 intersect\n\n-- 3\u00aa definici\u00f3n de interseccionGeneral\n-- ====================================\n\ninterseccionGeneral3 :: Eq a => [[a]] -> [a]\ninterseccionGeneral3 = foldl1' intersect\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_interseccionGeneral :: NonEmptyList [Int] -> Bool\nprop_interseccionGeneral (NonEmpty xss) =\n  all (== interseccionGeneral1 xss')\n      [interseccionGeneral2 xss',\n       interseccionGeneral3 xss']\n  where xss' = nub (map nub xss)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_interseccionGeneral\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> interseccionGeneral1 (replicate (10^6) [1..5])\n--    [1,2,3,4,5]\n--    (2.02 secs, 1,173,618,400 bytes)\n--    \u03bb> interseccionGeneral2 (replicate (10^6) [1..5])\n--    [1,2,3,4,5]\n--    (1.83 secs, 1,092,120,224 bytes)\n--    \u03bb> interseccionGeneral3 (replicate (10^6) [1..5])\n--    [1,2,3,4,5]\n--    (1.33 secs, 985,896,136 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Union_e_interseccion_general.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Definir las funciones unionGeneral :: Eq a => [[a]] -> [a] interseccionGeneral :: Eq a => [[a]] -> [a] tales que (unionGeneral xs) es la uni\u00f3n de los conjuntos de la lista de conjuntos xs (es decir, el conjunto de los elementos que pertenecen a alguno de los elementos de xs). Por ejemplo, unionGeneral []&#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":[2],"tags":[519],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7114"}],"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=7114"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7114\/revisions"}],"predecessor-version":[{"id":7115,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7114\/revisions\/7115"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7114"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7114"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7114"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}