Las relaciones binarias en un conjunto A se pueden representar mediante conjuntos de pares de elementos de A. Por ejemplo, la relaci\u00f3n de divisibilidad en el conjunto {1,2,3,6} se representa por<\/p>\n
\n [(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]\n<\/pre>\nLa composici\u00f3n de dos relaciones binarias R y S en el conjunto A es la relaci\u00f3n binaria formada por los pares (x,y) para los que existe un z tal que (x,z) \u2208 R y (z,y) \u2208 S.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n composicion :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\n<\/pre>\ntal que (composicion r s) es la composici\u00f3n de las relaciones binarias r y s. Por ejemplo,<\/p>\n
\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)]\n<\/pre>\nNota:<\/strong> Se supone que las relaciones binarias son listas sin elementos repetidos.<\/p>\nSoluciones<\/h4>\n\nimport Data.List (nub, sort)\nimport Data.Maybe (mapMaybe)\nimport qualified Data.Set.Monad as S (Set, fromList, toList)\nimport qualified Data.Map as M (Map, assocs, empty, insertWith, lookup, map)\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ncomposicion1 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\ncomposicion1 r s =\n nub [(x,y) | (x,u) <- r, (v,y) <- s, u == v] \n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ncomposicion2 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\ncomposicion2 r s =\n S.toList (composicionS (S.fromList r) (S.fromList s))\n\ncomposicionS :: Ord a => S.Set (a,a) -> S.Set (a,a) -> S.Set (a,a)\ncomposicionS r s = \n [(x,y) | (x,u) <- r, (v,y) <- s, u == v] \n\n-- 3\u00aa soluci\u00f3n\n-- ===========\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-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_composicion :: [(Int,Int)] -> [(Int,Int)] -> Bool\nprop_composicion r s =\n all (== sort (composicion1 r' s'))\n [sort (composicion2 r' s'),\n sort (composicion3 r' s')]\n where r' = nub r\n s' = nub s\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_composicion\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> length (composicion1 [(n,n+1) | n <- [1..2000]] [(n,n+1) | n <- [1..2000]])\n-- 1999\n-- (1.54 secs, 770,410,352 bytes)\n-- \u03bb> length (composicion2 [(n,n+1) | n <- [1..2000]] [(n,n+1) | n <- [1..2000]])\n-- 1999\n-- (1.66 secs, 1,348,948,096 bytes)\n-- \u03bb> length (composicion3 [(n,n+1) | n <- [1..2000]] [(n,n+1) | n <- [1..2000]])\n-- 1999\n-- (0.07 secs, 6,960,552 bytes)\n--\n-- \u03bb> r100 = [(n,k) | n <- [1..100], k <- [1..n]]\n-- \u03bb> length (composicion1 r100 r100)\n-- 5050\n-- (9.91 secs, 4,946,556,944 bytes)\n-- \u03bb> length (composicion2 r100 r100)\n-- 5050\n-- (13.59 secs, 15,241,357,536 bytes)\n-- \u03bb> length (composicion3 r100 r100)\n-- 5050\n-- (0.35 secs, 52,015,544 bytes)\n<\/pre>\n