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:
|
1 |
{2, 4, 6, 8, ...} = {2*k | k <- [1..]} |
Definir la función
|
1 |
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,
|
1 2 3 4 5 6 7 8 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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 Comentarios