F# on Algorithms - Wagner–Fischer algorithm

You never know when these algorithms can be used. This is the Levenshtein distance between two strings.　This sample code also demonstrates how to use Array2D in F#.

 let levenshteinDistance (str0:string) (str1:string) =   
   let s0 = str0.ToCharArray()  
   let s1 = str1.ToCharArray()  
   let result = Array2D.initBased -1 -1 (s0.Length+1) (s1.Length+1)  
           (fun i j ->   
             match i,j with  
             | (-1, -1) -> 0  
             | (_, -1) -> i+1  
             | (-1, _) -> j+1  
             | _ -> 0)  
   let min3 a b c = min a b |> (min c)  
   result   
   |> Array2D.iteri (fun i j v->   
             match i,j with  
             | (-1, -1)   
             | (_, -1)   
             | (-1, _) -> ()  
             | _ when s0.[i] = s1.[j] ->   
               result.[i,j] <- result.[i-1,j-1]  
             | _ ->   
               result.[i,j] <- 1 + min3 result.[i-1,j] result.[i,j-1] result.[i-1,j-1])  
   result  

Tweet to fsharp