Dies ist der Pseudocode für die Radix-Sortierung:
%Vor%Dies ist der Scala-Code für die Radix-Sortierung:
%Vor%Dies ist der Haskell-Code für die Radix-Sortierung:
%Vor%Meine Frage ist: Können Sie für die Radix-Sortierung ein Monoid oder eine Halbgruppe formulieren?
Die Radix-Sortierinvariante lautet, dass die Daten mit den ersten k Bits sortiert werden. Wenn Sie eine Operation wünschen, die mehr Daten sortiert oder nicht enthält, fragen Sie nach der Mergesort-Funktionalität, nicht nach Radix. Wenn Sie Daten zu allen Datensätzen hinzufügen, können Sie ein Monoid verwenden.
Edit: Das Hart eines Monoid ist eine assoziative Operation. Wir können uns die Sortierbits ansehen, um eine partielle Ordnung anzuwenden. Sie schreiben die Daten für alle Datensätze Stück für Stück. Jedes Bit wendet eine teilweise Reihenfolge an. Dies ist assoziativ. Sie können einige Bits zusammenführen, um eine ausführlichere Teilaufordnung zu erhalten. Die Reihenfolge der Noten ist wichtig, aber sie ist immer noch assoziativ und kann daher als Monade betrachtet werden.
Ich denke, Sie denken vielleicht zu wörtlich über die Idee von Radix-Sort. Abstrakt stelle ich mir vor, das Monoid, das Sie wollen, ist
Die große Frage ist, wie Sie die sortierten Listen darstellen wollen. Wenn Sie sie als sortierte Haskell-Listen darstellen, ist die Zusammenführungsoperation die übliche Stück-für-Stück-Zusammenführung, die bei der Zusammenführungssortierung verwendet wird. Wenn Sie sie auf eine radikalere Art repräsentieren, dann haben Sie eine Auswahl von trie . Sie können wahrscheinlich einige Algorithmen zum Zusammenführen von Versuchen finden. Es gibt eine in bytestring-trie , aber nichts über die Implementierung scheint dokumentiert zu sein.