algorithm - 尾递归编辑距离

Question

我在 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 转换为尾递归)

Answer 1

一般来说，当你想把代码变成尾递归形式时，你有两个选择:

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

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

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

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