In Haskell, wie kann ich die integrierte Funktion sortBy verwenden, um eine Liste von Paaren (Tupel) zu sortieren?

Question

Ich bin ein Anfänger in Haskell also bitte bitte mit mir. (Habe erst gestern angefangen zu lernen!) Wie kann ich eine Liste von Tupeln in erster Linie nach ihren ersten Komponenten sortieren (am höchsten zum kleinsten) und zweitens nach ihren zweiten Komponenten (am kleinsten zum höchsten)? Eine Probe Eingabe/Ausgabe wäre:

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

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

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

Ich habe versucht, mit dem folgenden, aber es gibt falsche Ausgabe:

sortGT a b = GT 

sortBy sortGT lst 

Ich bin mir sicher, dass ich dies nur mit sortBy tun kann, aber ich kann nicht ich tu mich selbst aus. Jede Hilfe würde sehr geschätzt werden!

Answer 1

Sie benötigen eine Funktion sortGT, so zu konstruieren, dass es Paare, die Art und Weise vergleicht wollen Sie es:

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

diese Verwendung Sie erhalten die folgenden Ergebnisse (I verwendet GHCI):

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

Answer 2

Es ist immer schwierig, zwei Argumente zu komponieren. Hier ist eine Implementierung:

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') 

Da sortBy eine Funktion von zwei Argumenten erwartet, Funktions Zusammensetzung nicht so schön ist.

Ich habe diesen Code getestet, und es funktioniert in Ihrem Beispiel.

Wie Fred darauf hinweist, können Sie compare EQ anstelle von invert schreiben. Wie Dario darauf hinweist, könnte ich on von Data.Function verwenden, aber tatsächlich , die ich stattdessen verwenden kann. Nun kann der Code nur von einem Haskell Meister gelesen werden:

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') 

ich zusammengestellt haben und diesen Code ausführen und es funktioniert auf dem ursprünglichen Beispiel.

(I haben keine Stimmen um für diese Antwort, aber dank der guten Kommentare, ich habe sicher viel über die Haskell-Bibliothek gelernt. Wer weiß, welche Funktion post entspricht? Nicht Hoogle ...)

Es wäre mehr idiomatisch, eine geeignete Vergleichsfunktion für Paare zu schreiben, aber Ihre Frage für aufeinanderfolgende Sortierungen gefragt.

Answer 3

Darf ich Folgendes vorschlagen?

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

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

Sie können dann sortieren, indem Sie sortBy myPredicate lst schreiben. Die Funktion mconcat scannt einfach durch die Liste und erhält das erste EQ Vorkommen (oder EQ Vorkommen, wenn alle Elemente EQ sind und somit beide Paare als gleich angesehen werden).

Auf den zweiten Gedanken, ist das Erstellen der Liste nicht notwendig.

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

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

Die Definition von mappend für Ordering ist im Wesentlichen:

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

das ist genau das, was wir brauchen.

Just for fun, gbacon Antwort zu verallgemeinern und macht den Einsatz ein wenig flexibler:

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

Herzlichen Glückwunsch zum ersten Schritte Haskell zu lernen. Es ist eine großartige Reise!

Riffing auf 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 

Ausgang:

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

Answer 5

Zuerst sollten wir die Bestellfunktion Wich nimmt zwei touples und kehrt entweder EQ, LT oder GT machen Dann (dh sortGT :: (a,b) -> (a,b) -> Ordering..) Wir können diese Ordnungsfunktion sortBy geben, und es wird seine Eingabe entsprechend dieser Reihenfolge sortieren.

Da Sie möchten, dass die ersten Komponenten die erste Priorität haben, überprüfen wir zuerst und wenn sie gleich sind, überprüfen wir das zweite Argument, wenn die ersten Komponenten nicht gleich sind, geben wir ihm den entgegengesetzten Wert seiner ursprünglichen Reihenfolge es ist von oben nach unten geordnet. Diese

ist, was ich denke, ist am einfachsten auf die Augen:

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

Jetzt verwenden wir sortBy wie Sie vorgeschlagen:

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

Answer 6

Die folgende Lösung funktioniert am besten für mich, ein Haskell-Neuling. Es sieht viel wie 3lectrologos 'Antwort aus: Ich habe nur die Funktionsdefinition und den List-Import hinzugefügt, aber es kann etwas Verwirrung verursachen, wenn es weggelassen wird.

Erstellen Sie eine Funktion 'myCompare' und vergessen Sie nicht, das List-Modul zu importieren. Du brauchst es, damit sortBy funktioniert. Die Funktion sollte wie folgt aussehen:

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 

Nach der Haskell-Datei geladen wird, können Sie die folgenden in Ihrem Terminal schreiben:

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

Welche zurück:

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

Answer 7

ich mag Vergleichsfunktion in Data.Ord. Dies ist im Grunde Gregs Antwort in noch kompakterer Form:

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") ]

"comparing fst" gibt eine Reihenfolge basierend auf dem ersten Element des Tupels.