En Haskell, ¿cómo puedo usar la función incorporada de sortBy para ordenar una lista de pares (tupla)?

Question

Soy un principiante en Haskell así que por favor tengan paciencia conmigo. (¡Empecé a aprender ayer!) ¿Cómo puedo ordenar una lista de tuplas principalmente por sus primeros componentes (de mayor a menor) y secundariamente por sus segundos componentes (del más pequeño al más alto)? Un ejemplo de entrada/salida sería:

[(1, "b"), (1, "a"), (2, "b"), (2, "a")] (de entrada)

[(1, "a"), (2, "a"), (1, "b"), (2, "b")] (paso intermedio)

[(2, "a"), (2, "b"), (1, "a"), (1, "b")] (salida)

He intentado utilizar el siguiente pero dio la salida equivocada:

sortGT a b = GT 

sortBy sortGT lst 

Estoy seguro de que puedo hacer esto usando sortBy solamente, pero no puedo entenderlo yo mismo. ¡Cualquier ayuda sería muy apreciada!

Answer 1

Es necesario para construir su función sortGT, por lo que se compara pares de la forma que desee:

sortGT (a1, b1) (a2, b2) 
    | a1 < a2 = GT 
    | a1 > a2 = LT 
    | a1 == a2 = compare b1 b2 

El uso de este se obtiene los siguientes resultados (utilicé ghci):

*Main Data.List> sortBy sortGT [(1, "b"), (1, "a"), (2, "b"), (2, "a")] 
[(2,"a"),(2,"b"),(1,"a"),(1,"b")] 

Answer 2

Siempre es complicado componer funciones de dos argumentos. Aquí es una implementación:

invert :: Ordering -> Ordering 
invert GT = LT 
invert LT = GT 
invert EQ = EQ 


sosort :: (Ord a, Ord b) => [(a, b)] -> [(a, b)] 
sosort = sortBy (\p p' -> invert $ uncurry compare $ double fst p p') . 
     sortBy (\p p' ->   uncurry compare $ double snd p p') 
    where double f a a' = (f a, f a') 

Debido sortBy espera una función de dos argumentos, la composición de funciones no es tan agradable.

He probado este código, y funciona en su ejemplo.

Como señala Fred, puede escribir compare EQ en lugar de invert. Como señala Dario, podría estar usando on de Data.Function, pero de hecho on compare == comparing, que puedo usar en su lugar. Ahora, el código puede ser leído por un Maestro Haskell:

sosort :: (Ord a, Ord b) => [(a, b)] -> [(a, b)] 
sosort = sortBy (compare EQ `post` comparing fst) . sortBy (comparing snd) 
    where post f g x x' = f (g x x') 

he recopilado y ejecutar el código y funciona en el ejemplo inicial.

(no he recibido ningún voto para esta respuesta, pero gracias a los buenos comentarios, estoy seguro que he aprendido mucho acerca de la biblioteca de Haskell. Quién sabe qué función post es equivalente a? No Hoogle ...)

Sería más idiomático escribir una función de comparación adecuada para los pares, pero su pregunta era para tipos consecutivos.

Answer 3

¿Puedo sugerir lo siguiente?

import Data.List (sortBy) 
import Data.Monoid (mconcat) 

myPredicate (a1, a2) (b1, b2) = mconcat [compare b1 a1, compare a2 b2] 

A continuación, puede ordenar por escrito sortBy myPredicate lst. La función mconcat simplemente escanea la lista y obtiene la primera aparición no EQ (o EQ si todos los elementos son EQ y, por lo tanto, ambos pares se consideran iguales).

Pensándolo bien, la construcción de la lista no es necesaria.

import Data.List (sortBy) 
import Data.Monoid (mappend) 

myPredicate (a1, a2) (b1, b2) = compare b1 a1 `mappend` compare a2 b2 

La definición de mappend para Ordering es esencialmente:

EQ `mappend` x = x 
x `mappend` _ = x 

que es exactamente lo que necesitamos.

Sólo por diversión, la generalización de la respuesta de gbacon y haciendo que el uso de un poco más flexible:

import Data.Ord 
import Data.List 
import Data.Monoid 

ascending = id 
descending = flip 

sortPairs f x g y = f (comparing x) `mappend` g (comparing y) 

mySort = sortBy (sortPairs descending fst ascending snd) 

Answer 4

Felicitaciones por dar sus primeros pasos para aprender Haskell. ¡Es un gran viaje!

Riffing en FredOverflow's answer:

import Data.Ord 
import Data.List 
import Data.Monoid 

main :: IO() 
main = do 
    print $ sortBy cmp [(1, "b"), (1, "a"), (2, "b"), (2, "a")] 
    where 
    cmp = flip (comparing fst) `mappend` comparing snd 

Salida:

[(2,"a"),(2,"b"),(1,"a"),(1,"b")]

Answer 5

En primer lugar debemos hacer que el wich función ordenadora toma dos touples y devuelve o EQ, LT o GT continuación (es decir sortGT :: (a,b) -> (a,b) -> Ordering.). podemos dar esta función de ordenamiento al sortBy y clasificará su entrada de acuerdo con este orden.

Como quiera que los primeros componentes tengan prioridad, comprobamos que primero y si son iguales comprobamos el segundo argumento, si los primeros componentes no son iguales le damos el valor opuesto de su orden original, de modo que está ordenado de mayor a menor.

Esto es lo que creo que es más fácil en los ojos:

sortGT (a1,b1) (a2,b2) = 
    case compare a1 a2 of 
    EQ -> compare b1 b2 
    LT -> GT 
    GT -> LT 

Ahora usamos sortBy como usted sugiere:

*Main> sortBy sortGT [(1, "b"), (1, "a"), (2, "b"), (2, "a")] 
[(2,"a"),(2,"b"),(1,"a"),(1,"b")] 

Answer 6

La siguiente solución funciona mejor para mí, un novato Haskell. Se parece mucho a 3lectrologos 'respuesta: en realidad solo agregué la definición de la función y la importación de la lista, pero puede causar cierta confusión si se omite.

Cree una función 'myCompare' y no olvide importar el módulo de Lista. Lo necesitarás para hacer que el orden funcione. La función debe tener este aspecto:

import Data.List 

myCompare :: (Ord a, Ord b) => (a,b) -> (a,b) -> Ordering 
myCompare (a1,b1) (a2,b2) 
    | a1 < a2  = GT 
    | a2 == a1 = EQ 
    | otherwise = LT 

Después de cargar el archivo de Haskell, puede escribir lo siguiente en su terminal:

*Main> sortBy myCompare [(1, "b"), (1, "a"), (2, "b"), (2, "a")] 

que devolverá:

[(2,"a"),(2,"b"),(1,"a"),(1,"b")] 

Answer 7

me gusta el comparando la función en Data.Ord. Esto es básicamente la respuesta de Greg en forma aún más compacta:

Prelude Data.Ord Data.List Data.Function> (reverse.sortBy (comparing fst)) [(1, "b"), (1, "a"), (2, "b"), (2, "a")] 

[(2, "a"), (2, "b"), (1, "a"), (1, "b") ]

"comparando fst" da un orden basado en el primer elemento de la tupla.