Ordenación según una función
Definir la función
|
1 |
ordenaSegun :: Ord b => (a -> b) -> [a] -> [a] |
tal que (ordenaSegun f xs) es la lista obtenida ordenando los elementos de xs según sus valores mediante la función f. Por ejemplo,
|
1 2 3 4 |
ordenaSegun abs [-3,2,5,-2] == [2,-2,-3,5] ordenaSegun abs [-3,-2,5,2] == [-2,2,-3,5] ordenaSegun length ["pq","x","mn"] == ["x","pq","mn"] [g 0 | g <- ordenaSegun (\f -> f 4) [(+5),(+2),(+3)]] == [2,3,5] |
Comprobar con QuickCheck que (ordenaSegun id) es equivalente a sort.
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 34 35 36 37 38 39 40 41 42 |
import Data.List (sort, sortBy) import Data.Ord (comparing) import Test.QuickCheck -- 1ª definición -- ============= ordenaSegun :: Ord b => (a -> b) -> [a] -> [a] ordenaSegun _ [] = [] ordenaSegun f (x:xs) = insertaSegun f x (ordenaSegun f xs) insertaSegun :: Ord b => (a -> b) -> a -> [a] -> [a] insertaSegun _ x [] = [x] insertaSegun f x (y:ys) | f x <= f y = x : y : ys | otherwise = y : insertaSegun f x ys -- 2ª definición -- ============= ordenaSegun2 :: Ord b => (a -> b) -> [a] -> [a] ordenaSegun2 f xs = [xs!!i | (_,i) <- sort (zip [f x | x <- xs] [0..])] -- 3ª definición -- ============= ordenaSegun3 :: Ord b => (a -> b) -> [a] -> [a] ordenaSegun3 f xs = map ((xs!!) . snd) (sort (zip (map f xs) [0..])) -- 4ª definición -- ============= ordenaSegun4 :: Ord b => (a -> b) -> [a] -> [a] ordenaSegun4 = sortBy . comparing -- La propiedad es prop_ordenaSegun :: Ord a => [a] -> Bool prop_ordenaSegun xs = ordenaSegun id xs == sort xs -- La comprobación es -- ghci> quickCheck prop_ordenaSegun -- +++ OK, passed 100 tests. |