{"id":6609,"date":"2019-04-03T11:10:34","date_gmt":"2019-04-03T09:10:34","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6609"},"modified":"2019-04-05T19:45:44","modified_gmt":"2019-04-05T17:45:44","slug":"i1m2018-operaciones-con-conjuntos-con-la-libreria-data-set","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-operaciones-con-conjuntos-con-la-libreria-data-set\/","title":{"rendered":"I1M2018: Operaciones con conjuntos con la librer\u00eda Data.Set"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han resuelto ejercicios de la relaci\u00f3n 30 sobre operaciones con conjuntos con la librer\u00eda Data.Set.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n es hacer los ejercicios de la relaci\u00f3n 29\n-- sobre operaciones con conjuntos usando la librer\u00eda Data.Set\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Data.Set as S\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    subconjunto :: Ord a => Set a -> Set a -> Bool\n-- tal que (subconjunto c1 c2) se verifica si todos los elementos de c1 \n-- pertenecen a c2. Por ejemplo,         \n--    subconjunto (fromList [2..100000]) (fromList [1..100000]) == True\n--    subconjunto (fromList [1..100000]) (fromList [2..100000]) == False\n-- ---------------------------------------------------------------------\n\nsubconjunto :: Ord a => Set a -> Set a -> Bool\nsubconjunto = isSubsetOf\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool\n-- tal (subconjuntoPropio c1 c2) se verifica si c1 es un subconjunto \n-- propio de c2. Por ejemplo,\n--   subconjuntoPropio (fromList [2..5]) (fromList [1..7]) == True\n--   subconjuntoPropio (fromList [2..5]) (fromList [1..4]) == False\n--   subconjuntoPropio (fromList [2..5]) (fromList [2..5]) == False\n-- ---------------------------------------------------------------------\n\nsubconjuntoPropio :: Ord a => Set a -> Set a -> Bool\nsubconjuntoPropio = isProperSubsetOf\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    unitario :: Ord a => a -> Set a \n-- tal que (unitario x) es el conjunto {x}. Por ejemplo,\n--   unitario 5 == fromList [5]\n-- ---------------------------------------------------------------------\n\nunitario :: Ord a => a -> Set a \nunitario = singleton\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    cardinal :: Set a -> Int\n-- tal que (cardinal c) es el n\u00famero de elementos del conjunto c. Por\n-- ejemplo,\n--    cardinal (fromList [3,2,5,1,2,3])  ==  4\n-- ---------------------------------------------------------------------\n\ncardinal :: Set a -> Int\ncardinal = size\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    union' :: Ord a => Set a -> Set a -> Set a\n-- tal (union' c1 c2) es la uni\u00f3n de ambos conjuntos. Por ejemplo,\n--    ghci> union' (fromList [3,2,5]) (fromList [2,7,5])\n--    fromList [2,3,5,7]\n-- ---------------------------------------------------------------------\n\nunion' :: Ord a => Set a -> Set a -> Set a\nunion' = union\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    unionG:: Ord a => [Set a] -> Set a\n-- tal (unionG cs) calcule la uni\u00f3n de la lista de conjuntos cd. Por\n-- ejemplo,\n--    ghci> unionG [fromList [3,2], fromList [2,5], fromList [3,5,7]]\n--    fromList [2,3,5,7]\n-- ---------------------------------------------------------------------\n\nunionG :: Ord a => [Set a] -> Set a\nunionG = unions\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    interseccion :: Ord a => Set a -> Set a -> Set a\n-- tal que (interseccion c1 c2) es la intersecci\u00f3n de los conjuntos c1 y\n-- c2. Por ejemplo,\n--    ghci> interseccion (fromList [1..7]) (fromList [4..9])\n--    fromList [4,5,6,7]\n--    ghci> interseccion (fromList [2..1000000]) (fromList [1])\n--    fromList []\n-- ---------------------------------------------------------------------\n\ninterseccion :: Ord a => Set a -> Set a -> Set a\ninterseccion = intersection\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    interseccionG:: Ord a => [Set a] -> Set a\n-- tal que (interseccionG cs) es la intersecci\u00f3n de la lista de\n-- conjuntos cs. Por ejemplo,\n--    ghci> interseccionG [fromList [3,2], fromList [2,5,3], fromList [3,5,7]]\n--    fromList [3]\n-- ---------------------------------------------------------------------\n\ninterseccionG :: Ord a => [Set a] -> Set a\ninterseccionG [c]      = c\ninterseccionG (cs:css) = intersection cs (interseccionG css)\n\n-- Se puede definir por plegado\ninterseccionG2 :: Ord a => [Set a] -> Set a\ninterseccionG2 = foldr1 interseccion \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    disjuntos :: Ord a => Set a -> Set a -> Bool\n-- tal que (disjuntos c1 c2) se verifica si los conjuntos c1 y c2 son\n-- disjuntos. Por ejemplo,\n--   disjuntos (fromList [2..5]) (fromList [6..9]) == True\n--   disjuntos (fromList [2..5]) (fromList [1..9]) == False\n-- ---------------------------------------------------------------------\n\ndisjuntos :: Ord a => Set a -> Set a -> Bool\ndisjuntos c1 c2 = S.null (intersection c1 c2)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    diferencia :: Ord a => Set a -> Set a -> Set a\n-- tal que (diferencia c1 c2) es el conjunto de los elementos de c1 que\n-- no son elementos de c2. Por ejemplo,\n--    ghci> diferencia (fromList [2,5,3]) (fromList [1,4,5])\n--    fromList [2,3]\n-- ---------------------------------------------------------------------\n\ndiferencia :: Ord a => Set a -> Set a -> Set a\ndiferencia = difference\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir la funci\u00f3n\n--    diferenciaSimetrica :: Ord a => Set a -> Set a -> Set a\n-- tal que (diferenciaSimetrica c1 c2) es la diferencia sim\u00e9trica de los\n-- conjuntos c1 y c2. Por ejemplo,\n--    ghci> diferenciaSimetrica (fromList [3,2,5]) (fromList [1,5])\n--    fromList [1,2,3]\n-- ---------------------------------------------------------------------\n\ndiferenciaSimetrica :: Ord a => Set a -> Set a -> Set a\ndiferenciaSimetrica c1 c2 = \n  (c1 `union` c2) \\\\ (c1 `intersection` c2)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    filtra :: (a -> Bool) -> Set a -> Set a\n-- tal (filtra p c) es el conjunto de elementos de c que verifican el\n-- predicado p. Por ejemplo,\n--    filtra even (fromList [3,2,5,6,8,9])  ==  fromList [2,6,8]\n--    filtra odd  (fromList [3,2,5,6,8,9])  ==  fromList [3,5,9]\n-- ---------------------------------------------------------------------\n\nfiltra :: (a -> Bool) -> Set a -> Set a\nfiltra = S.filter\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n\n--    particion :: (a -> Bool) -> Set a -> (Set a, Set a)\n-- tal que (particion c) es el par formado por dos conjuntos: el de sus\n-- elementos que verifican p y el de los elementos que no lo verifica. \n-- Por ejemplo,\n--    ghci> particion even (fromList [3,2,5,6,8,9])\n--    (fromList [2,6,8],fromList [3,5,9])\n-- ---------------------------------------------------------------------\n\nparticion :: (a -> Bool) -> Set a -> (Set a, Set a)\nparticion = partition\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la funci\u00f3n\n--    divide :: (Ord a) => a-> Set a -> (Set a, Set a)\n-- tal que (divide x c) es el par formado por dos subconjuntos de c: el\n-- de los elementos menores que x y el de los mayores que x. Por ejemplo,\n--    ghci> divide 5 (fromList [3,2,9,5,8,6])\n--    (fromList [2,3],fromList [6,8,9])\n-- ---------------------------------------------------------------------\n\ndivide :: Ord a => a-> Set a -> (Set a, Set a)\ndivide = split\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Definir la funci\u00f3n\n--    mapC :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b\n-- tal que (map f c) es el conjunto formado por las im\u00e1genes de los\n-- elementos de c, mediante f. Por ejemplo,\n--    mapC (*2) (fromList [1..4])  ==  fromList [2,4,6,8]\n-- ---------------------------------------------------------------------\n\nmapC :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b\nmapC = S.map\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. Definir la funci\u00f3n\n--    everyC :: Ord a => (a -> Bool) -> Set a -> Bool\n-- tal que (everyC p c) se verifica si todos los elementos de c\n-- verifican el predicado p.  Por ejemplo,\n--   everyC even (fromList [2,4..10]) == True\n--   everyC even (fromList [2..10])   == False\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\neveryC :: Ord a => (a -> Bool) -> Set a -> Bool\neveryC p c | S.null c  = True\n           | otherwise = p x && everyC p c1\n  where (x,c1) = deleteFindMin c\n\n-- 2\u00aa definici\u00f3n\neveryC2 :: Ord a => (a -> Bool) -> Set a -> Bool\neveryC2 p = S.foldr (\\x r -> p x && r) True\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Definir la funci\u00f3n\n--    someC :: Ord a => (a -> Bool) -> Set a -> Bool\n-- tal que (someC p c) se verifica si alg\u00fan elemento de c verifica el\n-- predicado p. Por ejemplo,\n--   someC even (fromList [1,4,7]) == True\n--   someC even (fromList [1,3,7]) == False\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\nsomeC :: Ord a => (a -> Bool) -> Set a -> Bool\nsomeC p c | S.null c  = False\n          | otherwise = p x || someC p c1\n  where (x,c1) = deleteFindMin c\n\n-- 2\u00aa definici\u00f3n\nsomeC2 :: Ord a => (a -> Bool) -> Set a -> Bool\nsomeC2 p = S.foldr (\\x r -> p x || r) False\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 18. Definir la funci\u00f3n\n--    productoC :: (Ord a, Ord b) => Set a -> Set b -> Set (a,b)\n-- tal que (productoC c1 c2) es el producto cartesiano de los \n-- conjuntos c1 y c2. Por ejemplo,\n--    ghci> productoC (fromList [1,3]) (fromList [2,4])\n--    fromList [(1,2),(1,4),(3,2),(3,4)]\n-- ---------------------------------------------------------------------\n\nproductoC :: (Ord a, Ord b) => Set a -> Set b -> Set (a,b)\nproductoC c1 c2 = \n  fromList [(x,y) | x <- elems c1, y <- elems c2]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 19. Definir la funci\u00f3n\n--    potencia :: Ord a => Set a -> Set (Set a)\n-- tal que (potencia c) es el conjunto potencia de c; es decir, el\n-- conjunto de todos los subconjuntos de c. Por ejemplo,\n--    ghci> potencia (fromList [1..3])\n--    fromList [fromList [],fromList [1],fromList [1,2],fromList [1,2,3],\n--              fromList [1,3],fromList [2],fromList [2,3],fromList [3]]\n-- ---------------------------------------------------------------------\n\npotencia :: Ord a => Set a -> Set (Set a)\npotencia c | S.null c  = singleton empty\n           | otherwise = S.map (insert x) pr `union` pr\n    where (x,rc) = deleteFindMin c\n          pr     = potencia rc\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han resuelto ejercicios de la relaci\u00f3n 30 sobre operaciones con conjuntos con la librer\u00eda Data.Set. Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[320],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6609"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=6609"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6609\/revisions"}],"predecessor-version":[{"id":6613,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6609\/revisions\/6613"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6609"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6609"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6609"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}