Reconocimiento de relaciones funcionales entre dos conjuntos
Una relación binaria entre dos conjuntos A y B se puede representar mediante un conjunto de pares (a,b) tales que a ∈ A y b ∈ B. Por ejemplo, la relación < entre A = {1,5,3} y B = {0,2,4} se representa por {(1,2),(1,4),(3,4)}.
Una relación R entre A y B es funcional si cada elemento de A está relacionado mediante R como máximo con un elemento de B. Por ejemplo, [(2,4),(1,5),(3,4)] es funcional, pero [(3,4),(1,4),(1,2),(3,4)] no lo es.
Definir la función
|
1 |
esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool |
tal que (esFuncional r) se verifica si la relación r es funcional. Por ejemplo,
|
1 2 |
esFuncional [(2,4),(1,5),(3,4)] == True esFuncional [(3,4),(1,4),(1,2),(3,4)] == False |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
import Data.List (nub, sort) esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool esFuncional r = and [esUnitario (imagen r x) | x <- dominio r] -- (dominio r) es el dominio de la relación r. Por ejemplo, -- dominio [(5,4),(1,4),(1,2),(3,4)] == [1,3,5] dominio :: Ord a => [(a,b)] -> [a] dominio = sort . nub . map fst -- (imagen r x) es la imagen de x en la relación r. Por ejemplo, -- imagen [(5,4),(1,4),(1,2),(3,4)] 1 == [2,4] -- imagen [(5,4),(1,4),(1,2),(3,4)] 2 == [] imagen :: (Ord a, Ord b) => [(a,b)] -> a -> [b] imagen r x = conjunto [y | (x1,y) <- r, x1 == x] -- (conjunto xs) es el conjunto (es decir, lista ordenada de elementos -- distintos) correspondiente a la lista xs. Por ejemplo, -- conjunto [7,2,3,2,7,3] == [2,3,7] conjunto :: Ord a => [a] -> [a] conjunto = sort . nub -- (esUnitario xs) se verifica si xs tiene sólo un elemento. esUnitario :: [a] -> Bool esUnitario xs = length xs == 1 |