La clausura transitiva de una relaci\u00f3n binaria R es la relaci\u00f3n transitiva que contiene a R. Se puede calcular
\nusando la composici\u00f3n de relaciones. Veamos un ejemplo, en el que (R \u2218 S) representa la composici\u00f3n de R y S: sea<\/p>\n
\n R = [(1,2),(2,5),(5,6)]\n<\/pre>\nla relaci\u00f3n R no es transitiva ya que (1,2) y (1,5) pertenecen a R pero (1,5) no pertenece; sea<\/p>\n
\n R1 = R \u222a (R \u2218 R)\n = [(1,2),(2,5),(5,6),(1,5),(2,6)]\n<\/pre>\nla relaci\u00f3n R1 tampoco es transitiva ya que (1,2) y (2,6) pertenecen a R pero (1,6) no pertenece; sea<\/p>\n
\n R2 = R1 \u222a (R1 \u2218 R1)\n = [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]\n<\/pre>\nLa relaci\u00f3n R2 es transitiva y contiene a R. Adem\u00e1s, R2 es la clausura transitiva de R.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n clausuraTransitiva :: Ord a => [(a,a)] -> [(a,a)] \n<\/pre>\ntal que (clausuraTransitiva r) es la clausura transitiva de r; es decir, la menor relaci\u00f3n transitiva que contiene a r. Por ejemplo,<\/p>\n
\n \u03bb> clausuraTransitiva [(1,2),(2,5),(5,6)]\n [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]\n \u03bb> clausuraTransitiva [(1,2),(2,5),(5,6),(6,3)]\n [(1,2),(2,5),(5,6),(6,3),(1,5),(2,6),(5,3),(1,6),(2,3),(1,3)]\n \u03bb> length (clausuraTransitiva [(n,n+1) | n <- [1..100]])\n 5050\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.List (union, nub, sort)\nimport Data.Maybe (mapMaybe)\nimport qualified Data.Map as M (Map, assocs, empty, insertWith, lookup, map)\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nclausuraTransitiva1 :: Ord a => [(a,a)] -> [(a,a)] \nclausuraTransitiva1 r\n | transitiva r = r\n | otherwise = clausuraTransitiva1 r1\n where r1 = r `union` composicion r r\n\n-- (transitiva r) se verifica si la relaci\u00f3n r es transitiva. Por\n-- ejemplo, \n-- transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)] == True\n-- transitiva [(1,1),(1,3),(3,1),(5,5)] == False\ntransitiva :: Ord a => [(a,a)] -> Bool\ntransitiva r = subconjunto (composicion r r) r\n\n-- (composicion r s) es la composici\u00f3n de las relaciones binarias r y\n-- s. Por ejemplo, \n-- \u03bb> composicion [(1,2)] [(2,3),(2,4)]\n-- [(1,3),(1,4)]\n-- \u03bb> composicion [(1,2),(5,2)] [(2,3),(2,4)]\n-- [(1,3),(1,4),(5,3),(5,4)]\n-- \u03bb> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)]\n-- [(1,3)]\ncomposicion :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\ncomposicion r s = nub [(x,y) | (x,u) <- r, (v,y) <- s, u == v] \n\n-- (subconjunto xs ys) se verifica si xs es un subconjunto de xs. Por\n-- ejemplo, \n-- subconjunto [1,3] [3,1,5] == True\n-- subconjunto [3,1,5] [1,3] == False\nsubconjunto :: Ord a => [a] -> [a] -> Bool\nsubconjunto xs ys = all (`elem` ys) xs\n\n-- 2\u00aa soluci\u00f3n\n-- =============\n\nclausuraTransitiva2 :: Ord a => [(a,a)] -> [(a,a)] \nclausuraTransitiva2 r\n | r1 == r = r\n | otherwise = clausuraTransitiva2 r1\n where r1 = r `union` composicion r r\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_clausuraTransitiva :: [(Int,Int)] -> Bool\nprop_clausuraTransitiva r =\n all (== sort (clausuraTransitiva1 r))\n [sort (clausuraTransitiva2 r),\n sort (clausuraTransitiva3 r)]\n \n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_clausuraTransitiva\n-- +++ OK, passed 100 tests.\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nclausuraTransitiva3 :: Ord a => [(a,a)] -> [(a,a)] \nclausuraTransitiva3 r\n | transitiva3 r = r\n | otherwise = clausuraTransitiva3 r1\n where r1 = r `union` composicion3 r r\n\ntransitiva3 :: Ord a => [(a,a)] -> Bool\ntransitiva3 r = subconjunto (composicion3 r r) r\n\ncomposicion3 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\ncomposicion3 r s =\n relAlista (composicionRel (listaArel r) (listaArel s))\n\n-- Una relaci\u00f3n se puede representar por un diccionario donde las claves\n-- son los elementos y los valores son las listas de los elementos con\n-- los que se relaciona.\ntype Rel a = M.Map a [a]\n\n-- (listaArel xys) es la relaci\u00f3n correspondiente a la lista de pares\n-- xys. Por ejemplo.\n-- \u03bb> listaArel [(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]\n-- fromList [(1,[1,2,3,6]),(2,[2,6]),(3,[3,6]),(6,[6])]\nlistaArel :: Ord a => [(a,a)] -> Rel a\nlistaArel [] = M.empty\nlistaArel ((x,y):xys) = M.insertWith (++) x [y] (listaArel xys)\n\n-- (composicionRel r s) es la composici\u00f3n de las relaciones r y s. Por\n-- ejemplo,\n-- \u03bb> r = listaArel [(1,2),(5,2)]\n-- \u03bb> s = listaArel [(2,3),(2,4)]\n-- \u03bb> composicionRel r s\n-- fromList [(1,[3,4]),(5,[3,4])]\ncomposicionRel :: Ord a => Rel a -> Rel a -> Rel a\ncomposicionRel r s =\n M.map f r \n where f xs = concat (mapMaybe (`M.lookup` s) xs)\n\n-- (relAlista r) es la lista de pares correspondientes a la relaci\u00f3n\n-- r. Por ejemplo,\n-- \u03bb> relAlista (M.fromList [(1,[3,4]),(5,[3,4])])\n-- [(1,3),(1,4),(5,3),(5,4)]\nrelAlista :: Ord a => Rel a -> [(a,a)]\nrelAlista r =\n nub [(x,y) | (x,ys) <- M.assocs r, y <- ys] \n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> length (clausuraTransitiva1 [(n,n+1) | n <- [1..60]])\n-- 1830\n-- (2.15 secs, 453,533,992 bytes)\n-- \u03bb> length (clausuraTransitiva2 [(n,n+1) | n <- [1..60]])\n-- 1830\n-- (2.23 secs, 558,571,904 bytes)\n-- \u03bb> length (clausuraTransitiva3 [(n,n+1) | n <- [1..60]])\n-- 1830\n-- (0.25 secs, 207,168,552 bytes)\n<\/pre>\n