Elementos óptimos
Definir la función
|
1 |
optimos :: Eq b => (b -> b -> Bool) -> (a -> b) -> [a] -> [a] |
tal que (optimos r f xs) es la lista de los elementos de xs donde la función f alcanza sus valores óptimos respecto de la relación r. Por ejemplo,
|
1 2 |
optimos (<) length ["ab","c","de","f"] == ["c","f"] optimos (>) length ["ab","c","de","f"] == ["ab","de"] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
-- 1ª definición -- ============= optimos1 :: Eq a => (b -> b -> Bool) -> (a -> b) -> [a] -> [a] optimos1 r f xs = [x | x <- xs, null [y | y <- xs, x /= y, r (f y) (f x)]] -- 2ª definición -- ============= optimos2 :: Eq b => (b -> b -> Bool) -> (a -> b) -> [a] -> [a] optimos2 r f xs = [x | x <- xs, f x `elem` ms] where ms = maximales r (map f xs) -- (maximales r xs) es la lista de los elementos de xs para los que no -- hay ningún otro elemento de xs mayor según la relación r. Por -- ejemplo, -- maximales (>) [2,3,4,6] == [6] -- maximales (<) [2,3,4,6] == [2] -- maximales (\x y -> mod x y == 0) [2,3,4,6] == [4,6] -- maximales (\x y -> mod y x == 0) [2,3,4,6] == [2,3] maximales :: Eq a => (a -> a -> Bool) -> [a] -> [a] maximales r xs = [x | x <- xs, null [y | y <- xs, y /= x, r y x]] -- Comparación de eficiencia -- ========================= -- λ> length $ optimos1 (>) length [replicate n 'a' | n <- [1..1000]] -- 1 -- (16.74 secs, 153,957,400 bytes) -- λ> length $ optimos2 (>) length [replicate n 'a' | n <- [1..1000]] -- 1 -- (0.64 secs, 85,520,896 bytes) |