{"id":4296,"date":"2014-04-25T18:23:55","date_gmt":"2014-04-25T16:23:55","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4296"},"modified":"2016-01-09T18:17:06","modified_gmt":"2016-01-09T17:17:06","slug":"i1m2013-ejercicios-con-el-tad-de-grafos-en-haskell-2","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-ejercicios-con-el-tad-de-grafos-en-haskell-2\/","title":{"rendered":"I1M2013: Ejercicios con el TAD de grafos en Haskell (2)"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones ejercicios, a partir del 5, sobre grafos de la 28\u00aa relaci\u00f3n.<\/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 de ejercicios es definir operaciones\n-- entre conjuntos, representados mediante listas ordenadas sin\n-- repeticiones, explicado en el tema 17 cuyas transparencias se\n-- encuentran en \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\/temas\/tema-17t.pdf\n-- ---------------------------------------------------------------------\n\n{-# LANGUAGE FlexibleInstances #-}\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Representaci\u00f3n de conjuntos y operaciones b\u00e1sicas                --\n-- ---------------------------------------------------------------------\n\n-- Los conjuntos como listas ordenadas sin repeticiones.\nnewtype Conj a = Cj [a]\n    deriving Eq\n\n-- Procedimiento de escritura de los conjuntos.\ninstance (Show a) => Show (Conj a) where\n    showsPrec _ (Cj s) cad = showConj s cad\n\nshowConj []     cad = showString \"{}\" cad\nshowConj (x:xs) cad = showChar '{' (shows x (showl xs cad))\n     where showl []     cad = showChar '}' cad\n           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))\n\n-- Ejemplo de conjunto:\n--    ghci> c1\n--    {0,1,2,3,5,7,9}\nc1, c2, c3, c4 :: Conj Int\nc1 = foldr inserta vacio [2,5,1,3,7,5,3,2,1,9,0]\nc2 = foldr inserta vacio [2,6,8,6,1,2,1,9,6]\nc3 = Cj [2..100000]\nc4 = Cj [1..100000]\n\n-- vacio es el conjunto vac\u00edo. Por ejemplo,\n--    ghci> vacio\n--    {}\nvacio :: Conj a                         \nvacio = Cj []\n\n-- (esVacio c) se verifica si c es el conjunto vac\u00edo. Por ejemplo, \n--    esVacio c1     ==  False\n--    esVacio vacio  ==  True\nesVacio :: Conj a -> Bool                \nesVacio (Cj xs) = null xs\n\n-- (pertenece x c) se verifica si x pertenece al conjunto c. Por ejemplo, \n--    c1              ==  {0,1,2,3,5,7,9}\n--    pertenece 3 c1  ==  True\n--    pertenece 4 c1  ==  False\npertenece :: Ord a => a -> Conj a -> Bool \npertenece x (Cj s) = x `elem` takeWhile (<= x) s\n\n-- (inserta x c) es el conjunto obtenido a\u00f1adiendo el elemento x al\n-- conjunto c. Por ejemplo,\n--    c1            ==  {0,1,2,3,5,7,9}\n--    inserta 5 c1  ==  {0,1,2,3,5,7,9}\n--    inserta 4 c1  ==  {0,1,2,3,4,5,7,9}\ninserta :: Ord a => a -> Conj a -> Conj a\ninserta x (Cj s) = Cj (agrega x s)\n    where agrega x []                    = [x]                \n          agrega x s@(y:ys) | x > y      = y : agrega x ys\n                            | x < y      = x : s\n                            | otherwise  = s\n\n-- (elimina x c) es el conjunto obtenido eliminando el elemento x\n-- del conjunto c. Por ejemplo,\n--    c1            ==  {0,1,2,3,5,7,9}\n--    elimina 3 c1  ==  {0,1,2,5,7,9}\nelimina :: Ord a => a -> Conj a -> Conj a\nelimina x (Cj s) = Cj (elimina x s)\n    where elimina x []                   = []\n          elimina x s@(y:ys) | x > y     = y : elimina x ys\n                             | x < y     = s\n                             | otherwise = ys\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Ejercicios                                                       --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    subconjunto :: Ord a => Conj a -> Conj a -> Bool\n-- tal que (subconjunto c1 c2) se verifica si todos los elementos de c1 \n-- pertenecen a c2. Por ejemplo,         \n--    subconjunto (Cj [2..100000]) (Cj [1..100000]) == True\n--    subconjunto (Cj [1..100000]) (Cj [2..100000]) == False\n-- ---------------------------------------------------------------------\n\n-- Se presentan distintas definiciones y se compara su eficiencia.\n\n-- 1\u00aa definici\u00f3n\nsubconjunto1 :: Ord a => Conj a -> Conj a -> Bool\nsubconjunto1 (Cj xs) (Cj ys) = sublista xs ys\n    where sublista [] _      = True\n          sublista (x:xs) ys = elem x ys && sublista xs ys\n\n-- 2\u00aa definici\u00f3n\nsubconjunto2 :: Ord a => Conj a -> Conj a -> Bool\nsubconjunto2 (Cj xs) c =\n    and [pertenece x c | x <-xs]\n\n-- 3\u00aa definici\u00f3n\nsubconjunto3 :: Ord a => Conj a -> Conj a -> Bool\nsubconjunto3 (Cj xs) (Cj ys) = sublista xs ys\n    where sublista [] _      = True\n          sublista _ []      = False\n          sublista (x:xs) ys@(y:zs) = x >= y && elem x ys &&\n                                       sublista xs zs\n\n-- 4\u00aa definici\u00f3n\nsubconjunto4 :: Ord a => Conj a -> Conj a -> Bool\nsubconjunto4 (Cj xs) (Cj ys) = sublista xs ys\n    where sublista [] _      = True\n          sublista _ []      = False\n          sublista (x:xs) ys@(y:zs) \n              | x < y  = False\n              | x == y = sublista xs zs\n              | x > y  = elem x zs && sublista xs zs\n\n-- Comparaci\u00f3n de la eficiencia:\n--    ghci> subconjunto1 (Cj [2..100000]) (Cj [1..1000000])\n--      C-c C-cInterrupted.\n--    ghci> subconjunto2 (Cj [2..100000]) (Cj [1..1000000])\n--      C-c C-cInterrupted.\n--    ghci> subconjunto3 (Cj [2..100000]) (Cj [1..1000000])\n--    True\n--    (0.52 secs, 26097076 bytes)\n--    ghci> subconjunto4 (Cj [2..100000]) (Cj [1..1000000])\n--    True\n--    (0.66 secs, 32236700 bytes)\n--    ghci> subconjunto1 (Cj [2..100000]) (Cj [1..10000])\n--    False\n--    (0.54 secs, 3679024 bytes)\n--    ghci> subconjunto2 (Cj [2..100000]) (Cj [1..10000])\n--    False\n--    (38.19 secs, 1415562032 bytes)\n--    ghci> subconjunto3 (Cj [2..100000]) (Cj [1..10000])\n--    False\n--    (0.08 secs, 3201112 bytes)\n--    ghci> subconjunto4 (Cj [2..100000]) (Cj [1..10000])\n--    False\n--    (0.09 secs, 3708988 bytes)\n\n-- En lo que sigue, se usar\u00e1 la 3\u00aa definici\u00f3n:\nsubconjunto :: Ord a => Conj a -> Conj a -> Bool\nsubconjunto = subconjunto3\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 (Cj [2..5]) (Cj [1..7]) == True\n--   subconjuntoPropio (Cj [2..5]) (Cj [1..4]) == False\n--   subconjuntoPropio (Cj [2..5]) (Cj [2..5]) == False\n-- ---------------------------------------------------------------------\n\nsubconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool\nsubconjuntoPropio c1 c2 = \n    subconjunto c1 c2 && c1 \/= c2\n  \n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    unitario :: Ord a => a -> Conj a \n-- tal que (unitario x) es el conjunto {x}. Por ejemplo,\n--   unitario 5 == {5}\n-- ---------------------------------------------------------------------\n\nunitario :: Ord a => a -> Conj a \nunitario x = inserta x vacio\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    cardinal :: Conj a -> Int\n-- tal que (cardinal c) es el n\u00famero de elementos del conjunto c. Por\n-- ejemplo,\n--    cardinal c1 == 7\n--    cardinal c2 == 5\n-- ---------------------------------------------------------------------\n\ncardinal :: Conj a -> Int\ncardinal (Cj xs) = length xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    union :: Ord a => Conj a -> Conj a -> Conj a\n-- tal (union c1 c2) es la uni\u00f3n de ambos conjuntos. Por ejemplo,\n--    union c1 c2             == {0,1,2,3,5,6,7,8,9}\n--    cardinal (union2 c3 c4) == 100000\n-- ---------------------------------------------------------------------\n\n-- Se considera distintas definiciones y se compara la eficiencia.\n\n-- 1\u00aa definici\u00f3n:\nunion1 :: Ord a => Conj a -> Conj a -> Conj a\nunion1 (Cj xs) (Cj ys) = foldr inserta (Cj ys) xs\n\n-- Otra defini\u00f3n es\nunion2 :: Ord a => Conj a -> Conj a -> Conj a\nunion2 (Cj xs) (Cj ys) = Cj (unionL xs ys)\n    where unionL [] ys = ys \n          unionL xs [] = xs \n          unionL l1@(x:xs) l2@(y:ys)\n              | x < y  = x : unionL xs l2\n              | x == y = x : unionL xs ys\n              | x > y  = y : unionL l1 ys \n\n-- Comparaci\u00f3n de eficiencia\n--    ghci> :set +s\n--    ghci> let c = Cj [1..1000]\n--    ghci> cardinal (union1 c c)\n--    1000\n--    (1.04 secs, 56914332 bytes)\n--    ghci> cardinal (union2 c c)\n--    1000\n--    (0.01 secs, 549596 bytes)\n\n-- En lo que sigue se usar\u00e1 la 2\u00aa definici\u00f3n\nunion :: Ord a => Conj a -> Conj a -> Conj a\nunion = union2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    unionG:: Ord a => [Conj a] -> Conj a\n-- tal (unionG cs) calcule la uni\u00f3n de la lista de conjuntos cd. Por\n-- ejemplo,\n--    unionG [c1, c2] == {0,1,2,3,5,6,7,8,9}\n-- ---------------------------------------------------------------------\n\nunionG:: Ord a => [Conj a] -> Conj a\nunionG []          = vacio\nunionG (Cj xs:css) = Cj xs `union` unionG css\n\n-- Se puede definir por plegados\nunionG2 :: Ord a => [Conj a] -> Conj a\nunionG2 = foldr union vacio\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    interseccion :: Eq a => Conj a -> Conj a -> Conj a\n-- tal que (interseccion c1 c2) es la intersecci\u00f3n de los conjuntos c1 y\n-- c2. Por ejemplo,\n--    interseccion (Cj [1..7]) (Cj [4..9])    == {4,5,6,7}\n--    interseccion (Cj [2..1000000]) (Cj [1]) == {}\n-- ---------------------------------------------------------------------\n\n-- Se da distintas definiciones y se compara su eficiencia.\n\n-- 1\u00aa definici\u00f3n\ninterseccion1 :: Eq a => Conj a -> Conj a -> Conj a\ninterseccion1 (Cj xs) (Cj ys) = Cj [x | x <- xs, x `elem` ys]\n\n-- 2\u00aa definici\u00f3n\ninterseccion2 :: Ord a => Conj a -> Conj a -> Conj a\ninterseccion2 (Cj xs) (Cj ys) = Cj (interseccionL xs ys)\n    where interseccionL l1@(x:xs) l2@(y:ys)\n              | x > y   = interseccionL l1 ys\n              | x == y  = x : interseccionL xs ys\n              | x < y   = interseccionL xs l2\n          interseccionL _ _ = []\n\n-- La comparaci\u00f3n de eficiencia es\n-- ghci> interseccion1 (Cj [2..1000000]) (Cj [1])\n-- {}\n-- (0.32 secs, 80396188 bytes)\n-- ghci> interseccion2 (Cj [2..1000000]) (Cj [1])\n-- {}\n-- (0.00 secs, 2108848 bytes)\n\n-- En lo que sigue se usa la 2\u00aa definici\u00f3n:\ninterseccion :: Ord a => Conj a -> Conj a -> Conj a\ninterseccion = interseccion2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    interseccionG:: Ord a => [Conj a] -> Conj a\n-- tal que (interseccionG cs) es la intersecci\u00f3n de la lista de\n-- conjuntos cs. Por ejemplo,\n--    interseccionG [c1, c2] == {1,2,9}\n-- ---------------------------------------------------------------------\n\ninterseccionG:: Ord a => [Conj a] -> Conj a\ninterseccionG [c] = c\ninterseccionG (cs:css) = interseccion cs (interseccionG css)\n\n-- Se puede definir por plegado\ninterseccionG2 :: Ord a => [Conj a] -> Conj a\ninterseccionG2 = foldr1 interseccion\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    disjuntos :: Ord a => Conj a -> Conj a -> Bool\n-- tal que (disjuntos c1 c2) se verifica si los conjuntos c1 y c2 son\n-- disjuntos. Por ejemplo,\n--   disjuntos (Cj [2..5]) (Cj [6..9]) == True\n--   disjuntos (Cj [2..5]) (Cj [1..9]) == False\n-- ---------------------------------------------------------------------\n\ndisjuntos :: Ord a => Conj a -> Conj a -> Bool\ndisjuntos c1 c2 = esVacio (interseccion c1 c2)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    diferencia :: Eq a => Conj a -> Conj a -> Conj 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--    diferencia c1 c2 == {0,3,5,7}\n--    diferencia c2 c1 == {6,8}\n-- ---------------------------------------------------------------------\n\ndiferencia :: Eq a => Conj a -> Conj a -> Conj a\ndiferencia (Cj xs) (Cj ys) = Cj zs\n    where zs = [x | x <- xs, x `notElem` ys]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir la funci\u00f3n\n--    diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a\n-- tal que (diferenciaSimetrica c1 c2) es la diferencia sim\u00e9trica de los\n-- conjuntos c1 y c2. Por ejemplo,\n--   diferenciaSimetrica c1 c2 == {0,3,5,6,7,8}\n--   diferenciaSimetrica c2 c1 == {0,3,5,6,7,8}\n-- ---------------------------------------------------------------------\n\ndiferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a\ndiferenciaSimetrica c1 c2 = \n    diferencia (union c1 c2) (interseccion c1 c2)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    filtra :: (a -> Bool) -> Conj a -> Conj a\n-- tal (filtra p c) es el conjunto de elementos de c que verifican el\n-- predicado p. Por ejemplo,\n--    filtra even c1 == {0,2}\n--    filtra odd  c1  == {1,3,5,7,9}\n-- ---------------------------------------------------------------------\n\nfiltra :: (a -> Bool) -> Conj a -> Conj a\nfiltra p (Cj xs) = Cj (filter p xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n\n--    particion :: (a -> Bool) -> Conj a -> (Conj a, Conj 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\n-- verifica. Por ejemplo,\n--    particion even c1 == ({0,2},{1,3,5,7,9})\n-- ---------------------------------------------------------------------\n\nparticion :: (a -> Bool) -> Conj a -> (Conj a, Conj a)\nparticion p c = (filtra p c, filtra (not . p) c)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la funci\u00f3n\n--    divide :: (Ord a) => a-> Conj a -> (Conj a, Conj a)\n-- tal que (divide x c) es el par formado por dos subconjuntos de c: el\n-- de los elementos menores o iguales que x y el de los mayores que x.\n-- Por ejemplo,\n--    divide 5 c1 == ({0,1,2,3,5},{7,9})  \n-- ---------------------------------------------------------------------\n\ndivide :: Ord a => a-> Conj a -> (Conj a, Conj a)\ndivide x = particion (<= x)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Definir la funci\u00f3n\n--    mapC :: (a -> b) -> Conj a -> Conj b\n-- tal que (map f c) es el conjunto formado por las im\u00e1genes de los\n-- elemsntos de c, mediante f. Por ejemplo,\n--   mapC (*2) (Cj [1..4]) == {2,4,6,8}\n-- ---------------------------------------------------------------------\n\nmapC :: (a -> b) -> Conj a -> Conj b\nmapC f (Cj xs) = Cj (map f xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. Definir la funci\u00f3n\n--    everyC :: (a -> Bool) -> Conj a -> Bool\n-- tal que (everyC p c) se verifica si todos los elemsntos de c\n-- verifican el predicado p.  Por ejmplo,\n--   everyC even (Cj [2,4..10]) == True\n--   everyC even (Cj [2..10])   == False\n-- ---------------------------------------------------------------------\n\neveryC :: (a -> Bool) -> Conj a -> Bool\neveryC p (Cj xs) = all p xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Definir la funci\u00f3n\n--    someC :: (a -> Bool) -> Conj 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 (Cj [1,4,7]) == True\n--   someC even (Cj [1,3,7]) == False\n-- ---------------------------------------------------------------------\n\nsomeC :: (a -> Bool) -> Conj a -> Bool\nsomeC p (Cj xs) = any p xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 18. Definir la funci\u00f3n\n--    productoC :: (Ord a, Ord b) => Conj a -> Conj b -> Conj (a,b)\n-- tal que (productoC c1 c2) es el producto cartesiano de los \n-- conjuntos c1 y c2. Por ejemplo,\n--   productoC (Cj [1,3]) (Cj [2,4])== {(1,2),(1,4),(3,2),(3,4)}\n-- ---------------------------------------------------------------------\n\nproductoC :: (Ord a, Ord b) => Conj a -> Conj b -> Conj (a,b)\nproductoC (Cj xs) (Cj ys) = \n    foldr inserta vacio [(x,y) | x <- xs, y <- ys]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio. Especificar que, dado un tipo ordenado a, el orden entre\n-- los conjuntos con elementos en a es el orden inducido por el orden\n-- existente entre las listas con elementos en a. \n-- ---------------------------------------------------------------------\n\ninstance Ord a => Ord (Conj a) where\n    (Cj xs) <= (Cj ys) = xs <= ys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 19. Definir la funci\u00f3n\n--    potencia :: Ord a => Conj a -> Conj (Conj 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--    potencia (Cj [1,2])  == {{},{1},{1,2},{2}}\n--    potencia (Cj [1..3]) == {{},{1},{1,2},{1,2,3},{1,3},{2},{2,3},{3}}\n-- ---------------------------------------------------------------------\n\npotencia :: Ord a => Conj a -> Conj (Conj a)\npotencia (Cj []) = unitario vacio\npotencia (Cj (x:xs)) = mapC (inserta x) pr `union` pr\n    where pr = potencia (Cj xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 20. Comprobar con QuickCheck que la relaci\u00f3n de subconjunto\n-- es un orden parcial. Es decir, es una relaci\u00f3n reflexiva,\n-- antisim\u00e9trica y transitiva.\n-- ---------------------------------------------------------------------\n\npropSubconjuntoReflexiva:: Conj Int -> Bool\npropSubconjuntoReflexiva c = subconjunto c c\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propSubconjuntoReflexiva\n--    +++ OK, passed 100 tests.\n\npropSubconjuntoAntisimetrica:: Conj Int -> Conj Int -> Property\npropSubconjuntoAntisimetrica c1 c2 =\n    subconjunto c1 c2 && subconjunto c2 c1 ==> c1 == c2\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propSubconjuntoAntisimetrica\n--    *** Gave up! Passed only 13 tests.\n\npropSubconjuntoTransitiva :: Conj Int -> Conj Int -> Conj Int -> Property\npropSubconjuntoTransitiva c1 c2 c3 =\n    subconjunto c1 c2 && subconjunto c2 c3 ==> subconjunto c1 c3\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propSubconjuntoTransitiva\n--    *** Gave up! Passed only 7 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 21. Comprobar con QuickCheck que el conjunto vac\u00edo est\u00e1\n-- contenido en cualquier conjunto.\n-- ---------------------------------------------------------------------\n\npropSubconjuntoVacio:: Conj Int -> Bool\npropSubconjuntoVacio c = subconjunto vacio c\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propSubconjuntoVacio\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 22. Comprobar con QuickCheck las siguientes propiedades de\n-- la uni\u00f3n de conjuntos:\n--    Idempotente:      A U A = A\n--    Neutro:           A U {} = A\n--    Commutativa:      A U B = B U A\n--    Asociativa:       A U (B U C) = (A U B) U C\n--    UnionSubconjunto: A y B son subconjuntos de (A U B)\n--    UnionDiferencia:  A U B = A U (B \\ A)\n-- ---------------------------------------------------------------------\n\npropUnionIdempotente :: Conj Int -> Bool\npropUnionIdempotente c = \n    union c c == c\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propUnionIdempotente\n--    +++ OK, passed 100 tests.\n\npropVacioNeutroUnion:: Conj Int -> Bool\npropVacioNeutroUnion c = \n    union c vacio == c\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propVacioNeutroUnion\n--    +++ OK, passed 100 tests.\n\npropUnionCommutativa:: Conj Int -> Conj Int -> Bool\npropUnionCommutativa c1 c2 =\n    union c1 c2 == union c2 c1\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propUnionCommutativa\n--    +++ OK, passed 100 tests.\n\npropUnionAsociativa:: Conj Int -> Conj Int -> Conj Int -> Bool\npropUnionAsociativa c1 c2 c3 =\n    union c1 (union c2 c3) == union (union c1 c2) c3\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propUnionAsociativa\n--    +++ OK, passed 100 tests.\n\npropUnionSubconjunto :: Conj Int -> Conj Int -> Bool\npropUnionSubconjunto c1 c2 =\n    subconjunto c1 c3 && subconjunto c2 c3\n    where c3 = union c1 c2\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propUnionSubconjunto\n--    +++ OK, passed 100 tests.\n\npropUnionDiferencia :: Conj Int -> Conj Int -> Bool\npropUnionDiferencia c1 c2 =\n    union c1 c2 == union c1 (diferencia c2 c1)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propUnionDiferencia\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 23. Comprobar con QuickCheck las siguientes propiedades de\n-- la intersecci\u00f3n de conjuntos:\n--    Idempotente:             A n A = A\n--    VacioInterseccion:       A n {} = {}\n--    Commutativa:             A n B = B n A\n--    Asociativa:              A n (B n C) = (A n B) n C\n--    InterseccionSubconjunto: (A n B) es subconjunto de A y B\n--    DistributivaIU:          A n (B U C) = (A n B) U (A n C)\n--    DistributivaUI:          A U (B n C) = (A U B) n (A U C)\n-- ---------------------------------------------------------------------\n\n\npropInterseccionIdempotente :: Conj Int -> Bool\npropInterseccionIdempotente c = \n    interseccion c c == c\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propInterseccionIdempotente\n--    +++ OK, passed 100 tests.\n\npropVacioInterseccion:: Conj Int -> Bool\npropVacioInterseccion c = \n    interseccion c vacio == vacio\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propVacioInterseccion\n--    +++ OK, passed 100 tests.\n\npropInterseccionCommutativa:: Conj Int -> Conj Int -> Bool\npropInterseccionCommutativa c1 c2 =\n    interseccion c1 c2 == interseccion c2 c1\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propInterseccionCommutativa\n--    +++ OK, passed 100 tests.\n\npropInterseccionAsociativa:: Conj Int -> Conj Int -> Conj Int -> Bool\npropInterseccionAsociativa c1 c2 c3 =\n    interseccion c1 (interseccion c2 c3) == interseccion (interseccion c1 c2) c3\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propInterseccionAsociativa\n--    +++ OK, passed 100 tests.\n\npropInterseccionSubconjunto :: Conj Int -> Conj Int -> Bool\npropInterseccionSubconjunto c1 c2 =\n    subconjunto c3 c1 && subconjunto c3 c2\n        where c3 = interseccion c1 c2\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propInterseccionSubconjunto\n--    +++ OK, passed 100 tests.\n\npropDistributivaIU:: Conj Int -> Conj Int -> Conj Int -> Bool\npropDistributivaIU c1 c2 c3 =\n    interseccion c1 (union c2 c3) == union (interseccion c1 c2)\n                                           (interseccion c1 c3)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propDistributivaIU\n--    +++ OK, passed 100 tests.\n\npropDistributivaUI:: Conj Int -> Conj Int -> Conj Int -> Bool\npropDistributivaUI c1 c2 c3 =\n    union c1 (interseccion c2 c3) == interseccion (union c1 c2)\n                                                  (union c1 c3)\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propDistributivaUI\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 24. Comprobar con QuickCheck las siguientes propiedades de\n-- la diferencia de conjuntos:\n--    DiferenciaVacio1: A \\ {} = A\n--    DiferenciaVacio2: {} \\ A = {}\n--    DiferenciaDif1:   (A \\ B) \\ C = A \\ (B U C)\n--    DiferenciaDif2:   A \\ (B \\ C) = (A \\ B) U (A n C)\n--    DiferenciaSubc:   (A \\ B) es subconjunto de A\n--    DiferenciaDisj:   A y (B \\ A) son disjuntos\n--    DiferenciaUI:     (A U B) \\ A = B \\ (A n B)\n-- ---------------------------------------------------------------------\n\npropDiferenciaVacio1 :: Conj Int -> Bool\npropDiferenciaVacio1 c = diferencia c vacio == c\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propDiferenciaVacio2\n--    +++ OK, passed 100 tests.\n\npropDiferenciaVacio2 :: Conj Int -> Bool\npropDiferenciaVacio2 c = diferencia vacio c == vacio\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propDiferenciaVacio2\n--    +++ OK, passed 100 tests.\n\npropDiferenciaDif1 :: Conj Int -> Conj Int -> Conj Int -> Bool\npropDiferenciaDif1 c1 c2 c3 =\n  diferencia (diferencia c1 c2) c3 == diferencia c1 (union c2 c3)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propDiferenciaDif1\n--    +++ OK, passed 100 tests.\n\npropDiferenciaDif2 :: Conj Int -> Conj Int -> Conj Int -> Bool\npropDiferenciaDif2 c1 c2 c3 =\n  diferencia c1 (diferencia c2 c3) == union (diferencia c1 c2) \n                                            (interseccion c1 c3) \n  \n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propDiferenciaDif2\n--    +++ OK, passed 100 tests.  \n\npropDiferenciaSubc:: Conj Int -> Conj Int -> Bool\npropDiferenciaSubc c1 c2 =\n  subconjunto (diferencia c1 c2) c1\n  \n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propDiferenciaSubc\n--    +++ OK, passed 100 tests.  \n\npropDiferenciaDisj:: Conj Int -> Conj Int -> Bool\npropDiferenciaDisj c1 c2 =  \n  disjuntos c1 (diferencia c2 c1)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propDiferenciaDisj\n--    +++ OK, passed 100 tests.\n\npropDiferenciaUI:: Conj Int -> Conj Int -> Bool\npropDiferenciaUI c1 c2 =  \n  diferencia (union c1 c2) c1 == diferencia c2 (interseccion c1 c2)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck propDiferenciaUI\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Generador de conjuntos                                          --\n-- ---------------------------------------------------------------------\n\n-- genConjunto es un generador de conjuntos. Por ejemplo,\n--    ghci> sample genConjunto\n--    {}\n--    {}\n--    {}\n--    {3,-2,-2,-3,-2,4}\n--    {-8,0,4,6,-5,-2}\n--    {12,-2,-1,-10,-2,2,15,15}\n--    {2}\n--    {}\n--    {-42,55,55,-11,23,23,-11,27,-17,-48,16,-15,-7,5,41,43}\n--    {-124,-66,-5,-47,58,-88,-32,-125}\n--    {49,-38,-231,-117,-32,-3,45,227,-41,54,169,-160,19}\ngenConjunto :: Gen (Conj Int)\ngenConjunto = do xs <- listOf arbitrary\n                 return (foldr inserta vacio xs)\n\n-- Los conjuntos son concreciones de los arbitrarios.\ninstance Arbitrary (Conj Int) where\n    arbitrary = genConjunto\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 ejercicios, a partir del 5, sobre grafos de la 28\u00aa relaci\u00f3n. Los ejercicios y sus soluciones 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":[222],"tags":[270,300,126],"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\/4296"}],"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=4296"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4296\/revisions"}],"predecessor-version":[{"id":5268,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4296\/revisions\/5268"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4296"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4296"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4296"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}