{"id":4312,"date":"2014-05-13T18:30:07","date_gmt":"2014-05-13T16:30:07","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4312"},"modified":"2014-05-16T08:36:54","modified_gmt":"2014-05-16T06:36:54","slug":"i1m2013-ejercicios-de-relaciones-binarias-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-ejercicios-de-relaciones-binarias-en-haskell\/","title":{"rendered":"I1M2013: Ejercicios de relaciones binarias 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-13\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones de los ejercicios sobre relaciones binarias de la 29\u00aa relaci\u00f3n.<\/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).\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.List\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 la lista de los\n-- elementos de A (el universo de R) y ps es la lista de pares de R (el\n-- grafo de R). Definir el tipo de dato (Rel a) para representar las\n-- relaciones binarias sobre a.  \n-- ---------------------------------------------------------------------\n\ntype Rel a = ([a],[(a,a)])\n\n-- ---------------------------------------------------------------------\n-- Nota. En los ejemplos usaremos las siguientes relaciones binarias: \n--    r1, r2, r3 :: Rel Int\n--    r1 = ([1..9],[(1,3), (2,6), (8,9), (2,7)])\n--    r2 = ([1..9],[(1,3), (2,6), (8,9), (3,7)])\n--    r3 = ([1..9],[(1,3), (2,6), (8,9), (3,6)])\n-- ---------------------------------------------------------------------\n\nr1, r2, r3 :: Rel Int\nr1 = ([1..9],[(1,3), (2,6), (8,9), (2,7)])\nr2 = ([1..9],[(1,3), (2,6), (8,9), (3,7)])\nr3 = ([1..9],[(1,3), (2,6), (8,9), (3,6)])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    universo :: Eq a => Rel a -> [a]\n-- tal que (universo r) es el universo de la relaci\u00f3n r. Por ejemplo, \n--    r1           ==  ([1,2,3,4,5,6,7,8,9],[(1,3),(2,6),(8,9),(2,7)])\n--    universo r1  ==  [1,2,3,4,5,6,7,8,9]\n-- ---------------------------------------------------------------------\n\nuniverso :: Eq a => Rel a -> [a]\nuniverso (us,_) = us\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    grafo :: Eq a => ([a],[(a,a)]) -> [(a,a)]\n-- tal que (grafo r) es el grafo de la relaci\u00f3n r. Por ejemplo, \n--    r1        ==  ([1,2,3,4,5,6,7,8,9],[(1,3),(2,6),(8,9),(2,7)])\n--    grafo r1  ==  [(1,3),(2,6),(8,9),(2,7)]\n-- ---------------------------------------------------------------------\n\ngrafo :: Eq a => ([a],[(a,a)]) -> [(a,a)]\ngrafo (_,ps) = ps\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    reflexiva :: Eq a => Rel a -> Bool\n-- tal que (reflexiva r) se verifica si la relaci\u00f3n r es reflexiva. Por\n-- ejemplo, \n--    reflexiva ([1,3],[(1,1),(1,3),(3,3)])    ==  True\n--    reflexiva ([1,2,3],[(1,1),(1,3),(3,3)])  ==  False\n-- ---------------------------------------------------------------------\n\nreflexiva :: Eq a => Rel a -> Bool\nreflexiva (us,ps) = and [elem (x,x) ps | x <- us]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    simetrica :: Eq a => Rel a -> Bool\n-- tal que (simetrica r) se verifica si la relaci\u00f3n r es sim\u00e9trica. Por\n-- ejemplo, \n--    simetrica ([1,3],[(1,1),(1,3),(3,1)])  ==  True\n--    simetrica ([1,3],[(1,1),(1,3),(3,2)])  ==  False\n--    simetrica ([1,3],[])                   ==  True\n-- ---------------------------------------------------------------------\n\nsimetrica :: Eq a => Rel a -> Bool\nsimetrica (us,ps) = and [(y,x) `elem` ps | (x,y) <- ps] \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    subconjunto :: Eq a => [a] -> [a] -> Bool\n-- tal que (subconjunto xs ys) se verifica si xs es un subconjunto de\n-- xs. Por ejemplo,\n--    subconjunto [1,3] [3,1,5]  ==  True\n--    subconjunto [3,1,5] [1,3]  ==  False\n-- ---------------------------------------------------------------------\n\nsubconjunto :: Eq a => [a] -> [a] -> Bool\nsubconjunto xs ys = and [elem x ys | x <- xs]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    composicion :: Eq 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> composicion ([1,2],[(1,2),(2,2)]) ([1,2],[(2,1)])\n--    ([1,2],[(1,1),(2,1)])\n-- ---------------------------------------------------------------------\n\ncomposicion :: Eq a => Rel a -> Rel a -> Rel a\ncomposicion (xs,ps) (_,qs) = \n    (xs,[(x,z) | (x,y) <- ps, (y1,z) <- qs, y == y1])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    transitiva :: Eq a => Rel a -> Bool\n-- tal que (transitiva r) se verifica si la relaci\u00f3n r es transitiva. \n-- Por ejemplo,\n--    transitiva ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])  ==  True\n--    transitiva ([1,3,5],[(1,1),(1,3),(3,1),(5,5)])        ==  False\n-- ---------------------------------------------------------------------\n\ntransitiva :: Eq a => Rel a -> Bool\ntransitiva r@(xs,ps) = \n    subconjunto (grafo (composicion r r)) ps\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    esEquivalencia :: Eq 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 ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])\n--    True\n--    ghci> esEquivalencia ([1,2,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])\n--    False\n--    ghci> esEquivalencia ([1,3,5],[(1,1),(1,3),(3,3),(5,5)])\n--    False\n-- ---------------------------------------------------------------------\n\nesEquivalencia :: Eq a => Rel a -> Bool\nesEquivalencia r = reflexiva r && simetrica r && transitiva r\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    irreflexiva :: Eq 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--    irreflexiva ([1,2,3],[(1,2),(2,1),(2,3)])  ==  True\n--    irreflexiva ([1,2,3],[(1,2),(2,1),(3,3)])  ==  False\n-- ---------------------------------------------------------------------\n\nirreflexiva :: Eq a => Rel a -> Bool\nirreflexiva (xs,ps) = and [(x,x) `notElem` ps | x <- xs]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir la funci\u00f3n\n--    antisimetrica :: Eq 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 ([1,2],[(1,2)])        ==  True\n--    antisimetrica ([1,2],[(1,2),(2,1)])  ==  False\n--    antisimetrica ([1,2],[(1,1),(2,1)])  ==  True\n-- ---------------------------------------------------------------------\n\nantisimetrica :: Eq a => Rel a -> Bool\nantisimetrica (_,ps) =\n    null [(x,y) | (x,y) <- ps, x \/= y, (y,x) `elem` ps]\n\n-- Otra definici\u00f3n es\nantisimetrica2 :: Eq a => Rel a -> Bool\nantisimetrica2 (xs,ps) = \n    and [((x,y) `elem` ps && (y,x) `elem` ps) --> (x == y) \n         | x <- xs, y <- xs]\n    where p --> q = not p || q\n\n-- Las dos definiciones son equivalentes\nprop_antisimetrica :: Rel Int -> Bool\nprop_antisimetrica r =\n    antisimetrica r == antisimetrica2 r\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_antisimetrica\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    total :: Eq 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 ([1,3],[(1,1),(3,1),(3,3)])  ==  True\n--    total ([1,3],[(1,1),(3,1)])        ==  False\n--    total ([1,3],[(1,1),(3,3)])        ==  False\n-- ---------------------------------------------------------------------\n\ntotal :: Eq a => Rel a -> Bool\ntotal (xs,ps) = \n    and [(x,y) `elem` ps || (y,x) `elem` ps | x <- xs, y <- xs]\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 19 tests.\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Clausuras                                                        --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la funci\u00f3n\n--    clausuraReflexiva :: Eq 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 ([1,3],[(1,1),(3,1)])\n--    ([1,3],[(1,1),(3,1),(3,3)])\n-- ---------------------------------------------------------------------\n\nclausuraReflexiva :: Eq a => Rel a -> Rel a  \nclausuraReflexiva (xs,ps) =\n  (xs, ps `union` [(x,x) | x <- xs])\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_ClausuraRefl\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. Definir la funci\u00f3n\n--    clausuraSimetrica :: Eq 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 ([1,3,5],[(1,1),(3,1),(1,5)])\n--    ([1,3,5],[(1,1),(3,1),(1,5),(1,3),(5,1)])\n-- ---------------------------------------------------------------------\n\nclausuraSimetrica :: Eq a => Rel a -> Rel a  \nclausuraSimetrica (xs,ps) =\n    (xs, ps `union` [(y,x) | (x,y) <- ps])\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 :: Eq 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 ([1..6],[(1,2),(2,5),(5,6)])\n--    ([1,2,3,4,5,6],[(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)])\n-- ---------------------------------------------------------------------\n\nclausuraTransitiva :: Eq a => Rel a -> Rel a  \nclausuraTransitiva (xs,ps) = (xs, aux ps)\n    where aux xs | cerradoTr xs = xs\n                 | otherwise    = aux (xs `union` (comp xs xs))\n          cerradoTr r = subconjunto (comp r r) r\n          comp r s    = [(x,z) | (x,y) <- r, (y1,z) <- s, y == y1]\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> quickCheck prop_ClausuraTransitiva\n--    +++ OK, passed 100 tests.\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 hemos comentado las soluciones de los ejercicios sobre relaciones binarias de la 29\u00aa relaci\u00f3n. Los ejercicios y su soluci\u00f3n 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],"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\/4312"}],"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=4312"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4312\/revisions"}],"predecessor-version":[{"id":4315,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4312\/revisions\/4315"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4312"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4312"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4312"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}