Damerau-LevenshteinDistance algorithm in O(m) Space

damerauLevenshteinDistance.fs

//based on http://mwh.geek.nz/2009/04/26/python-damerau-levenshtein-distance/

let damerauLevenshteinDistance (arr1:'a []) (arr2:'a []) =  
    let wrap j k = if j = k then arr2.Length else j - 1 - k 
    let rec outer (oneback:int[]) (twoback:int[]) s = function
       | i when i = arr1.Length || arr2.Length = 0 -> s
       | i ->  let thisrow = Array.zeroCreate (arr2.Length+1) in thisrow.[thisrow.Length - 1] <- i + 1 
               for j in 0..arr2.Length - 1 do 
                    let delcost, addcost, subcost = oneback.[j] + 1, thisrow.[wrap j 0] + 1,
                                                                oneback.[wrap j 0] + if arr1.[i] <> arr2.[j] then 1 else 0
                    thisrow.[j] <- [delcost; addcost; subcost] |> List.min                    
                    if i > 0 && j > 0 && arr1.[i] = arr2.[j-1] && arr1.[i - 1] = arr2.[j] && arr1.[i] <> arr2.[j] then
                                                    thisrow.[j] <-  min (thisrow.[j]) (twoback.[wrap j 1] + 1)     
               outer thisrow oneback thisrow.[arr2.Length - 1] (i + 1)
    outer (Array.append (Array.init arr2.Length ((+) 1)) [|0|]) (Array.zeroCreate (arr2.Length+1)) (max arr1.Length arr2.Length) 0
                                        

damerauLevenshteinDistance "philosophy" "philomath";;
val it : int = 4

damerauLevenshteinDistance "yacht" "";;
val it : int = 5

damerauLevenshteinDistance "yacht" "fact";;
val it : int = 2