{"id":6614,"date":"2019-04-03T11:17:48","date_gmt":"2019-04-03T09:17:48","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6614"},"modified":"2019-04-05T19:46:06","modified_gmt":"2019-04-05T17:46:06","slug":"i1m2018-relaciones-binarias-homogeneas-con-la-libreria-de-conjuntos-de-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-relaciones-binarias-homogeneas-con-la-libreria-de-conjuntos-de-haskell\/","title":{"rendered":"I1M2018: Relaciones binarias homog\u00e9neas con la librer\u00eda de conjuntos de Haskell"},"content":{"rendered":"<p>En la tercera part 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 31 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-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n de ejercicios es definir propiedades y\n-- operaciones sobre las relaciones binarias (homog\u00e9neas) usando la\n-- librer\u00eda Data.Set.\n--\n-- Como referencia se puede usar el art\u00edculo de la wikipedia\n-- http:\/\/bit.ly\/HVHOPS \n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\nimport Data.Set as S\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Una relaci\u00f3n binaria S sobre un conjunto A se puede\n-- representar mediante la expresi\u00f3n (R xs ps) donde xs es el conjunto\n-- de los elementos de A (el universo de S) y ps es el conjunto de pares\n-- de S (el grafo de S). Definir el tipo de dato (Rel a) para\n-- representar las relaciones binarias sobre a.  \n-- ---------------------------------------------------------------------\n\ndata Rel a = R (Set a) (Set (a,a))\n  deriving Show\n\n-- ---------------------------------------------------------------------\n-- Nota. En los ejemplos usaremos las siguientes relaciones binarias: \n--    r1, r2, r3 :: Rel Int\n--    r1 = R (fromList [1..9]) (fromList [(1,3), (2,6), (8,9), (2,7)])\n--    r2 = R (fromList [1..9]) (fromList [(1,3), (2,6), (8,9), (3,7)])\n--    r3 = R (fromList [1..9]) (fromList [(1,3), (2,6), (8,9), (3,6)])\n-- ---------------------------------------------------------------------\n\nr1, r2, r3 :: Rel Int\nr1 = R (fromList [1..9]) (fromList [(1,3), (2,6), (8,9), (2,7)])\nr2 = R (fromList [1..9]) (fromList [(1,3), (2,6), (8,9), (3,7)])\nr3 = R (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 (R 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 (R _ 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 (R (fromList [1,3]) (fromList [(1,1),(1,3),(3,3)]))\n--    True\n--    ghci> reflexiva (R (fromList [1,2,3]) (fromList [(1,1),(1,3),(3,3)]))\n--    False\n-- ---------------------------------------------------------------------\n\nreflexiva :: Ord a => Rel a -> Bool\nreflexiva (R 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 (R (fromList [1,3]) (fromList [(1,1),(1,3),(3,1)]))\n--    True\n--    ghci> simetrica (R (fromList [1,3]) (fromList [(1,1),(1,3),(3,2)]))\n--    False\n--    ghci> simetrica (R (fromList [1,3]) (fromList []))\n--    True\n-- ---------------------------------------------------------------------\n\nsimetrica :: Ord a => Rel a -> Bool\nsimetrica (R _ 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 = (R (fromList [1,2]) (fromList [(1,2),(2,2)]))\n--    ghci> let r2 = (R (fromList [1,2]) (fromList [(2,1)]))\n--    ghci> let r3 = (R (fromList [1,2]) (fromList [(1,1)]))\n--    ghci> composicion r1 r2\n--    R (fromList [1,2]) (fromList [(1,1),(2,1)])\n--    ghci> composicion r1 r3\n--    R (fromList [1,2,3,4,5,6,7,8,9]) (fromList [])\n-- ---------------------------------------------------------------------\n\ncomposicion :: Ord a => Rel a -> Rel a -> Rel a\ncomposicion (R u g1) (R _ g2) = \n  R 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 (R (fromList [1,3,5])\n--                     (fromList [(1,1),(1,3),(3,1),(3,3),(5,5)]))\n--  True\n--  ghci> transitiva (R (fromList [1,3,5])\n--                      (fromList [(1,1),(1,3),(3,1),(5,5)]))\n--  False\n-- ---------------------------------------------------------------------\n\ntransitiva :: Ord a => Rel a -> Bool\ntransitiva r@(R _ 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 (R (fromList [1,3,5])\n--                            (fromList [(1,1),(1,3),(3,1),(3,3),(5,5)]))\n--    True\n--    ghci> esEquivalencia (R (fromList [1,2,3,5])\n--                            (fromList [(1,1),(1,3),(3,1),(3,3),(5,5)]))\n--    False\n--    ghci> esEquivalencia (R (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 (R (fromList [1,2,3]) (fromList [(1,2),(2,1),(2,3)]))\n--    True\n--    ghci> irreflexiva (R (fromList [1,2,3]) (fromList [(1,2),(2,1),(3,3)]))\n--    False\n-- ---------------------------------------------------------------------\n\nirreflexiva :: Ord a => Rel a -> Bool\nirreflexiva (R 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 (R (fromList [1,2]) (fromList [(1,2)]))       == True\n--    antisimetrica (R (fromList [1,2]) (fromList [(1,2),(2,1)])) == False\n--    antisimetrica (R (fromList [1,2]) (fromList [(1,1),(2,1)])) == True\n-- ---------------------------------------------------------------------\n\nantisimetrica :: Ord a => Rel a -> Bool\nantisimetrica (R _ 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 (R 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 est\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 (R 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 (R u g) =\n  R 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 (R (fromList [1,3,5])\n--                               (fromList [(1,1),(3,1),(1,5)]))\n--    R (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 (R u g) =\n  R 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 (R (fromList [1..6])\n--                                (fromList [(1,2),(2,5),(5,6)]))\n--    R (fromList [1,2,3,4,5,6])\n--      (fromList [(1,2),(1,5),(1,6),(2,5),(2,6),(5,6)])\n-- ---------------------------------------------------------------------\n\nclausuraTransitiva :: Ord a => Rel a -> Rel a  \nclausuraTransitiva (R u g) = R 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\n  xs <- listOf1 arbitrary\n  ys <- listOf (elements [(x,y) | x <- xs, y <- xs])\n  return (R (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 tercera part de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han resuelto ejercicios de la relaci\u00f3n 31 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":[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\/6614"}],"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=6614"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6614\/revisions"}],"predecessor-version":[{"id":6617,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6614\/revisions\/6617"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6614"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6614"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6614"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}