{"id":6048,"date":"2018-04-13T08:17:52","date_gmt":"2018-04-13T06:17:52","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6048"},"modified":"2018-04-14T08:09:21","modified_gmt":"2018-04-14T06:09:21","slug":"i1m2017-relaciones-binarias-homogeneas-con-la-libreria-de-conjuntos-de-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2017-relaciones-binarias-homogeneas-con-la-libreria-de-conjuntos-de-haskell\/","title":{"rendered":"I1M2017: Relaciones binarias homog\u00e9neas con la librer\u00eda de conjuntos de Haskell"},"content":{"rendered":"<p>En la primera part de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-17\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 32 sobre relaciones binarias homog\u00e9neas usando la librer\u00eda <a href=\"http:\/\/bit.ly\/17OqgVU\">Data.Set<\/a> de Haskell.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- \u00a7 Pragmas                                                          --\n-- ---------------------------------------------------------------------\n\n{-# LANGUAGE TypeSynonymInstances, \n             FlexibleInstances #-}\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\nimport Data.Set\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Una relaci\u00f3n binaria R sobre un conjunto A puede\n-- representar mediante un par (xs,ps) donde xs es el conjunto de los\n-- elementos de A (el universo de R) y ps es el conjunto de pares de R\n-- (el grafo de R). Definir el tipo de dato (Rel a) para representar las\n-- relaciones binarias sobre a.  \n-- ---------------------------------------------------------------------\n\ntype Rel a = (Set a, Set (a,a))\n\n-- ---------------------------------------------------------------------\n-- Nota. En los ejemplos usaremos las siguientes relaciones binarias: \n--    r1, r2, r3 :: Rel Int\n--    r1 = (fromList [1..9],fromList [(1,3), (2,6), (8,9), (2,7)])\n--    r2 = (fromList [1..9],fromList [(1,3), (2,6), (8,9), (3,7)])\n--    r3 = (fromList [1..9],fromList [(1,3), (2,6), (8,9), (3,6)])\n-- ---------------------------------------------------------------------\n\nr1, r2, r3 :: Rel Int\nr1 = (fromList [1..9],fromList [(1,3), (2,6), (8,9), (2,7)])\nr2 = (fromList [1..9],fromList [(1,3), (2,6), (8,9), (3,7)])\nr3 = (fromList [1..9],fromList [(1,3), (2,6), (8,9), (3,6)])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    universo :: Ord a => Rel a -> Set a\n-- tal que (universo r) es el universo de la relaci\u00f3n r. Por ejemplo, \n--    universo r1  ==  fromList [1,2,3,4,5,6,7,8,9]\n-- ---------------------------------------------------------------------\n\nuniverso :: Ord a => Rel a -> Set a\nuniverso (u,_) = u\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    grafo :: Ord a => Rel a -> [(a,a)]\n-- tal que (grafo r) es el grafo de la relaci\u00f3n r. Por ejemplo, \n--    grafo r1  ==  fromList [(1,3),(2,6),(2,7),(8,9)]\n-- ---------------------------------------------------------------------\n\ngrafo :: Ord a => Rel a -> Set (a,a)\ngrafo (_,g) = g\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    reflexiva :: Ord a => Rel a -> Bool\n-- tal que (reflexiva r) se verifica si la relaci\u00f3n r es reflexiva. Por\n-- ejemplo, \n--    ghci> reflexiva (fromList [1,3], fromList [(1,1),(1,3),(3,3)])\n--    True\n--    ghci> reflexiva (fromList [1,2,3], fromList [(1,1),(1,3),(3,3)])\n--    False\n-- ---------------------------------------------------------------------\n\nreflexiva :: Ord a => Rel a -> Bool\nreflexiva (u,g) = and [(x,x) `member` g | x <- elems u]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    simetrica :: Ord a => Rel a -> Bool\n-- tal que (simetrica r) se verifica si la relaci\u00f3n r es sim\u00e9trica. Por\n-- ejemplo, \n--    ghci> simetrica (fromList [1,3], fromList [(1,1),(1,3),(3,1)])\n--    True\n--    ghci> simetrica (fromList [1,3], fromList [(1,1),(1,3),(3,2)])\n--    False\n--    ghci> simetrica (fromList [1,3], fromList [])\n--    True\n-- ---------------------------------------------------------------------\n\nsimetrica :: Ord a => Rel a -> Bool\nsimetrica (u,g) = and [(y,x) `member` g | (x,y) <- elems g] \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    subconjunto :: Ord a => Set a -> Set a -> Bool\n-- tal que (subconjunto c1 c2) se verifica si c1 es un subconjunto de\n-- c2. Por ejemplo,\n--    subconjunto (fromList [1,3]) (fromList [3,1,5])  ==  True\n--    subconjunto (fromList [3,1,5]) (fromList [1,3])  ==  False\n-- ---------------------------------------------------------------------\n\nsubconjunto :: Ord a => Set a -> Set a -> Bool\nsubconjunto = isSubsetOf\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    composicion :: Ord a => Rel a -> Rel a -> Rel a\n-- tal que (composicion r s) es la composici\u00f3n de las relaciones r y\n-- s. Por ejemplo, \n--    ghci> let r1 = (fromList [1,2], fromList [(1,2),(2,2)])\n--    ghci> let r2 = (fromList [1,2], fromList [(2,1)])\n--    ghci> let r3 = (fromList [1,2], fromList [(1,1)])\n--    ghci> composicion r1 r2\n--    (fromList [1,2],fromList [(1,1),(2,1)])\n--    ghci> composicion r1 r3\n--    (fromList [1,2,3,4,5,6,7,8,9],fromList [])\n-- ---------------------------------------------------------------------\n\ncomposicion :: Ord a => Rel a -> Rel a -> Rel a\ncomposicion (u,g1) (_,g2) = \n    (u,fromList [(x,z) | (x,y1) <- elems g1, \n                         (y2,z) <- elems g2, \n                         y1 == y2])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    transitiva :: Ord a => Rel a -> Bool\n-- tal que (transitiva r) se verifica si la relaci\u00f3n r es transitiva. \n-- Por ejemplo,\n--    ghci> transitiva (fromList [1,3,5],fromList [(1,1),(1,3),(3,1),(3,3),(5,5)])\n--    True\n--    ghci> transitiva (fromList [1,3,5],fromList [(1,1),(1,3),(3,1),(5,5)])\n--    False\n-- ---------------------------------------------------------------------\n\ntransitiva :: Ord a => Rel a -> Bool\ntransitiva r@(u,g) = \n    isSubsetOf (grafo (composicion r r)) g\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    esEquivalencia :: Ord a => Rel a -> Bool\n-- tal que (esEquivalencia r) se verifica si la relaci\u00f3n r es de\n-- equivalencia. Por ejemplo,\n--    ghci> esEquivalencia (fromList [1,3,5],\n--                          fromList [(1,1),(1,3),(3,1),(3,3),(5,5)])\n--    True\n--    ghci> esEquivalencia (fromList [1,2,3,5],\n--                          fromList [(1,1),(1,3),(3,1),(3,3),(5,5)])\n--    False\n--    ghci> esEquivalencia (fromList [1,3,5],\n--                          fromList [(1,1),(1,3),(3,3),(5,5)])\n--    False\n-- ---------------------------------------------------------------------\n\nesEquivalencia :: Ord a => Rel a -> Bool\nesEquivalencia r = reflexiva r && simetrica r && transitiva r\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    irreflexiva :: Ord a => Rel a -> Bool\n-- tal que (irreflexiva r) se verifica si la relaci\u00f3n r es irreflexiva;\n-- es decir, si ning\u00fan elemento de su universo est\u00e1 relacionado con \n-- \u00e9l mismo. Por ejemplo,\n--    ghci> irreflexiva (fromList [1,2,3],fromList [(1,2),(2,1),(2,3)])\n--    True\n--    ghci> irreflexiva (fromList [1,2,3],fromList [(1,2),(2,1),(3,3)])\n--    False\n-- ---------------------------------------------------------------------\n\nirreflexiva :: Ord a => Rel a -> Bool\nirreflexiva (u,g) = and [(x,x) `notMember` g | x <- elems u]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir la funci\u00f3n\n--    antisimetrica :: Ord a => Rel a -> Bool\n-- tal que (antisimetrica r) se verifica si la relaci\u00f3n r es\n-- antisim\u00e9trica; es decir, si (x,y) e (y,x) est\u00e1n relacionado, entonces\n-- x=y. Por ejemplo,\n--    antisimetrica (fromList [1,2],fromList [(1,2)])        ==  True\n--    antisimetrica (fromList [1,2],fromList [(1,2),(2,1)])  ==  False\n--    antisimetrica (fromList [1,2],fromList [(1,1),(2,1)])  ==  True\n-- ---------------------------------------------------------------------\n\nantisimetrica :: Ord a => Rel a -> Bool\nantisimetrica (_,g) =\n    [(x,y) | (x,y) <- elems g, x \/= y, (y,x) `member` g] == []\n\n-- Otra definici\u00f3n es\nantisimetrica2 :: Ord a => Rel a -> Bool\nantisimetrica2 (u,g) = \n    and [((x,y) `member` g && (y,x) `member` g) --> (x == y) \n         | x <- elems u, y <- elems u]\n    where p --> q = not p || q\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    total :: Ord a => Rel a -> Bool\n-- tal que (total r) se verifica si la relaci\u00f3n r es total; es decir, si\n-- para cualquier par x, y de elementos del universo de r, se tiene que\n-- x est\u00e1 relacionado con y \u00f3 y et\u00e1 relacionado con x. Por ejemplo,\n--    total (fromList [1,3],fromList [(1,1),(3,1),(3,3)])  ==  True\n--    total (fromList [1,3],fromList [(1,1),(3,1)])        ==  False\n--    total (fromList [1,3],fromList [(1,1),(3,3)])        ==  False\n-- ---------------------------------------------------------------------\n\ntotal :: Ord a => Rel a -> Bool\ntotal (u,g) = \n    and [(x,y) `member` g || (y,x) `member` g | x <- xs, y <- xs]\n    where xs = elems u\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Comprobar con QuickCheck que las relaciones totales son\n-- reflexivas. \n-- ---------------------------------------------------------------------\n\nprop_total_reflexiva :: Rel Int -> Property\nprop_total_reflexiva r =\n    total r ==> reflexiva r\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_total_reflexiva\n--    *** *** Gave up! Passed only 77 tests.\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Clausuras                                                        --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la funci\u00f3n\n--    clausuraReflexiva :: Ord a => Rel a -> Rel a  \n-- tal que (clausuraReflexiva r) es la clausura reflexiva de r; es\n-- decir, la menor relaci\u00f3n reflexiva que contiene a r. Por ejemplo,\n--    ghci> clausuraReflexiva (fromList [1,3], fromList [(1,1),(3,1)])\n--    (fromList [1,3],fromList [(1,1),(3,1),(3,3)])\n-- ---------------------------------------------------------------------\n\nclausuraReflexiva :: Ord a => Rel a -> Rel a  \nclausuraReflexiva (u,g) =\n    (u, g `union` fromList [(x,x) | x <- elems u])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Comprobar con QuickCheck que clausuraReflexiva es\n-- reflexiva. \n-- ---------------------------------------------------------------------\n\nprop_ClausuraReflexiva :: Rel Int -> Bool\nprop_ClausuraReflexiva r = \n    reflexiva (clausuraReflexiva r)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_ClausuraReflexiva\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. Definir la funci\u00f3n\n--    clausuraSimetrica :: Ord a => Rel a -> Rel a  \n-- tal que (clausuraSimetrica r) es la clausura sim\u00e9trica de r; es\n-- decir, la menor relaci\u00f3n sim\u00e9trica que contiene a r. Por ejemplo,\n--    ghci> clausuraSimetrica (fromList [1,3,5],fromList [(1,1),(3,1),(1,5)])\n--    (fromList [1,3,5],fromList [(1,1),(1,3),(1,5),(3,1),(5,1)])\n-- ---------------------------------------------------------------------\n\nclausuraSimetrica :: Ord a => Rel a -> Rel a  \nclausuraSimetrica (u,g) =\n    (u, g `union` fromList [(y,x) | (x,y) <- elems g])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Comprobar con QuickCheck que clausuraSimetrica es\n-- sim\u00e9trica. \n-- ---------------------------------------------------------------------\n\nprop_ClausuraSimetrica :: Rel Int -> Bool\nprop_ClausuraSimetrica r = \n    simetrica (clausuraSimetrica r)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_ClausuraSimetrica\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 18. Definir la funci\u00f3n\n--    clausuraTransitiva :: Ord a => Rel a -> Rel a  \n-- tal que (clausuraTransitiva r) es la clausura transitiva de r; es\n-- decir, la menor relaci\u00f3n transitiva que contiene a r. Por ejemplo,\n--    ghci> clausuraTransitiva (fromList [1..6],fromList [(1,2),(2,5),(5,6)])\n--    (fromList [1,2,3,4,5,6],fromList [(1,2),(1,5),(1,6),(2,5),(2,6),(5,6)])\n-- ---------------------------------------------------------------------\n\nclausuraTransitiva :: Ord a => Rel a -> Rel a  \nclausuraTransitiva (u,g) = (u, aux g)\n    where aux r | cerradoTr r = r\n                | otherwise   = aux (r `union` comp r r)\n          cerradoTr r = isSubsetOf (comp r r) r\n          comp r s    = fromList [(x,z) | (x,y1) <- elems r, \n                                          (y2,z) <- elems s, \n                                          y1 == y2]\n          \n-- ---------------------------------------------------------------------\n-- Ejercicio 19. Comprobar con QuickCheck que clausuraTransitiva es\n-- transitiva. \n-- ---------------------------------------------------------------------\n\nprop_ClausuraTransitiva :: Rel Int -> Bool\nprop_ClausuraTransitiva r = \n    transitiva (clausuraTransitiva r)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_ClausuraTransitiva\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Generador de relaciones                                          --\n-- ---------------------------------------------------------------------\n\n-- genSet es un generador de relaciones binarias. Por ejemplo,\n--    ghci> sample genRel\n--    (fromList [0],fromList [])\n--    (fromList [-1,1],fromList [(-1,1)])\n--    (fromList [-3,-2],fromList [])\n--    (fromList [-2,0,1,6],fromList [(0,0),(6,0)])\n--    (fromList [-7,0,2],fromList [(-7,0),(2,0)])\n--    (fromList [2,11],fromList [(2,2),(2,11),(11,2),(11,11)])\n--    (fromList [-4,-2,1,4,5],fromList [(1,-2),(1,1),(1,5)])\n--    (fromList [-4,-3,-2,6,7],fromList [(-3,-4),(7,-3),(7,-2)])\n--    (fromList [-9,-7,0,10],fromList [(10,-9)])\n--    (fromList [-10,3,8,10],fromList [(3,3),(10,-10)])\n--    (fromList [-10,-9,-7,-6,-5,-4,-2,8,12],fromList [])\ngenRel :: (Arbitrary a, Integral a) => Gen (Rel a)\ngenRel = do xs <- listOf1 arbitrary\n            ys <- listOf (elements [(x,y) | x <- xs, y <- xs])\n            return (fromList xs, fromList ys)\n\ninstance (Arbitrary a, Integral a) => Arbitrary (Rel a) where\n    arbitrary = genRel\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la primera part 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 32 sobre relaciones binarias homog\u00e9neas 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":"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":[265],"tags":[270,316],"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\/6048"}],"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=6048"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6048\/revisions"}],"predecessor-version":[{"id":6049,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6048\/revisions\/6049"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6048"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6048"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6048"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}