Haskell Program for Levenshtein distance

Question

I need a program in Haskell that computes the Levenshtein distance.

Answer 1

You need to calculate the Levenshtein distance (also called the edit distance) which is defined as follow for strings a and b: (taken from Wikipedia):

Because the values of lev(i,j) only depends on previous values, we can take advantage of Haskell's lazyness to intialize an Array where the value of element at position (i, j) is a function of previous values of the same array! See Dynamic programming example to see examples of how this can be done.

Here goes an basic implementation for lev:

import Data.Array

lev :: String -> String -> Int
lev x y = c ! (m, n)
  where
    c = listArray ((0, 0), (m, n)) [compute i j | i <- [0 .. m], j <- [0 .. n]]
    compute 0 j = j
    compute i 0 = i
    compute i j
      | x !! (i - 1) == y !! (j - 1) = c ! (i - 1, j - 1)
      | otherwise = 1 + (minimum $ map (c !) [(i , j - 1),
                                              (i - 1, j),
                                              (i - 1, j - 1)])
    m = length x
    n = length y

This code can be further optimized, but should give you a good idea to get started.

After computing the Levenshtein, you just need to compare it with the edit cost bound k.