Ich bin völlig neu bei Haskell, also entschuldige mich, wenn die Frage albern ist.
Ich möchte rekursiv eine Liste erstellen, während gleichzeitig einen auf den rekursiven Aufrufen basierenden akkumulierten Wert aufbaut. Dies ist für ein Problem, das ich für einen Coursera-Kurs mache, also werde ich nicht das genaue Problem, sondern etwas Analoges posten.
Sagen wir zum Beispiel, ich wollte eine Liste von Ints nehmen und jede einzelne verdoppeln (ich ignoriere für den Zweck des Beispiels, dass ich einfach map verwenden könnte), aber ich auch wollte mitzählen Wie oft erscheint die Nummer "5" in der Liste.
Um die Verdoppelung zu machen, könnte ich das tun:
%Vor% So weit so einfach. Aber wie kann ich auch angeben, wie oft x eine Fünf ist? Die beste Lösung, die ich habe, ist, einen expliziten Akkumulator wie diesen zu verwenden, den ich nicht mag, da er die Liste umkehrt, also müssen Sie am Ende eine Umkehrung durchführen:
Aber ich denke, das sollte besser mit der State monad behandelt werden, die ich vorher noch nicht benutzt habe, aber wenn ich versuche, eine Funktion zu erstellen, die zu dem Muster passt, das ich gesehen habe, bleibe ich stecken wegen des rekursiven Aufrufs von foo . Gibt es einen schöneren Weg, dies zu tun?
EDIT: Ich brauche das für sehr lange Listen, also müssen rekursive Aufrufe auch tail-rekursiv sein. (Das Beispiel, das ich hier habe, schafft es dank Haskells "Schwanzrekursion modulo contras", rekursiv zu werden.)
Dies ist eine einfache Falte
%Vor% oder ausgedrückt mit foldr
Der akkumulierte Wert ist ein Paar beider Operationen.
Hinweise:
Sie können State auch für die gleiche Sache verwenden, indem Sie jedes Element als statusbehaftete Berechnung betrachten. Das ist ein bisschen zu viel, aber sicher möglich. Tatsächlich kann jede Faltung als eine Folge von State Berechnungen ausgedrückt werden:
Funktion mapM_ bildet zuerst jedes Element von xs auf eine statusbehaftete Berechnung von modify . f :: b -> State a () ab. Dann kombiniert es eine Liste solcher Berechnungen in eine vom Typ State a () (es verwirft die Ergebnisse der monadischen Berechnungen, behält nur die Effekte bei). Schließlich führen wir diese Stateful Berechnung auf z aus.
Tags und Links haskell recursion state-monad accumulator