末尾再帰レーベンシュタイン距離

Question

私は運動

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

としてF＃でかなり標準的な方法でレーベンシュタイン距離を実現ししかし、私は末尾再帰するList.minコールを変換する簡単な方法が表示されません。再帰呼び出しの後に、単に独立した計算を追加するだけではありません。代わりに、複数の再帰呼び出しの結果を選択しています。

エレガントにこれを尾を再帰的に変換する方法はありますか？

（私は簡単に+1は末尾再帰であることを変換することができます）

Answer 1

、あなたは末尾再帰形式にコードを有効にするとき、あなたは2つのオプションがあります。あなたの再帰関数は、自分自身だけを呼び出す場合

• をに一度アキュムレータパラメータを使用できます。
• それ自体を複数回呼び出した場合、あなたはジェフリーが言うように継続

を使用する必要があり、継続渡しスタイルあなたが別の関数を取り、結果を返すために、すべての機能を変換する必要があるため、ビット醜いですそれを呼び出すことによって。しかし、継続はモナドであるため、これを少し上手くできるので、の計算式を使うことができます。

次の計算ビルダー定義する場合：

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

は、その後、あなたが以下のように@gradbotからソリューションを書き換えることができます（とラムダ関数の明示的な建設を取り除く）：

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

あなたは再帰呼び出しのセットで最小を取るしたい場合は、再帰的にこの尾を行うことはできません。すべての通話後にmin操作を実行する必要があります。

継続通行スタイルに変換してテールコールを使用するように任意の計算を変換できます。

継続的な通過スタイルはしばしば（私には）複雑に見えますが、それに慣れるとそれはかなり簡単です。

Answer 3

継続継承の基本的な考え方は、関数内の将来の作業を「隠す」ことです。

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" 

出力

一般に

6