Levenshtein distance

Wikipedia article

Code:

levenshtein sa sb = last $ foldl (transform sa) [0..length sa] sb
    where 
      transform str xs@(x:xs') c = res
          where
              res = x+1 : zipWith4 compute str xs xs' res
              compute c' x y z = minimum [y+1, z+1, x + if c' == c then 0 else 1]

Кстати, в 2006-ом году Владимир Левенштейн получил за это дело медаль Хэмминга.
Кстати, первую медаль Хэмминга получил сам Хэмминг.