Kurz gesagt: Wie würden Sie Elemente eines Map oder Set auf einer Monade filtern?
Prädikat in Haskell?
Ich könnte mir zwei Möglichkeiten vorstellen:
a) Round-Trip durch eine Liste und filterM (wahrscheinlich nicht sehr effizient):
b) Wenn das Prädikat nicht von Natur aus monadisch ist, sondern z.B. ist ein Vergleich zu den
Zustand in State monad; dann können wir Data.Map.filter verwenden (ziemlich speziell
Fall):
Gibt es einen besseren Weg, dies zu tun?
Hier ist ein kleines Beispielprogramm zur Demonstration.
%Vor% Update : Ich habe einen Benchmark zwischen verschiedenen Implementierungen von filterMapM erstellt. Es stellt sich heraus, dass die Rundreise durch eine Liste eigentlich ziemlich gut ist. Überraschenderweise war es sogar noch besser als ein Umsetzungsrecht auf die interne Struktur von Map . Der Code und die Daten sind hier verfügbar.
Die beiden Ansätze haben unterschiedliche Semantiken und Implikationen für die Effizienz.
Wenn Sie eine Liste durchlaufen, können Sie die Filterung durch alle vorherigen Vergleiche beeinflussen, so dass das Endergebnis von der Reihenfolge beeinflusst werden kann, in der die Elemente besucht werden. Im zweiten Fall ist die Filterung jedoch eine reine Funktion, so dass die Antwort dieselbe ist, egal in welcher Reihenfolge die Vergleiche gemacht werden.
Zum Beispiel könnte der Benutzer, der die Fragen beantwortet, die Anzahl der geraden und ungeraden Zahlen ungefähr gleich halten, und somit hängt die Frage, ob der Benutzer eine bestimmte Zahl mag, von allen Zahlen ab, die zuvor präsentiert wurden. p>
Auf der anderen Seite ist hier der Code für M.filter :
Wichtig ist, dass die Form des Codes - die resultierende Baumstruktur - stark von der Struktur des ursprünglichen Baumes beeinflusst wird. Vielleicht wird nur ein kleiner Ausgleich benötigt. Dies könnte viel effizienter sein, als den Baum aus Null Wissen mit M.fromList wiederherzustellen.
Das Ergebnis ist, dass Sie sich in dem Fall filterM1 Gedanken über die Reihenfolge machen sollten, in der die Vergleiche gemacht werden. Vielleicht gibt M.toList eine akzeptable Reihenfolge, oder vielleicht möchten Sie reverse . M.toList , oder ...
Im zweiten Fall müssen Sie sich nicht darum kümmern, also können Sie M.filter die gesamte Arbeit erledigen lassen und die Kenntnisse über die Datenstruktur nutzen.
Update: Ich habe gerade die Funktionen M.toAscList und M.fromAscList bemerkt, also ist diese Version von filterMapM1 vielleicht etwas effizienter:
Momentan glaube ich nicht, dass es eine allgemeinere Abstraktion gibt, die filterM direkt unterstützt. Traversable nicht, weil traverse die Form der Struktur nicht ändern kann. Ich denke, dass es technisch möglich ist, dies mit Objektiv zu tun, aber die Dokumentation schlägt vor, dass Sie das wirklich nicht tun sollten und ich denke, dass es sowieso durch eine andere Struktur rockt.
Sie könnten so etwas verwenden (nicht kompilierbar, weil filter kein Klassenmitglied ist):
Ob dies mehr oder weniger effizient ist als das Runden durch eine Liste, hängt wahrscheinlich von der Struktur ab. Es ist wohl weniger sauber.
Tags und Links haskell