F#で編集距離の関数を書いてみる

下記をちょっとF#で書いてみる。

あれ、編集距離と違うのかな？

レーベンシュタイン距離 - Wikipedia

open System

let rec editDistance (s1:char list) (s2:char list) : int = 

  match (s1, s2) with
  | ([], _) -> Seq.length s2
  | (_, []) -> Seq.length s1
  | (h1::t1, h2::t2) -> if h1 = h2 then editDistance t1 t2 else 1 + List.min [ editDistance t1 s2; editDistance s1 t2; editDistance t1 t2]

let ed (s1:string) (s2:string) =
  editDistance (Seq.toList s1) (Seq.toList s2)

[<EntryPoint>]
let main argv =
    printfn "Hello World from F#!"
    printfn "%d" <| ed "" "tesat"
    0 // return an integer exit code