The edit distance or Levenshtein distance is the minimum number of simple string operations required to convert one string into another. In this recipe, we will compute the edit distance based on only insertions, deletions, and substitutions of characters.
Review the equation shown in the following figure obtained from the Wikipedia article about the Levenshtein distance (http://en.wikipedia.org/wiki/Levenshtein_distance):
Here, a and b are the two strings, and i and j are numbers representing their lengths.
The Haskell code will be a direct translation of this mathematical formula.
Also, install the data-memocombinators
package from Cabal. This allows us to minimize redundant computations to improve runtime.
$ cabal install data-memocombinators