7

演習として、F# でかなり標準的な方法でレーベンシュタイン距離を実装しました。

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

ただし、List.min 呼び出しを末尾再帰に変換する簡単な方法はわかりません。再帰呼び出しの後に、追加の独立した計算を単純に行っているわけではありません。代わりに、複数の再帰呼び出しの結果を選択しています。

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

+1(末尾再帰に簡単に変換できます)

4

3 に答える 3

12

一般に、コードを末尾再帰形式に変換する場合は、次の2つのオプションがあります。

  • 再帰関数がそれ自体を1回だけ呼び出す場合は、アキュムレータパラメータを使用できます。
  • 自分自身を複数回呼び出す場合は、継続を使用する必要があります

ジェフリーが言うように、継続渡しスタイルは少し見苦しいように見えます。これは、すべての関数を変換して別の関数を取得し、それを呼び出して結果を返す必要があるためです。ただし、継続はモナドであり、計算式を使用できるため、これを少し改善することができます。

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

// 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)
于 2013-02-13T22:20:57.957 に答える
7

一連の再帰呼び出しで最小値を取りたい場合、このテールを再帰的に行うことはできません。minすべての呼び出しの後に操作を行う必要があります。

継続渡しスタイルに変換することで、末尾呼び出しを使用するように任意の計算を変換できます。

継続渡しのスタイルは (私には) 複雑に見えることがよくありますが、慣れればかなり簡単だと思います。

于 2013-02-13T18:21:49.933 に答える
4

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

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
于 2013-02-13T21:30:24.253 に答える