Menu Close

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

   esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool

tal que (esFuncional r) se verifica si la relación r es funcional. Por ejemplo,

   esFuncional [(2,4),(1,5),(3,4)]        ==  True
   esFuncional [(3,4),(1,4),(1,2),(3,4)]  ==  False

Soluciones

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

8 soluciones de “Reconocimiento de relaciones funcionales entre dos conjuntos

  1. antnavoro
    esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool
    esFuncional xs = nub a == a
      where a = map fst xs
  2. angruicam1
    import Data.List (nub)
     
    esFuncional :: (Ord a, Ord b) = [(a,b)] -> Bool
    esFuncional r = rs == nub rs
        where rs = fst . unzip $ r
  3. jaibengue
    import Data.List
     
    esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool
    esFuncional = aux . map (fst)
      where aux (x:xs) | x `elem` xs = False
                       | otherwise   = aux xs
            aux _ = True
  4. jaibengue
    import Data.List
     
    esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool
    esFuncional = aux . sort
      where aux (x:x':xs) | fst x == fst x' && snd x /= snd x' = False
                          | otherwise                          = aux (x':xs)
            aux _ = True
  5. angruicam1
    import Data.List (nub)
     
    esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool
    esFuncional r = rs == nub rs
      where rs = fst . unzip $ nub r
    • jaibengue

      Tu función es O(n^2), ya que nub es O(n^2), y la mía usa sort que es O(n (log n)).

      λ> esFuncional (zip [40000,39999..1] (repeat 0))
      True
      (27.81 secs, 23,463,512 bytes)
      λ> esFuncional2 (zip [40000,39999..1] (repeat 0))
      True
      (0.06 secs, 26,464,080 bytes)

      La función mas eficiente creo que sería ir elemento a elemento sacándolo de la lista y metiéndolo en una caja correspondiente, inicialmente vacía, y comparando si es diferente al elemento que hay en la caja, en ese caso la respuesta es False y en caso contrario desechamos el elemento y seguimos sacando elementos de la lista y metiéndolos en sus cajas. Esta función es lineal pero quizá abusa demasiado de memoria. Aunque realmente mi problema es que no sabría implementarla en Haskell. :/

  6. alvblamol
    import Data.List
    esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool
    esFuncional xs =[fst p | p<-(nub xs)] == nub [fst p | p<-(nub xs)]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.