Definir la funci\u00f3n<\/p>\n
\n minimales :: Ord a => [[a]] -> [[a]]\n<\/pre>\ntal que (minimales xss) es la lista de los elementos de xss que no est\u00e1n contenidos en otros elementos de xss. Por ejemplo,<\/p>\n
\n minimales [[1,3],[2,3,1],[3,2,5]] == [[2,3,1],[3,2,5]]\n minimales [[1,3],[2,3,1],[3,2,5],[3,1]] == [[2,3,1],[3,2,5]]\n map sum (minimales [[1..n] | n <- [1..300]]) == [45150]\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.List (delete, nub)\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nminimales :: Ord a => [[a]] -> [[a]]\nminimales xss =\n [xs | xs <- xss,\n null [ys | ys <- xss, subconjuntoPropio xs ys]]\n\n-- (subconjuntoPropio xs ys) se verifica si xs es un subconjunto propio\n-- de ys. Por ejemplo,\n-- subconjuntoPropio [1,3] [3,1,3] == False\n-- subconjuntoPropio [1,3,1] [3,1,2] == True\nsubconjuntoPropio :: Ord a => [a] -> [a] -> Bool\nsubconjuntoPropio xs ys = aux (nub xs) (nub ys)\n where\n aux _ [] = False\n aux [] _ = True\n aux (u:us) vs = u `elem` vs && aux us (delete u vs)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nminimales2 :: Ord a => [[a]] -> [[a]]\nminimales2 xss =\n [xs | xs <- xss,\n null [ys | ys <- xss, subconjuntoPropio2 xs ys]]\n\nsubconjuntoPropio2 :: Ord a => [a] -> [a] -> Bool\nsubconjuntoPropio2 xs ys =\n subconjunto xs ys && not (subconjunto ys xs)\n\n-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. Por\n-- ejemplo,\n-- subconjunto [1,3] [3,1,3] == True\n-- subconjunto [1,3,1,3] [3,1,3] == True\n-- subconjunto [1,3,2,3] [3,1,3] == False\n-- subconjunto [1,3,1,3] [3,1,3,2] == True\nsubconjunto :: Ord a => [a] -> [a] -> Bool\nsubconjunto xs ys =\n all (`elem` ys) xs\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_minimales :: [[Int]] -> Bool\nprop_minimales xss =\n minimales xss == minimales2 xss\n\nverifica_minimales :: IO ()\nverifica_minimales =\n quickCheck prop_minimales\n\n-- La comprobaci\u00f3n es\n-- \u03bb> verifica_minimales\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> length (minimales [[1..n] | n <- [1..200]])\n-- 1\n-- (2.30 secs, 657,839,560 bytes)\n-- \u03bb> length (minimales2 [[1..n] | n <- [1..200]])\n-- 1\n-- (0.84 secs, 101,962,480 bytes)\n<\/pre>\n