尾递归Levenshtein距离

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

通常,当您想将代码转换为尾递归形式时,您有两个选择:

• 如果递归函数只调用一次,则可以使用累加器参数.
• 如果它多次调用自己,则需要使用continuation

正如Jeffrey所说,延续传递样式看起来有点难看,因为你必须转换所有函数以获取另一个函数并通过调用返回结果.但是,你可以使它更好一点,因为continuation是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)

Answer 2

如果你想在一组递归调用上采取最小值,则不能递归地执行此尾.min所有呼叫后都需要进行操作.

您可以转换任何计算,以便通过转换为延续传递样式来使用尾调用.

延续传球风格通常看起来很复杂(对我来说),但我怀疑一旦你习惯它,它是相当简单的.