Ich habe Levenshtein Distance in einer ziemlich normalen Weise in F # als Übung implementiert.
%Vor%Ich sehe jedoch keine direkte Möglichkeit, den Aufruf von List.min so zu konvertieren, dass er rekursiv ist. Wir machen nicht einfach einige zusätzliche, unabhängige Berechnungen nach dem rekursiven Aufruf; Stattdessen wählen wir das Ergebnis mehrerer rekursiver Aufrufe.
Gibt es eine Möglichkeit, dies elegant zu konvertieren, um rekursiv zu sein?
(Ich kann das +1 einfach so umwandeln, dass es rekursiv ist)
Wenn Sie Code in ein tail-rekursives Formular umwandeln möchten, haben Sie im Allgemeinen zwei Möglichkeiten:
Wie Jeffrey sagt, sieht der Fortsetzungsmodus etwas hässlich aus, weil Sie alle Funktionen so umformen müssen, dass sie eine andere Funktion übernehmen und das Ergebnis zurückgeben, indem Sie sie aufrufen. Sie können dies jedoch etwas schöner gestalten, da Fortsetzungen Monaden sind und Sie Berechnungsausdrücke verwenden können.
Wenn Sie den folgenden Berechnungsgenerator definieren:
%Vor%Dann können Sie die Lösung von @gradbot wie folgt umschreiben (und die explizite Konstruktion von Lambda-Funktionen loswerden):
%Vor% Wenn Sie das Minimum für eine Reihe von rekursiven Aufrufen verwenden möchten, können Sie diesen Tail nicht rekursiv ausführen. Sie müssen die Operation min nach allen Aufrufen ausführen.
Sie können jede Berechnung so konvertieren, dass sie Tail-Aufrufe verwendet, indem Sie in den Fortsetzungsmodus umwandeln.
Die Art der Fortsetzung des Passierens sieht (für mich) oft kompliziert aus, aber ich vermute, wenn man sich erst einmal daran gewöhnt hat, ist das ziemlich einfach.
Tags und Links algorithm f# functional-programming ocaml tail-recursion