Ich lerne Haskell Book , und in Kapitel 10 (Folding Lists) versuche ich eine Übung zu lösen, die sich darauf bezieht, nur eins zu bekommen bestimmter Elementtyp aus einer Liste, die verschiedene Arten von Elementen enthält.
Die Autoren geben folgenden Code:
%Vor%und die erste Frage ist:
%Vor%Schreiben Sie eine Funktion, die nach DbDate-Werten filtert und eine Liste von die UTCTime-Werte in ihnen.
Da es im Kapitel nur um das Falten von Listen geht, gehe ich davon aus, dass dies beispielsweise mit foldr geschehen kann.
Mein erster Versuch war, zuerst einige Hilfsfunktionen zu schreiben und sie in foldr zu verwenden, wie zum Beispiel:
Dies scheint die Aufgabe zu erfüllen, denn:
%Vor%Aber ich fühle mich nicht wohl mit dieser Lösung, denn vor allem gibt es folgende Warnung:
%Vor% Und ich benutze zwei Hilfsfunktionen, eine zum Ausfiltern der Werte, die nicht DbDate sind, eine andere, um an die UTCTime -Komponente zu kommen.
Um die nicht erschöpfende Warnung zum Mustervergleich loszuwerden und eine einzige Hilfsfunktion zu verwenden, habe ich beschlossen, es wie folgt zu schreiben:
%Vor%Aber das obige kompiliert natürlich nicht, weil es keine Überprüfung eingibt, zum Beispiel:
%Vor% Mit anderen Worten, es kann eine Liste von Just UTCTime -Werten zusammen mit Nothing -Werten und nicht nur eine Liste von UTCTime -Werten zurückgegeben werden.
Meine Frage ist also: Wie kann ich eine (Helfer?) Funktion schreiben, die auf einen Schlag (damit ich filter nicht benutzen muss) prüft, ob ihr Wert DbNumber ist, und wenn Gibt also die UTCTime -Komponente zurück? (Und wenn nicht ... muss es auch etwas zurückgeben (zB Nothing ?), Und hier habe ich Probleme, das heißt Maybe UTCTime , und dann Just UTCTime Werte usw.)
Es gibt mehrere andere Antworten, die gute Vorschläge zu anderen Möglichkeiten zum Nachdenken über das Problem enthalten: Verwenden von catMaybes , um die Daten ein zweites Mal zu verschieben, nachdem Sie Maybe UTCTime s ausgewählt haben; Verwenden von Listenkompromittierungen und der praktischen Syntax, die sie zum Herausfiltern von nicht passenden Mustern haben; Verwenden der monadischen Struktur von Listen zum Einschließen oder Überspringen von Ergebnissen; und schreibe eine maßgeschneiderte rekursive Funktion. In dieser Antwort werde ich auf Ihre direkte Frage eingehen und zeigen, wie Sie die bereits vorhandene Programmstruktur verwenden, ohne Ihre Herangehensweise an Listenmanipulationen völlig neu zu überdenken. Rufen Sie foldr mit einer Hilfsfunktion auf, die alles auf einmal erledigt.
Zunächst beobachte ich, dass all Ihre bestehenden Versuche foldr eine Funktion senden, die bedingungslos (:) aufruft:
Die Sache mit diesem Muster ist, dass dies bedeutet, dass die Liste, die Sie aus foldr erhalten, dieselbe Länge wie die übergebene Funktion hat, da jedes (:) in der Eingabeliste in ein% co_de umgewandelt wird % in der Ausgabeliste. In Ihrer ersten Lösung haben Sie dies erledigt, indem Sie einige Einträge aus der Eingabeliste entfernt haben, die Ihnen nicht wichtig waren. In Ihrer zweiten Lösung haben Sie dies mit zusätzlichen uninteressanten Elementen in Ihrer Ausgabeliste behandelt.
Eine dritte Lösung besteht darin, das Listenelement zu betrachten, bevor entschieden wird, ob (:) aufgerufen werden soll oder nicht. So könnte man das machen:
Beachten Sie insbesondere, dass wir in der zweiten Klausel nicht (:) aufrufen - dies filtert die nicht übereinstimmenden Elemente der Liste heraus. Wir haben auch keine Sorge über fehlende Muster. Jetzt können wir schreiben
Testen in ghci:
%Vor%Perfekt!
Es gibt einige gute Antworten, aber ich möchte einen weiteren Ansatz hinzufügen, wie Sie Lösungen für solche Aufgaben finden können.
Schreiben Sie zuerst die einfachste mögliche Lösung , d. h. eine Lösung mit direkter Rekursion.
%Vor%Dies hilft, die beteiligten Strukturen zu verstehen und ermöglicht es Ihnen, sich mit den tatsächlich erforderlichen Schritten vertraut zu machen. Es ist nicht die performanteste Version, aber es ist einfach zu schreiben und es reicht oft für die Aufgabe.
Der nächste Schritt wäre, den Code mit der Tail-Rekursion leistungsfähiger zu machen. Es ist eine einfache, fast mechanische Transformation.
Bestimmen Sie den Akkumulatortyp. Dies ist oft auch der Rückgabetyp; In diesem Fall eine Liste. Das gibt dir die neuen ersten Zeilen
%Vor% Nimm nun die ursprüngliche Funktion und verwandle sie in die interne Funktion go , indem du jeden rekursiven Aufruf durch den Akkumulator ersetzt und dann das Ergebnis in einen rekursiven Aufruf von go setzt.
Fügen Sie die Handhabung des Endfalls hinzu. Achten Sie darauf, dass die Reihenfolge der Vorgänge umgekehrt wird.
%Vor%Verschieben Sie die Behandlung des Endfalls in den ursprünglichen Anruf. Dies ist nicht notwendig, wenn Sie hier aufhören wollen, aber es hilft auf dem Weg zu einer Falte.
%Vor%Nun zu verwandle das in eine Falte . Der Akkumulator ist der gleiche, den die Falte benutzen wird und die Transformation ist wiederum fast mechanisch.
Ersetzen Sie den Aufruf von go durch einen Aufruf an eine Falte.
Schalten Sie go in f um, indem Sie den Listen-Teil des Pattern-Matches, den End-Case und die rekursiven Aufrufe entfernen.
Überlege, ob es besser wäre, die Richtung der Rekursion umzukehren.
%Vor%Jetzt für die endgültige Säuberung, extra brownie Punkte und um Haskell-Lehrer zu verärgern, machen es so allgemein wie möglich, ohne etwas zu kaputt zu machen.
%Vor% Liste ist eine Monade. Also können wir die Funktionen der Monad type-Klasse verwenden.
Die Funktion (>>=) ist hier der Schlüssel. Es ist im Wesentlichen das gleiche wie "FlatMap" in anderen Sprachen, wenn das eine Glocke klingelt.
Das Folgende ist das gleiche wie das oben in der Do-Notation ausgedrückte:
%Vor% Tatsächlich können wir dies sogar zu einer Funktion verallgemeinern, die für jede Monade über UTCTime (naja, MonadPlus , wirklich) funktioniert:
Ein einfacher Weg dies zu tun ist wie folgt
%Vor% Das heißt, Sie übergeben ein weiteres Argument, das die Werte enthält, die Sie behalten möchten. Wenn du genau hinsiehst, siehst du, dass dies genau der Typ von foldl ist, der auf foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b verweist (Du kannst es auch mit foldr machen, aber ich überlasse dir das), außer es erwartet einen Element zu einer Zeit. Lassen Sie uns also filterDbDate' erneut schreiben.
Dies ist nicht die effizienteste Funktion, aber hoffentlich sehen Sie, wie Sie Funktionen zur Verwendung von Falten übersetzen. Probieren Sie es mit foldr !
Tags und Links haskell