{"id":6599,"date":"2019-03-29T16:37:03","date_gmt":"2019-03-29T15:37:03","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6599"},"modified":"2019-03-30T16:38:41","modified_gmt":"2019-03-30T15:38:41","slug":"i1m2018-ejercicios-con-el-tipo-de-dato-de-los-conjuntos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-ejercicios-con-el-tipo-de-dato-de-los-conjuntos-en-haskell\/","title":{"rendered":"I1M2018: Ejercicios con el tipo de dato de los conjuntos en Haskell"},"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 29 sobre el tipo de datos de las conjuntos.<\/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-14\/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) = showConj s \n\nshowConj :: Show a => [a] -> String -> String\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-- 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-- 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-- 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-- elementos 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 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 29 sobre el tipo de datos de las conjuntos. 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\/6599"}],"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=6599"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6599\/revisions"}],"predecessor-version":[{"id":6601,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6599\/revisions\/6601"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6599"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6599"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6599"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}