Un conjunto A est\u00e1 cerrado respecto de una funci\u00f3n f si para elemento x de A se tiene que f(x) pertenece a A. La clausura de un conjunto B respecto de una funci\u00f3n f es el menor conjunto A que contiene a B y es cerrado respecto de f. Por ejemplo, la clausura de {0,1,2] respecto del opuesto es {-2,-1,0,1,2}.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n clausura :: Ord a => (a -> a) -> [a] -> [a]\n<\/pre>\ntal que (clausura f xs)<\/code> es la clausura de xs<\/code> respecto de f. Por ejemplo,<\/p>\n\n clausura (\\x -> -x) [0,1,2] == [-2,-1,0,1,2]\n clausura (\\x -> (x+1) `mod` 5) [0] == [0,1,2,3,4]\n length (clausura (\\x -> (x+1) `mod` (10^6)) [0]) == 1000000\n<\/pre>\nSoluciones<\/h4>\n\nmodule Clausura where\n\nimport Data.List ((\\\\), nub, sort, union)\nimport Test.QuickCheck.HigherOrder (quickCheck')\nimport qualified Data.Set as S (Set, difference, fromList, map, null, toList, union)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nclausura1 :: Ord a => (a -> a) -> [a] -> [a]\nclausura1 f xs\n | esCerrado f xs = sort xs\n | otherwise = clausura1 f (expansion f xs)\n\n-- (esCerrado f xs) se verifica si al aplicar f a cualquier elemento de\n-- xs se obtiene un elemento de xs. Por ejemplo,\n-- \u03bb> esCerrado (\\x -> -x) [0,1,2]\n-- False\n-- \u03bb> esCerrado (\\x -> -x) [0,1,2,-2,-1]\n-- True\nesCerrado :: Ord a => (a -> a) -> [a] -> Bool\nesCerrado f xs = all (`elem` xs) (map f xs)\n\n-- (expansion f xs) es la lista (sin repeticiones) obtenidas a\u00f1adi\u00e9ndole\n-- a xs el resulta de aplicar f a sus elementos. Por ejemplo,\n-- expansion (\\x -> -x) [0,1,2] == [0,1,2,-1,-2]\nexpansion :: Ord a => (a -> a) -> [a] -> [a]\nexpansion f xs = xs `union` map f xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nclausura2 :: Ord a => (a -> a) -> [a] -> [a]\nclausura2 f xs = sort (until (esCerrado f) (expansion f) xs)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nclausura3 :: Ord a => (a -> a) -> [a] -> [a]\nclausura3 f xs = aux xs xs\n where aux ys vs | null ns = sort vs\n | otherwise = aux ns (vs ++ ns)\n where ns = nub (map f ys) \\\\ vs\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nclausura4 :: Ord a => (a -> a) -> [a] -> [a]\nclausura4 f xs = S.toList (clausura4' f (S.fromList xs))\n\nclausura4' :: Ord a => (a -> a) -> S.Set a -> S.Set a\nclausura4' f xs = aux xs xs\n where aux ys vs | S.null ns = vs\n | otherwise = aux ns (vs `S.union` ns)\n where ns = S.map f ys `S.difference` vs\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_clausura :: (Int -> Int) -> [Int] -> Bool\nprop_clausura f xs =\n all (== clausura1 f xs')\n [ clausura2 f xs'\n , clausura3 f xs'\n , clausura4 f xs'\n ]\n where xs' = sort (nub xs)\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck' prop_clausura\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> length (clausura1 (\\x -> (x+1) `mod` 800) [0])\n-- 800\n-- (1.95 secs, 213,481,560 bytes)\n-- \u03bb> length (clausura2 (\\x -> (x+1) `mod` 800) [0])\n-- 800\n-- (1.96 secs, 213,372,824 bytes)\n-- \u03bb> length (clausura3 (\\x -> (x+1) `mod` 800) [0])\n-- 800\n-- (0.03 secs, 42,055,128 bytes)\n-- \u03bb> length (clausura4 (\\x -> (x+1) `mod` 800) [0])\n-- 800\n-- (0.01 secs, 1,779,768 bytes)\n--\n-- \u03bb> length (clausura3 (\\x -> (x+1) `mod` (10^4)) [0])\n-- 10000\n-- (2.50 secs, 8,080,105,816 bytes)\n-- \u03bb> length (clausura4 (\\x -> (x+1) `mod` (10^4)) [0])\n-- 10000\n-- (0.05 secs, 27,186,920 bytes)\n<\/pre>\nEl c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\nLa elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n