Tail Recursive Levenshteina Odległość

Question

I wdrożone Odległość Levenshteina w dość standardowy sposób w F # jako ćwiczenie

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 
     ]) 

Jednak nie widzę prosty sposób przekonwertować rozmowę List.min za ogon rekurencyjnej. Nie wykonujemy po prostu dodatkowych, niezależnych obliczeń po wywołaniu rekursywnym; zamiast tego wybieramy wynik wielu wywołań rekurencyjnych.

Czy istnieje sposób, aby elegancko przekonwertować to na rekursywne?

(można łatwo przekonwertować +1 za ogon rekurencyjnej)

Answer 1

W ogóle, jeśli chcesz, aby włączyć kod w postaci ogona-rekurencyjne, masz dwie opcje:

• Jeśli rekurencyjna funkcja zwraca tylko się raz, można użyć Paramter akumulatora.
• Jeśli to nazywa się wielokrotnie, trzeba użyć kontynuacje

Jak mówi Jeffrey, styl kontynuacja mijania wygląda nieco brzydki, bo trzeba przekształcić wszystkie funkcje podjąć inną funkcję i zwraca wynik przez wywołanie go. Możesz jednak uczynić to nieco ładniejszym, ponieważ kontynuacje są monadami, więc możesz używać wyrażeń obliczeniowych .

Jeżeli zdefiniowano następujące obliczeń producentów:

// 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() 

Następnie można przepisać rozwiązanie z @gradbot następująco (i pozbyć wyraźnej konstrukcji funkcji lambda):

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

Jeśli chcesz wziąć minimum nad zestawem wywołań rekurencyjnych, nie można zrobić ogon rekurencyjnie. Po wszystkich połączeniach musisz wykonać operację min.

Można przekonwertować dowolne obliczenia w taki sposób, aby korzystał z wywołań tylnych, konwertując do stylu przekazywania kontynuacji.

Ciąg dalszy przechodzenia często wydaje się zawiłowany (do mnie), ale podejrzewam, że gdy już się do tego przyzwyczaisz, jest to dość proste.

Answer 3

Podstawową ideą przejścia kontynuacji jest "ukrywanie" przyszłej pracy w funkcji.

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" 

wyjście

6