Menu Close

Ordenación según una función

Definir la función

   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,

   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

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.

4 soluciones de “Ordenación según una función

  1. Diego
    import Data.List (sort, sortBy)
    import Test.QuickCheck (quickCheck)
     
    ordenaSegun :: Ord b => (a -> b) -> [a] -> [a]
    ordenaSegun f = sortBy (x y -> compare (f x) (f y))
     
    -- Sin sortBy
    ordenaSegun2 :: Ord b => (a -> b) -> [a] -> [a]
    ordenaSegun2 f xs = map ((xs!!) . snd) (sort (zip (map f xs) [0..]))
     
    prop_ordenaSegun :: Ord a => [a] -> Bool
    prop_ordenaSegun xs = ordenaSegun id xs == sort xs
    • jneira

      Data.Ord.comparing es justo la funcion usada en el primero que quedaria simplemente

      ordenaSegun = sortBy . comparing
  2. M Miranda
    -- Sin usar sort 
     
    ordenaSegun f xs = [xs !! (x-1) | x <- segundoElemento f xs]
     
    segundoElemento f xs = [y | (x,y) <- ordenaFuncionAplicada f xs]
     
    ordenaFuncionAplicada f xs = 
        ordena [(x,y) | (x,y) <- zip (aplicaFuncion f xs) [1..]]
     
    aplicaFuncion f xs = [f x| x <- xs]
     
    ordena [] = []
    ordena (x:xs) = (ordena (menores x xs)) ++ [x] ++ (ordena (mayores x xs))
     
    mayores x xs = [y |y <- xs, y > x]
     
    menores x xs = [y | y <- xs, y < x]
     
    prop_ordenaSegun xs = ordenaSegun id xs == sort xs
  3. Rafael González

    ordenaSegun :: Ord b => (a -> b) -> [a] -> [a]
    ordenaSegun f xs = [x | (x,y) <- ordenaPares (zip xs (map f xs))]
    
    ordenaPares []     = []
    ordenaPares (x:xs) = 
        (ordenaPares (menores x xs)) ++ [x] ++ (ordenaPares (mayores x xs))
    
    mayores x xs = [y | y <- xs, snd y >= snd x]
    
    menores x xs = [y | y <- xs, snd y <  snd x]
    
    prop_ordenaSegun :: Ord a => [a] -> Bool
    prop_ordenaSegun xs = sort xs == ordenaSegun id xs
    

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.