Schwanz rekursive Levenshtein Entfernung

Question

implementiert I Levenshtein Entfernung in einem ziemlich Standard Art und Weise in F # als eine Übung

let lastchar (s:string) = s.Substring(s.Length-1, 1) 
let lastchar_substring (s:string) len = s.Substring(len-1, 1) 

let rec levdist (sa:string) (sb:string) alen blen = match alen, blen with 
    | -1, -1 -> levdist sa sb sa.Length sb.Length 
    | 0, 0 -> 0 
    | _ , 0 -> alen 
    | 0, _ -> blen 
    | _ -> List.min [ (* How do I make this tail recursive...? *) 
      (levdist sa sb (alen-1) blen) + 1; 
      (levdist sa sb alen (blen-1)) + 1; 
      (levdist sa sb (alen-1) (blen-1)) + 
       match (lastchar_substring sa alen), (lastchar_substring sb blen) with 
         | x, y when x = y -> 0 
         | _ -> 1 
     ]) 

Allerdings habe ich nicht eine einfache Art und Weise finden Sie in der List.min Aufruf zu konvertieren Schwanz rekursiv zu sein. 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 umzuwandeln, um rekursiv zu sein?

(Ich kann leicht den +1 konvertieren Schwanz rekursiv zu sein)

Answer 1

Im Allgemeinen, wenn Sie Code in ein Schwanz-rekursive Form umwandeln möchten, haben Sie zwei Möglichkeiten:

• Wenn Ihre rekursive Funktion nennt sich nur einmal, können Sie Akku-Parameter verwenden.
• Wenn es sich mehrmals aufruft, müssen Sie Fortsetzungen

Wie Jeffrey sagt Fortsetzung Übertragungsstil sieht ein bisschen hässlich verwenden, da Sie alle Funktionen zur Transformation haben eine andere Funktion zu übernehmen und das Ergebnis zurück indem ich es anrufe. Sie können dies jedoch ein bisschen schöner machen, da Fortsetzungen Monaden sind und Sie können Berechnungsausdrücke verwenden.

Wenn Sie definieren die folgende Berechnung Bauer:

// Computation that uses CPS - when given a continuation 
// it does some computation and return the result 
type Cont<'T, 'R> = (('T -> 'R) -> 'R) 

type ContBuilder() = 
    member x.Return(v) : Cont<'T, 'R> = fun k -> k v 
    member x.ReturnFrom(r) = r 
    member x.Bind(vf:Cont<'T1, 'R>, f:'T1 -> Cont<'T2, 'R>) : Cont<'T2, 'R> = 
    fun k -> vf (fun v -> f v k) 

let cont = ContBuilder() 

Dann können Sie die Lösung von @gradbot wie folgt umschreiben (und werden die expliziten Konstruktion von Lambda-Funktionen zu befreien):

let levdist (sa:string) (sb:string) = 
    let rec levdist_cont (sa:string) (sb:string) alen blen = cont { 
     match alen, blen with 
     | -1, -1 -> return! levdist_cont sa sb sa.Length sb.Length 
     | 0, 0 -> return 0 
     | _, 0 -> return alen 
     | 0, _ -> return blen 
     | _ -> 
      let! l1 = levdist_cont sa sb (alen - 1) (blen ) 
      let! l2 = levdist_cont sa sb (alen ) (blen - 1) 
      let! l3 = levdist_cont sa sb (alen - 1) (blen - 1) 
      let d = if (lastchar_substring sa alen) = (lastchar_substring sb blen) then 0 else 1 
      return (min (l1 + 1) (min (l2 + 1) (l3 + d))) } 

    levdist_cont sa sb -1 -1 (fun x -> x) 

Answer 2

Wenn Sie das Minimum über einen Satz von rekursiven Anrufe annehmen möchten, können Sie diesen Schwanz rekursiv nicht. Sie müssen nach allen Anrufen die Operation min ausführen.

Sie können jede Berechnung so konvertieren, dass sie Tail-Aufrufe verwendet, indem Sie in den Continuation-Passing-Stil umwandeln.

Continuation Passing-Stil sieht oft kompliziert (für mich), aber ich vermute, sobald Sie sich daran gewöhnt haben, ist es einigermaßen unkompliziert.

Answer 3

Die Grundidee der Fortsetzungsübergabe ist, dass Sie zukünftige Arbeiten in einer Funktion "verstecken".

let lastchar (s:string) = s.Substring(s.Length-1, 1) 
let lastchar_substring (s:string) len = s.Substring(len-1, 1) 

let levdist (sa:string) (sb:string) = 
    let rec levdist_cont (sa:string) (sb:string) alen blen cont = 
     match alen, blen with 
     | -1, -1 -> levdist_cont sa sb sa.Length sb.Length cont 
     | 0, 0 -> cont 0 
     | _, 0 -> cont alen 
     | 0, _ -> cont blen 
     | _ -> 
      levdist_cont sa sb (alen - 1) (blen ) (fun l1 -> 
      levdist_cont sa sb (alen ) (blen - 1) (fun l2 -> 
      levdist_cont sa sb (alen - 1) (blen - 1) (fun l3 -> 
       let d = if (lastchar_substring sa alen) = (lastchar_substring sb blen) then 0 else 1 
       cont (min (l1 + 1) (min (l2 + 1) (l3 + d))) 
       ))) 

    levdist_cont sa sb -1 -1 (fun x -> x) 

levdist "guisuifgh" "sfg" 
|> printf "%A" 

Ausgang

6