7

我在 F# 中以非常标准的方式实现了 Levenshtein Distance 作为练习

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

通常，当您想将代码转换为尾递归形式时，您有两种选择：

  • 如果你的递归函数只调用一次，你可以使用累加器参数。
  • 如果它多次调用自身，则需要使用延续

正如 Jeffrey 所说，延续传递风格看起来有点难看，因为您必须转换所有函数以获取另一个函数并通过调用它返回结果。但是，您可以使它更好一点，因为延续是单子，因此您可以使用计算表达式。

如果您定义以下计算构建器：

// 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 重写解决方案，如下所示（并摆脱 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)
于 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 回答