LevenshteinDistance.hs

module LevenshteinDistance where
import Data.Array

levenshteinDistance xs ys = tbl!(n,m)
    where
      n = length xs
      m = length ys
      tbl = listArray ((0,0),(n,m)) [ let x = if xs!!(i-1) == ys!!(j-1) then 0 else 1
                                      in
                                        if i==0 then j
                                        else if j==0 then i
                                             else  
                                                 minimum ([ tbl!(i-1,j-1) + x
                                                          , tbl!(i-1,j)   + 1
                                                          , tbl!(i, j-1)  + 1
                                                          ])
                                      | (i,j)<-range((0,0),(n,m))
                                    ]