Menu Close

Clausura respecto de una operación binaria

Se dice que una operador @ es interno en un conjunto A si al @ sobre elementos de A se obtiene como resultado otro elemento de A. Por ejemplo, la suma es un operador interno en el conjunto de los números naturales pares.

La clausura de un conjunto A con respecto a un operador @ es el menor conjunto B tal que A está contenido en B y el operador @ es interno en el conjunto B. Por ejemplo, la clausura del conjunto {2} con respecto a la suma es el conjunto de los números pares positivos:

   {2, 4, 6, 8, ...} = {2*k | k <- [1..]}

Definir la función

   clausuraOperador :: (Int -> Int -> Int) -> Set Int -> Set Int

tal que (clausuraOperador op xs) es la clausura del conjunto xs con respecto a la operación op. Por ejemplo,

   clausuraOperador gcd (fromList [6,9,10])     ==
      fromList [1,2,3,6,9,10]
   clausuraOperador gcd (fromList [42,70,105])  ==
      fromList [7,14,21,35,42,70,105]
   clausuraOperador lcm (fromList [6,9,10])     ==
      fromList [6,9,10,18,30,90]
   clausuraOperador lcm (fromList [2,3,5,7])    ==
      fromList [2,3,5,6,7,10,14,15,21,30,35,42,70,105,210]

Soluciones

import Prelude hiding (map)
import Data.Set ( Set
                , elems
                , fromList
                , map
                , notMember
                , union
                , unions
                ) 
 
-- 1ª definición 
clausuraOperador :: (Int -> Int -> Int) -> Set Int -> Set Int
clausuraOperador op =
  until (\ xs -> null [(x,y) | x <- elems xs,
                               y <- elems xs,
                               notMember (op x y) xs])
        (\ xs -> union xs (fromList [op x y | x <- elems xs,
                                              y <- elems xs]))
 
-- 2ª definición 
clausuraOperador2 :: (Int -> Int -> Int) -> Set Int -> Set Int
clausuraOperador2 op = until ((==) <*> g) g
  where g ys = unions [map (`op` y) ys | y <- elems ys]

3 soluciones de “Clausura respecto de una operación binaria

  1. angruicam1
    import Prelude  hiding (map)
    import Data.Set (elems, map, Set, unions)
     
    clausuraOperador :: (Int -> Int -> Int) -> Set Int -> Set Int
    clausuraOperador op = until ((==) . id <*> g) g
      where g ys = unions [map (`op` y) ys | y <- elems ys]
  2. goncarlop
    import Data.Set
     
    clausuraOperador :: (Int -> Int -> Int) -> Set Int -> Set Int
    clausuraOperador op c
      | c == x    = c
      | otherwise = clausuraOperador op x
      where x = fromList [op a b | a <- toList c, b <- toList c]
  3. carriomon1
    import Data.Set  as S
    import Data.List as L
     
    clausuraOperador :: (Int -> Int -> Int) -> Set Int -> Set Int
    clausuraOperador f xs
      | xs == ys  = xs 
      | otherwise = S.union xs ys
      where ys = completo f (toList xs) 
     
    completo :: (Int -> Int -> Int) -> [Int] -> Set Int
    completo f xs
      | fromList xs == fromList (opera f xs) = fromList xs
      | otherwise                            = completo f (opera f xs) 
     
    opera ::  (Int -> Int -> Int) -> [Int] -> [Int] 
    opera f xs = concat [L.map (x -> f a x) xs | a <- xs]

Escribe tu solución

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