Um @ RamonSnirs Antwort hinzuzufügen, kann die Funktion zum Gruppieren eines Datentyps durch Konstruktoren auch automatisch mit dem Framework "Scrap your bastplate" erstellt werden:
%Vor%Die zwei wichtigen Teile sind:
(Dies ist wahrscheinlich extrem Overkill, aber es war eine lustige Frage, um herumzubasteln!)
Die angegebenen Antworten leiden unter 3 leichten Problemen:
Ord ist (weil zum Beispiel irgendwo eine Funktion drin ist)? [X 2, X 1] [X 1, X 2] sein soll (das ist, was Sie bekommen, wenn Sie die sort -basierte verwenden Lösungen) oder sollten die Elemente in ihrer ursprünglichen Reihenfolge beibehalten werden? Also hier ist die allgemeinste Lösung, die ich mir vorstellen konnte. Es ist stabil, es braucht nicht Ord (in der Tat müssen Sie nicht einmal den ursprünglichen Datentyp berühren) und es läuft in etwa O (n * min (n, W)) Zeit wo W ist die Wortgröße von Ihre Maschine (bei mir ist es 64). Das heißt, es ist linear, sobald die Liste länger als 64 Elemente ist (ich sage 'ungefähr', weil die gruppierten Elemente noch aus den Differenzlisten rekonstituiert werden müssen).
und jetzt groupByConstructor vals gibt [[X 2, X 1],[Y True, Y False],[Z 2.7, Z 3.14, Z 0.2]] , wie ich denke, sollte es.
Es funktioniert nicht zum Sortieren von Listen von Int s, Char s, Float s oder nicht darstellbaren Typen wie Ptr und Array . Es könnte wahrscheinlich ein bisschen effizienter gemacht werden, indem man einen Algorithmus verwendet, der die Anzahl der möglichen Konstruktoren benutzt, um die lineare Konstante weiter nach unten zu schieben, aber IntMap wird vorerst tun müssen: -)
Tags und Links haskell types generic-programming