{"id":4848,"date":"2015-04-06T20:08:55","date_gmt":"2015-04-06T18:08:55","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4848"},"modified":"2015-04-07T17:17:25","modified_gmt":"2015-04-07T15:17:25","slug":"i1m2014-operaciones-con-conjuntos-usando-la-libreria-data-set-de-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-operaciones-con-conjuntos-usando-la-libreria-data-set-de-haskell\/","title":{"rendered":"I1M2014: Operaciones con conjuntos usando la librer\u00eda Data.Set de Haskell"},"content":{"rendered":"

En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 27 sobre operaciones con conjuntos usando la librer\u00eda Data.Set<\/a> de Haskell.<\/p>\n

Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n
\n<\/p>\n

\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n es hacer los ejercicios de la relaci\u00f3n 19\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-- \u00a7 Ejercicios                                                       --\n-- ---------------------------------------------------------------------\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--    uni\u00f3n :: Ord a => Set a -> Set a -> Set a\n-- tal (uni\u00f3n c1 c2) es la uni\u00f3n de ambos conjuntos. Por ejemplo,\n--    ghci> uni\u00f3n (fromList [3,2,5]) (fromList [2,7,5])\n--    fromList [2,3,5,7]\n-- ---------------------------------------------------------------------\n\nuni\u00f3n :: Ord a => Set a -> Set a -> Set a\nuni\u00f3n = 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    (union c1 c2) \\\\ (intersection c1 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\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-- ---------------------------------------------------------------------\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\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-- ---------------------------------------------------------------------\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":"
En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 27 sobre operaciones con conjuntos usando la librer\u00eda Data.Set de Haskell. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"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":[238],"tags":[270,305],"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\/4848"}],"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=4848"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4848\/revisions"}],"predecessor-version":[{"id":4852,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4848\/revisions\/4852"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4848"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4848"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4848"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}