Menu Close

Ordenación según una función

José A. Alonso,

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.
Medio
, , , , , , , , , ,

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

  1. Responder
    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
    • Responder
      jneira

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

      ordenaSegun = sortBy . comparing
  2. Responder
    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. Responder
    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.