Transitividad de una relación
Una relación binaria R sobre un conjunto A es transitiva cuando se cumple que siempre que un elemento se relaciona con otro y éste último con un tercero, entonces el primero se relaciona con el
Definir la función
transitiva :: Eq a => [(a,a)] -> Bool
tal que (transitiva r) se verifica si la relación r es transitiva. Por ejemplo,
transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)] == True transitiva [(1,1),(1,3),(3,1),(5,5)] == False
Soluciones
import Data.List (nub) -- 1ª definición -- ============= transitiva1 :: Eq a => [(a,a)] -> Bool transitiva1 r = and [(x,y) `elem` r | (x,u) <- r, (v,y) <- r, u == v] -- 2ª definición -- ============= transitiva2 :: Eq a => [(a,a)] -> Bool transitiva2 r = all (`elem` r) [(x,y) | (x,u) <- r, (v,y) <- r, u == v] -- 3ª definición -- ============= transitiva3 :: Eq a => [(a,a)] -> Bool transitiva3 r = subconjunto (composicion r r) r -- (subconjunto xs ys) se verifica si xs es un subconjunto de xs. Por -- ejemplo, -- subconjunto [1,3] [3,1,5] == True -- subconjunto [3,1,5] [1,3] == False subconjunto :: Eq a => [a] -> [a] -> Bool subconjunto xs ys = and [elem x ys | x <- xs] -- (composicion r s) es la composición de las relaciones binarias r y -- s. Por ejemplo, -- λ> composicion [(1,2)] [(2,3),(2,4)] -- [(1,3),(1,4)] -- λ> composicion [(1,2),(5,2)] [(2,3),(2,4)] -- [(1,3),(1,4),(5,3),(5,4)] -- λ> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)] -- [(1,3)] composicion :: Eq a => [(a,a)] -> [(a,a)] -> [(a,a)] composicion r s = nub [(x,y) | (x,u) <- r, (v,y) <- s, u == v]