{"id":5399,"date":"2016-04-08T19:30:22","date_gmt":"2016-04-08T17:30:22","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5399"},"modified":"2016-04-09T10:31:12","modified_gmt":"2016-04-09T08:31:12","slug":"i1m2015-el-tad-de-los-multiconjuntos-mediante-diccionarios-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-el-tad-de-los-multiconjuntos-mediante-diccionarios-en-haskell\/","title":{"rendered":"I1M2015: El TAD de los multiconjuntos mediante diccionarios en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 30 sobre los multiconjuntos mediante diccionarios.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- Un multiconjunto es una colecci\u00f3n de elementos en los que no importa\n-- el orden de los elementos, pero s\u00ed el n\u00famero de veces en que\n-- aparecen. Por ejemplo, la factorizaci\u00f3n prima de un n\u00famero se puede\n-- representar como un multiconjunto de n\u00fameros primos. \n-- \n-- El objetivo de esta relaci\u00f3n de ejercicios es implementar el TAD de\n-- los multiconjuntos utilizando los diccionarios estudiados en el tema\n-- 29 https:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/temas\/tema-29.html\n-- \n-- El manual, con ejemplos, de la librer\u00eda Data.Map se encuentra en\n-- http:\/\/bit.ly\/25B1na0\n\n-- ---------------------------------------------------------------------\n-- Librer\u00edas auxiliares                                               --\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\nimport qualified Data.Map as M\n\n-- ---------------------------------------------------------------------\n-- El tipo de dato de multiconjuntos                                  --\n-- ---------------------------------------------------------------------\n\n-- Un multiconjunto se puede representar mediante un diccionario donde\n-- las claves son los elementos del multiconjunto y sus valores sus\n-- n\u00fameros de ocurrencias. Por ejemplo, el multiconjunto \n--    {a, b, a, c, b, a, e}\n-- se representa por el diccionario\n--    [(a,3), (b,2), (c,1), (e,1)]\n\ntype MultiConj a = M.Map a Int\n \n-- ---------------------------------------------------------------------\n-- Construcciones de multiconjuntos                                   --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la constante\n--    vacio :: MultiConj a\n-- para el multiconjunto vac\u00edo. Por ejemplo,\n--    vacio  ==  fromList []\n-- ---------------------------------------------------------------------\n\nvacio :: MultiConj a\nvacio = M.empty\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    unitario :: a -> MultiConj a\n-- tal que (unitario x) es el multiconjunto cuyo \u00fanico elemento es\n-- x. Por ejemplo,\n--    unitario 'a'  ==  fromList [('a',1)]\n-- ---------------------------------------------------------------------\n\nunitario :: a -> MultiConj a\nunitario x = M.singleton x 1\n\n-- ---------------------------------------------------------------------\n-- A\u00f1adir y quitar elementos                                          --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    inserta :: Ord a => a -> MultiConj a -> MultiConj a\n-- tal que (inserta x m) es el multiconjunto obtenido a\u00f1adi\u00e9ndole a m el \n-- elemento x. Por ejemplo,\n--    ghci> inserta 'a' (unitario 'a')\n--    fromList [('a',2)]\n--    ghci> inserta 'b' it\n--    fromList [('a',2),('b',1)]\n--    ghci> inserta 'a' it\n--    fromList [('a',3),('b',1)]\n--    ghci> inserta 'b' it\n--    fromList [('a',3),('b',2)]\n-- ---------------------------------------------------------------------\n\ninserta :: Ord a => a -> MultiConj a -> MultiConj a\ninserta x = M.insertWith (+) x 1\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n \n--    listaAmc :: Ord a => [a] -> MultiConj a\n-- tal que (listaAmc xs) es el multiconjunto cuyos elementos son los de\n-- la lista xs. Por ejemplo,\n--    listaAmc \"ababc\"  ==  fromList [('a',2),('b',2),('c',1)]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\nlistaAmc :: Ord a => [a] -> MultiConj a\nlistaAmc xs = M.fromListWith (+) (zip xs (repeat 1))\n\n-- 2\u00aa soluci\u00f3n\nlistaAmc2 :: Ord a => [a] -> MultiConj a\nlistaAmc2 = foldr inserta vacio\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> listaAmc (replicate 5000000 1)\n--    fromList [(1,5000000)]\n--    (1.52 secs, 1,368,870,760 bytes)\n--    \u03bb> listaAmc2 (replicate 5000000 1)\n--    fromList [(1,5000000)]\n--    (4.20 secs, 2,385,729,056 bytes)\n--    \n--    \u03bb> listaAmc (replicate 10000000 1)\n--    fromList [(1,10000000)]\n--    (2.97 secs, 2,732,899,360 bytes)\n--    \u03bb> listaAmc2 (replicate 10000000 1)\n--    fromList *** Exception: stack overflow\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    insertaVarios :: Ord a => a -> Int -> MultiConj a -> MultiConj a\n-- tal que (insertaVarios x n m) es el multiconjunto obtenido\n-- a\u00f1adi\u00e9ndole a m n copias del elemento x. Por ejemplo, \n--    ghci> insertaVarios 'a' 3 vacio\n--    fromList [('a',3)]\n--    ghci> insertaVarios 'b' 2 it \n--    fromList [('a',3),('b',2)]\n--    ghci> insertaVarios 'a' 2 it \n--    fromList [('a',5),('b',2)]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\ninsertaVarios :: Ord a => a -> Int -> MultiConj a -> MultiConj a\ninsertaVarios = M.insertWith (+) \n\n-- 2\u00aa soluci\u00f3n\ninsertaVarios2 :: Ord a => a -> Int -> MultiConj a -> MultiConj a\ninsertaVarios2 x n m = foldr inserta m (replicate n x)\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> insertaVarios 1 5000000 vacio\n--    fromList [(1,5000000)]\n--    (0.00 secs, 0 bytes)\n--    \u03bb> insertaVarios2 1 5000000 vacio\n--    fromList [(1,5000000)]\n--    (4.24 secs, 2,226,242,792 bytes)\n--    \n--    \u03bb> insertaVarios 1 10000000 vacio\n--    fromList [(1,10000000)]\n--    (0.00 secs, 0 bytes)\n--    \u03bb> insertaVarios2 1 10000000 vacio\n--    fromList *** Exception: stack overflow\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    borra :: Ord a => a -> MultiConj a -> MultiConj a\n-- tal que (borra x m) es el multiconjunto obtenido borrando una\n-- ocurrencia de x en m. Por ejemplo,\n--    ghci> borra 'a' (listaAmc \"ababc\")\n--    fromList [('a',1),('b',2),('c',1)]\n--    ghci> borra 'a' it\n--    fromList [('b',2),('c',1)]\n--    ghci> borra 'a' it\n--    fromList [('b',2),('c',1)]\n-- ---------------------------------------------------------------------\n\nborra :: Ord a => a -> MultiConj a -> MultiConj a\nborra = M.update f\n    where f m | m <= 1    = Nothing\n              | otherwise = Just (m - 1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    borraVarias :: Ord a => a -> Int -> MultiConj a -> MultiConj a\n-- tal que (borraVarias x n m) es el multiconjunto obtenido a partir del\n-- m borrando n ocurrencias del elemento x. Por ejemplo,\n--    ghci> listaAmc \"ababcad\"\n--    fromList [('a',3),('b',2),('c',1),('d',1)]\n--    ghci> borraVarias 'a' 2 (listaAmc \"ababcad\")\n--    fromList [('a',1),('b',2),('c',1),('d',1)]\n--    ghci> borraVarias 'a' 5 (listaAmc \"ababcad\")\n--    fromList [('b',2),('c',1),('d',1)]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\nborraVarias :: Ord a => a -> Int -> MultiConj a -> MultiConj a\nborraVarias x n = M.update (f n) x\n    where f n m | m <= n    = Nothing\n                | otherwise = Just (m - n)\n\n-- 2\u00aa definici\u00f3n\nborraVarias2 :: Ord a => a -> Int -> MultiConj a -> MultiConj a\nborraVarias2 x n m = foldr borra m (replicate n x)\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> borraVarias 1 5000000 (listaAmc (replicate 6000000 1))\n--    fromList [(1,1000000)]\n--    (1.74 secs, 1,594,100,344 bytes)\n--    \u03bb> borraVarias2 1 5000000 (listaAmc (replicate 6000000 1))\n--    fromList [(1,1000000)]\n--    (6.79 secs, 4,424,846,104 bytes)\n--    \n--    \u03bb> borraVarias 1 5000000 (listaAmc (replicate 10000000 1))\n--    fromList [(1,5000000)]\n--    (3.02 secs, 2,768,894,680 bytes)\n--    \u03bb> borraVarias2 1 5000000 (listaAmc (replicate 10000000 1))\n--    fromList *** Exception: stack overflow\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    borraTodas :: Ord a => a -> MultiConj a -> MultiConj a\n-- tal que (borraTodas x m) es el multiconjunto obtenido a partir del\n-- m borrando todas las ocurrencias del elemento x. Por ejemplo,\n--    ghci> borraTodas 'a' (listaAmc \"ababcad\")\n--    fromList [('b',2),('c',1),('d',1)]\n-- ---------------------------------------------------------------------\n\nborraTodas :: Ord a => a -> MultiConj a -> MultiConj a\nborraTodas = M.delete\n\n-- ---------------------------------------------------------------------\n-- Consultas                                                          --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n \n--    esVacio :: MultiConj a -> Bool\n-- tal que (esVacio m) se verifica si el multiconjunto m es vac\u00edo. Por\n-- ejemplo, \n--    esVacio vacio  ==  True\n--    esVacio (inserta 'a' vacio)  ==  False\n-- ---------------------------------------------------------------------\n\nesVacio :: MultiConj a -> Bool\nesVacio = M.null\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    cardinal :: MultiConj a -> Int\n-- tal que (cardinal m) es el n\u00famero de elementos (contando las\n-- repeticiones) del multiconjunto m. Por ejemplo,\n--    cardinal (listaAmc \"ababcad\")  ==  7\n-- ---------------------------------------------------------------------\n\ncardinal :: MultiConj a -> Int\ncardinal = sum . M.elems\n\n-- 2\u00aa definici\u00f3n\ncardinal2 :: MultiConj a -> Int\ncardinal2 m = sum [v | (k,v) <- M.assocs m]\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> cardinal (listaAmc [1..5000000])\n--    5000000\n--    (5.92 secs, 9,071,879,144 bytes)\n--    \u03bb> cardinal2 (listaAmc [1..5000000])\n--    5000000\n--    (7.06 secs, 9,591,013,280 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir la funci\u00f3n\n--    cardDistintos :: MultiConj a -> Int\n-- tal que (cardDistintos m) es el n\u00famero de elementos (sin contar las\n-- repeticiones) del multiconjunto m. Por ejemplo,\n--    cardDistintos (listaAmc \"ababcad\")  ==  4\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\ncardDistintos :: MultiConj a -> Int\ncardDistintos = M.size\n\n-- 2\u00aa definici\u00f3n\ncardDistintos2 :: MultiConj a -> Int\ncardDistintos2 = length . M.keys\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> cardDistintos (listaAmc [1..10000000])\n--    10000000\n--    (9.86 secs, 17,538,021,680 bytes)\n--    \u03bb> cardDistintos2 (listaAmc [1..10000000])\n--    10000000\n--    (10.14 secs, 18,092,597,184 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    pertenece :: Ord a => a -> MultiConj a -> Bool\n-- tal que (pertenece x m) se verifica si el elemento x pertenece al\n-- multiconjunto m. Por ejemplo,\n--    pertenece 'b' (listaAmc \"ababcad\")  ==  True\n--    pertenece 'r' (listaAmc \"ababcad\")  ==  False\n-- ---------------------------------------------------------------------\n\npertenece :: Ord a => a -> MultiConj a -> Bool\npertenece = M.member\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n\n--    noPertenece :: Ord a => a -> MultiConj a -> Bool\n-- tal que (noPertenece x m) se verifica si el elemento x no pertenece al\n-- multiconjunto m. Por ejemplo,\n--    noPertenece 'b' (listaAmc \"ababcad\")  ==  False\n--    noPertenece 'r' (listaAmc \"ababcad\")  ==  True\n-- ---------------------------------------------------------------------\n\nnoPertenece :: Ord a => a -> MultiConj a -> Bool\nnoPertenece  = M.notMember\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la funci\u00f3n\n--    ocurrencias :: Ord a => a -> MultiConj a -> Int\n-- tal que (ocurrencias x m) es el n\u00famero de ocurrencias de x en el\n-- multiconjunto m. Por ejemplo,\n--    ocurrencias 'a' (listaAmc \"ababcad\")  ==  3\n--    ocurrencias 'r' (listaAmc \"ababcad\")  ==  0\n-- ---------------------------------------------------------------------\n\nocurrencias :: Ord a => a -> MultiConj a -> Int\nocurrencias = M.findWithDefault 0\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15: Definir la funci\u00f3n \n--    elementos :: Ord a => MultiConj a -> [a]\n-- tal que (elementos m) es la lista de los elementos (sin repeticiones)\n-- del multiconjunto m. Por ejemplo,\n--    elementos (listaAmc \"ababcad\")  ==  \"abcd\"\n-- ---------------------------------------------------------------------\n\nelementos :: Ord a => MultiConj a -> [a]\nelementos = M.keys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16.Definir la funci\u00f3n\n--    esSubmultiConj :: Ord a => MultiConj a -> MultiConj a -> Bool\n-- tal que (esSubmultiConj m1 m2) se verifica si m1 es un\n-- submulticonjuto de m2 (es decir; los elementos de m1 pertenecen a m2\n-- con un n\u00famro de ocurrencias igual o mayor). Por ejemplo,\n--    ghci> let m1 = listaAmc \"ababcad\"\n--    ghci> let m2 = listaAmc \"bcbaadaa\"\n--    ghci> m1\n--    fromList [('a',3),('b',2),('c',1),('d',1)]\n--    ghci> m2\n--    fromList [('a',4),('b',2),('c',1),('d',1)]\n--    ghci> esSubmultiConj m1 m2\n--    True\n--    ghci> esSubmultiConj m2 m1\n--    False\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\nesSubmultiConj :: Ord a => MultiConj a -> MultiConj a -> Bool\nesSubmultiConj m1 m2 =\n    all (\\x -> ocurrencias x m1 <= ocurrencias x m2)\n        (elementos m1)\n\n-- 2\u00aa definici\u00f3n\nesSubmultiConj2 :: Ord a => MultiConj a -> MultiConj a -> Bool\nesSubmultiConj2 = M.isSubmapOfBy (<=)\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> esSubmultiConj (listaAmc [1..1000000]) (listaAmc [1..1000000])\n--    True\n--    (3.06 secs, 3,440,710,816 bytes)\n--    \u03bb> esSubmultiConj2 (listaAmc [1..1000000]) (listaAmc [1..1000000])\n--    True\n--    (1.71 secs, 3,058,187,728 bytes)\n--\n--    \u03bb> let m = listaAmc (replicate 10000000 1) in esSubmultiConj m m\n--    True\n--    (5.71 secs, 5,539,250,712 bytes)\n--    \u03bb> let m = listaAmc (replicate 10000000 1) in esSubmultiConj2 m m\n--    True\n--    (5.87 secs, 5,468,766,496 bytes)\n\n-- ---------------------------------------------------------------------\n-- Elemento minimo y m\u00e1ximo de un multiconjunto                       --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Definir la funci\u00f3n\n--    minimo :: MultiConj a -> a\n-- tal que (minimo m) es el m\u00ednimo elemento del multiconjunto m. Por\n-- ejemplo, \n--    minimo (listaAmc \"cdacbab\")  ==  'a'\n-- ---------------------------------------------------------------------\n\nminimo :: MultiConj a -> a\nminimo = fst . M.findMin\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 18. Definir la funci\u00f3n\n--    maximo :: MultiConj a -> a\n-- tal que (maximo m) es el m\u00e1ximo elemento del multiconjunto m. Por\n-- ejemplo, \n--    maximo (listaAmc \"cdacbab\")  ==  'd'\n-- ---------------------------------------------------------------------\n\nmaximo :: MultiConj a -> a\nmaximo = fst . M.findMax\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 19. Definir la funci\u00f3n   \n--    borraMin :: Ord a => MultiConj a -> MultiConj a\n-- tal que (borraMin m) es el multiconjunto obtenido eliminando una\n-- ocurrencia del menor elemento de m. Por ejemplo,\n--    ghci> borraMin (listaAmc \"cdacbab\")\n--    fromList [('a',1),('b',2),('c',2),('d',1)]\n--    ghci> borraMin it\n--    fromList [('b',2),('c',2),('d',1)]\n-- ---------------------------------------------------------------------\n\nborraMin :: Ord a => MultiConj a -> MultiConj a\nborraMin m = borra (minimo m) m\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 20. Definir la funci\u00f3n   \n--    borraMax :: Ord a => MultiConj a -> MultiConj a\n-- tal que (borraMax m) es el multiconjunto obtenido eliminando una\n-- ocurrencia del mayor elemento de m. Por ejemplo,\n--    ghci> borraMax (listaAmc \"cdacbab\")\n--    fromList [('a',2),('b',2),('c',2)]\n--    ghci> borraMax it\n--    fromList [('a',2),('b',2),('c',1)]\n-- ---------------------------------------------------------------------\n\nborraMax :: Ord a => MultiConj a -> MultiConj a\nborraMax m = borra (maximo m) m\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 21. Definir la funci\u00f3n   \n--    borraMinTodo :: Ord a => MultiConj a -> MultiConj a\n-- tal que (borraMinTodo m) es el multiconjunto obtenido eliminando\n-- todas las ocurrencias del menor elemento de m. Por ejemplo,\n--    ghci> borraMinTodo (listaAmc \"cdacbab\")\n--    fromList [('b',2),('c',2),('d',1)]\n--    ghci> borraMinTodo it\n--    fromList [('c',2),('d',1)]\n-- ---------------------------------------------------------------------\n\nborraMinTodo :: Ord a => MultiConj a -> MultiConj a\nborraMinTodo = M.deleteMin\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 22. Definir la funci\u00f3n   \n--    borraMaxTodo :: Ord a => MultiConj a -> MultiConj a\n-- tal que (borraMaxTodo m) es el multiconjunto obtenido eliminando\n-- todas las ocurrencias del mayor elemento de m. Por ejemplo,\n--    ghci> borraMaxTodo (listaAmc \"cdacbab\")\n--    fromList [('a',2),('b',2),('c',2)]\n--    ghci> borraMaxTodo it\n--    fromList [('a',2),('b',2)]\n-- ---------------------------------------------------------------------\n\nborraMaxTodo :: Ord a => MultiConj a -> MultiConj a\nborraMaxTodo = M.deleteMax\n\n-- ---------------------------------------------------------------------\n-- Operaciones: uni\u00f3n, intersecci\u00f3n y diferencia de multiconjuntos    --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 23. Definir la funci\u00f3n\n--    union :: Ord a => MultiConj a -> MultiConj a -> MultiConj a\n-- tal que (union m1 m2) es la uni\u00f3n de los multiconjuntos m1 y m2. Por\n-- ejemplo, \n--    ghci> let m1 = listaAmc \"cdacba\"\n--    ghci> let m2 = listaAmc \"acec\"\n--    ghci> m1\n--    fromList [('a',2),('b',1),('c',2),('d',1)]\n--    ghci> m2\n--    fromList [('a',1),('c',2),('e',1)]\n--    ghci> union m1 m2\n--    fromList [('a',3),('b',1),('c',4),('d',1),('e',1)]\n-- ---------------------------------------------------------------------\n\nunion :: Ord a => MultiConj a -> MultiConj a -> MultiConj a\nunion = M.unionWith (+)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 24. Definir la funci\u00f3n\n--    unionG :: Ord a => [MultiConj a] -> MultiConj a\n-- tal que (unionG ms) es la uni\u00f3n de la lista de multiconjuntos ms. Por\n-- ejemplo, \n--    ghci> unionG (map listaAmc [\"aba\", \"cda\", \"bdb\"])\n--    fromList [('a',3),('b',3),('c',1),('d',2)]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\nunionG :: Ord a => [MultiConj a] -> MultiConj a\nunionG = M.unionsWith (+)\n\n-- 2\u00aa definici\u00f3n\nunionG2 :: Ord a => [MultiConj a] -> MultiConj a\nunionG2 = foldr union vacio\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> unionG (replicate 1000000 (listaAmc \"abc\"))\n--    fromList [('a',1000000),('b',1000000),('c',1000000)]\n--    (1.04 secs, 693,213,488 bytes)\n--    \u03bb> unionG2 (replicate 1000000 (listaAmc \"abc\"))\n--    fromList [('a',1000000),('b',1000000),('c',1000000)]\n--    (1.40 secs, 832,739,480 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 25. Definir la funci\u00f3n\n--    diferencia :: Ord a => MultiConj a -> MultiConj a -> MultiConj a\n-- tal que (diferencia m1 m2) es la diferencia de los multiconjuntos m1\n-- y m2. Por ejemplo,\n--    ghci> diferencia (listaAmc \"abacc\") (listaAmc \"dcb\")\n--    fromList [('a',2),('c',1)]\n-- ---------------------------------------------------------------------\n\ndiferencia :: Ord a => MultiConj a -> MultiConj a -> MultiConj a\ndiferencia = M.differenceWith f \n    where f x y | x <= y    = Nothing\n                | otherwise = Just (x - y)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 26. Definir la funci\u00f3n\n--    interseccion :: Ord a => MultiConj a -> MultiConj a -> MultiConj a\n-- tal que (interseccion m1 m2) es la intersecci\u00f3n de los multiconjuntos\n-- m1 y m2. Por ejemplo,\n--    ghci> interseccion (listaAmc \"abcacc\") (listaAmc \"bdcbc\")\n--    fromList [('b',1),('c',2)]\n-- ---------------------------------------------------------------------\n\ninterseccion :: Ord a => MultiConj a -> MultiConj a -> MultiConj a\ninterseccion = M.intersectionWith min \n\n-- ---------------------------------------------------------------------\n-- Filtrado y partici\u00f3n                                               --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 27. Definir la funci\u00f3n\n--    filtra :: Ord a => (a -> Bool) -> MultiConj a -> MultiConj a\n-- tal que (filtra p m) es el multiconjunto de los elementos de m que\n-- verifican la propiedad p. Por ejemplo,\n--    ghci> filtra (>'b') (listaAmc \"abaccaded\") \n--    fromList [('c',2),('d',2),('e',1)]\n-- ---------------------------------------------------------------------\n\nfiltra :: Ord a => (a -> Bool) -> MultiConj a -> MultiConj a\nfiltra p = M.filterWithKey (\\k _ -> p k) \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 28. Definir la funci\u00f3n\n--    particion :: Ord a => \n--                 (a -> Bool) -> MultiConj a -> (MultiConj a,MultiConj a)\n-- tal que (particion p m) es el par cuya primera componente consta de\n-- los elementos de m que cumplen p y la segunda por los que no lo\n-- cumplen. Por ejemplo, \n--    ghci> particion (>'b') (listaAmc \"abaccaded\") \n--    (fromList [('c',2),('d',2),('e',1)],fromList [('a',3),('b',1)])\n-- ---------------------------------------------------------------------\n\nparticion :: Ord a => \n             (a -> Bool) -> MultiConj a -> (MultiConj a,MultiConj a)\nparticion p = M.partitionWithKey (\\k _ -> p k) \n\n-- ---------------------------------------------------------------------\n-- Funci\u00f3n aplicativa                                                 --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 29. Definir la funci\u00f3n\n--    mapMC :: Ord b => (a -> b) -> MultiConj a -> MultiConj b\n-- tal que (mapMC f m) es el multiconjunto obtenido aplicando la funci\u00f3n\n-- f a todos los  elementos de m. Por ejemplo,\n--    ghci> mapMC (:\"N\") (listaAmc \"abaccaded\") \n--    fromList [(\"aN\",3),(\"bN\",1),(\"cN\",2),(\"dN\",2),(\"eN\",1)]\n-- ---------------------------------------------------------------------\n\nmapMC :: Ord b => (a -> b) -> MultiConj a -> MultiConj b\nmapMC = M.mapKeys\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En 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 30 sobre los multiconjuntos mediante diccionarios. Los ejercicios y su soluci\u00f3n 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":[250],"tags":[244,270,310],"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\/5399"}],"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=5399"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5399\/revisions"}],"predecessor-version":[{"id":5400,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5399\/revisions\/5400"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5399"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5399"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5399"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}