Una relaci\u00f3n binaria R sobre un conjunto A es transitiva cuando se cumple que siempre que un elemento se relaciona con otro y \u00e9ste \u00faltimo con un tercero, entonces el primero se relaciona con el tercero.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n transitiva :: Ord a => [(a,a)] -> Bool\n<\/pre>\ntal que (transitiva r) se verifica si la relaci\u00f3n r es transitiva. Por ejemplo,<\/p>\n
\n transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)] == True\n transitiva [(1,1),(1,3),(3,1),(5,5)] == False\n transitiva [(n,n) | n <- [1..10^4]] == True\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.List (nub)\nimport Data.Maybe (mapMaybe)\nimport qualified Data.Map as M (Map, assocs, empty, insertWith, lookup, map)\nimport Test.QuickCheck (maxSize, quickCheckWith, stdArgs)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntransitiva1 :: Ord a => [(a,a)] -> Bool\ntransitiva1 r = \n and [(x,y) `elem` r | (x,u) <- r, (v,y) <- r, u == v]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ntransitiva2 :: Ord a => [(a,a)] -> Bool\ntransitiva2 r = \n all (`elem` r) [(x,y) | (x,u) <- r, (v,y) <- r, u == v]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ntransitiva3 :: Ord a => [(a,a)] -> Bool\ntransitiva3 r =\n subconjunto (composicion r r) r\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 =\n all (`elem`ys) xs\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 =\n nub [(x,y) | (x,u) <- r, (v,y) <- s, u == v] \n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ntransitiva4 :: Ord a => [(a,a)] -> Bool\ntransitiva4 r =\n subconjunto (composicion4 r r) r\n\ncomposicion4 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\ncomposicion4 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-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_transitiva :: [(Int,Int)] -> Bool\nprop_transitiva r =\n all (== transitiva1 r)\n [transitiva2 r,\n transitiva3 r,\n transitiva4 r] \n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheckWith (stdArgs {maxSize=7}) prop_transitiva\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> transitiva1 [(n,n) | n <- [1..5*10^3]]\n-- True\n-- (4.27 secs, 1,403,139,032 bytes)\n-- \u03bb> transitiva2 [(n,n) | n <- [1..5*10^3]]\n-- True\n-- (4.24 secs, 1,402,739,056 bytes)\n-- \u03bb> transitiva3 [(n,n) | n <- [1..5*10^3]]\n-- True\n-- (4.41 secs, 1,403,219,880 bytes)\n-- \u03bb> transitiva4 [(n,n) | n <- [1..5*10^3]]\n-- True\n-- (0.46 secs, 16,206,624 bytes)\n<\/pre>\n