Immer wenn ich über Monad Beispiel lese, präsentieren sie immer IO als eine Fallstudie.
Gibt es Beispiele für Monaden, die Listenmanipulationen durchführen, die jemand präsentieren könnte? Ich denke, das könnte Overkill sein, aber ich bin interessiert, ob Monaden Vorteile gegenüber regulären Listenmanipulationstechniken bieten können.
Das große Geheimnis der Listen-Monade in Haskell ist, dass Listen-Comprehensions syntaktischer Zucker für do-Blöcke sind. Jedes Mal, wenn Sie ein Listenverständnis schreiben, könnten Sie es stattdessen mit einem Do-Block geschrieben haben, der die Listen-Monaden-Instanz verwendet.
Nehmen wir an, Sie möchten zwei Listen nehmen und ihr kartesisches Produkt zurückgeben (dh die Liste von (x,y) für jede Kombination von x aus der ersten Liste und y von der zweiten Liste).
Sie können das mit einem Listenverständnis tun:
%Vor%Das Listenverständnis ist syntaktischer Zucker für diesen Do-Block:
%Vor%was wiederum syntaktischer Zucker für
ist %Vor%Dieses Beispiel zeigt jedoch nicht wirklich die Macht von Monaden, weil Sie es einfach schreiben könnten, ohne sich auf die Tatsache zu verlassen, dass Listen eine Monad-Instanz haben. Wenn wir beispielsweise nur die Applicative-Instanz verwenden:
%Vor% Nehmen wir nun an, Sie nehmen jedes Element einer Liste positiver Ganzzahlen und replizieren es so oft wie es selbst ist (z. B. f [1,2,3] = [1,2,2,3,3,3] zum Beispiel). Wer weiß, warum Sie das tun wollen, aber es ist einfach:
Das ist nur syntaktischer Zucker dafür:
%Vor%was wiederum syntaktischer Zucker für
ist %Vor% Diesmal können nicht schreiben, dass wir nur die applikative Instanz verwenden. Der Hauptunterschied ist, dass wir die Ausgabe von der ersten Bindung ( x ) genommen haben und den Rest des Blocks davon abhängig gemacht haben ( y <- replicate x x ).
Ein klassisches Beispiel für die Verwendung der Listenmonade, um geschickt eine "einfache" Listenfunktion zu schreiben, ist dies:
%Vor% Der Typ von filterM ist Monad m => (a -> m Bool) -> [a] -> m [a] . Im Kontext der Listenmonade ist dies ein nichtdeterministischer Listenfilter : eine Filteroperation, die ein nichtdeterministisches Prädikat übernimmt, das eine Liste von Alternative zurückgibt Antworten. Das Ergebnis von filterM ist wiederum eine Liste möglicher alternativer Ergebnisse.
Oder in einfacher Sprache: filterM (\x -> [True, False]) bedeutet: Für jedes Element der Liste möchte ich beide behalten und wegwerfen. filterM ermittelt alle möglichen Kombinationen, um dies für jedes Listenelement zu tun.
Hier ist ein sehr dummer Weg, Paare von Divisoren für eine gegebene Ganzzahl zu finden:
%Vor%Die Bedeutung dieses Fragments sollte ziemlich geradlinig sein. Offensichtlich ist dies ein dummer Weg, um dieses spezifische Problem zu lösen. (In diesem Fall sind weitaus effizientere Methoden möglich.) Stellen Sie sich nun ein komplizierteres Problem vor, bei dem diese Suche sehr komplex ist. Diese Art von Idiom für die Suche kann sehr nützlich sein.
Ein schönes Beispiel für die Listenmanipulation ist die Abfrage eines HTML / XML-Dokuments, a la jQuery. jQuery ist eine Monade . Schauen wir uns ein Beispiel an:
%Vor% Dies gibt Ihnen die Überschriften aller Top-Level-Tabellen mit einer CSS-Klasse bar . Dies ist eine ungewöhnliche Art, jQuery zu verwenden (normalerweise würden Sie einfach body > table.bar > caption verwenden), aber das liegt daran, dass ich die Schritte anzeigen wollte.
In xml-conduit machst du das ähnlich:
Was die Listen-Monade macht, ist die Kombination der Schritte. Die Monade selbst weiß nichts über HTML / XML.
In HXT machst du das fast genauso. Neuere HXT Versionen verwenden sogenannte Pfeile anstelle von Monaden, aber das zugrundeliegende Prinzip ist dasselbe.
Ein anderes Beispiel ist die Konstruktion aller Teiler einer Zahl aus ihrer Primfaktorzerlegung (obwohl sie nicht in der richtigen Reihenfolge sind):
%Vor% Die Funktion f in mapM f == sequence . map f erzeugt für jeden Eintrag in der Eingabeliste eine Liste von Potenzen eines Faktors; dann bildet sequence alle Pfade durch die Listen und wählt jeweils eine Nummer aus; dann wird diese Liste aller möglichen Kombinationen map product zugeführt, die die Teiler berechnet:
Die großartige Beschreibung in Luis Casillas 'Antwort gilt auch hier:
Im Kontext der Listenmonade ist
mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]eine nichtdeterministische Listenzuordnung : eine Zuordnungsoperation, die eine nichtdeterministische Funktion abbildet - so dass eine Liste von < em> alternative Ergebnisse - über eine Liste, Erstellen aller alternativen möglichen Listen von Ergebnissen.
Die Manipulation von Monaden und Listen macht sogar noch mehr Spaß, wenn sie mit guard von MonadPlus und vielleicht noch eine Monade. Lassen Sie uns als Beispiel das klassische Wortarithmetik Rätsel lösen: SEND + MORE = MONEY . Jeder Buchstabe muss eine eindeutige Ziffer darstellen und die führenden Ziffern dürfen nicht Null sein.
Dafür konstruieren wir einen Monadenstapel aus StateT und [] :
Die Listen-Monaden erlauben uns, Berechnungen zu verzweigen, um alle möglichen Wege zu suchen, und der Zustand ist die Liste von Ziffern, die zur Auswahl verfügbar sind. Wir können diese Monade ausführen, indem wir ihnen alle möglichen Ziffern als:
geben %Vor%Wir brauchen eine Hilfsfunktion, die eine Berechnung abzweigt, indem sie alle verfügbaren Ziffern auswählt und den Zustand mit dem Rest aktualisiert:
%Vor%Auch müssen wir oft eine Ziffer ungleich Null auswählen:
%Vor% Das Lösen des Puzzles ist jetzt einfach: Wir können die Addition einfach Ziffer für Ziffer implementieren und überprüfen mit guard , dass die Ziffern des Ergebnisses gleich der Summe sind:
Das Puzzle hat genau ein Ergebnis: (9567,1085,10652) . (Natürlich kann der Code weiter optimiert werden, aber ich wollte, dass es einfach ist.)
Weitere Rätsel finden Sie hier: Ссылка .