Tail Recursive Levenshtein Distance

Question

I implemented Levenshtein Distance in a pretty standard way in F# as an exercise

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

However, I don't see a straightforward way to convert the List.min call to be tail recursive. We're not simply doing some additional, independent computations after the recursive call; instead we're choosing the result of multiple recursive calls.

Is there a way to elegantly convert this to be tail recursive?

(I can easily convert the +1 to be tail recursive)

Answer 1

In general, when you want to turn code into a tail-recursive form, you have two options:

• If your recursive function calls itself only once, you can use accumulator paramter.
• If it calls itself multiple times, you need to use continuations

As Jeffrey says, continuation passing style looks a bit ugly, because you have to transform all functions to take another function and return the result by calling it. You can, however, make this a bit nicer because continuations are monads and so you can use computation expressions.

If you define the following computation builder:

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

Then you can rewrite the solution from @gradbot as follows (and get rid of the explicit construction of lambda functions):

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)