Levenshtein Distance with Haskell Vectors and Memoization

Question

Is the following an effective way to implement the Levenshtein Distance with Haskell vectors?

  import qualified Data.Vector as V

  levenshtein s1 s2 = levenshteinV (V.fromList s1) (V.fromList s2)

  levenshteinV p1 p2 = lev V.! l1 V.! l2
    where
      lev    = V.map levi      (V.enumFromN 0 (l1 + 1))
      levi i = V.map (levij i) (V.enumFromN 0 (l2 + 1))
      levij i j
        | i == 0    = j
        | j == 0    = i
        | otherwise =
          ((lev V.! (i - 1) V.!  j)      + 1) `min`
          ((lev V.!  i      V.! (j - 1)) + 1) `min`
          ((lev V.! (i - 1) V.! (j - 1)) + ind (i - 1) (j - 1))

      ind i j = if p1 V.! i == p2 V.! j then 0 else 1
      l1      = V.length p1
      l2      = V.length p2

In particular, should I be using V.map to construct the vectors or is there a better approach? Perhaps V.generate? Or does it not make a difference because of lazy evaluation?

Answer 1

Readability improves a lot with import Data.Vector ((!)) and replacing V.! with !.

generate looks better; performance-wise I do not expect a difference (with optimization).

lev    = V.generate (l1 + 1) levi

If you like point-free notation, you can short-cut levi, with intermediate manual steps:

  lev    = V.generate (l1 + 1) levi
  levi i = V.generate (l2 + 1) (levij i)

2

  lev    = V.generate (l1 + 1) (\i ->
           V.generate (l2 + 1) (levij i))

3

  lev    = V.generate (l1 + 1) (\i -> V.generate (l2 + 1) (levij i))

4

  lev    = V.generate (l1 + 1) (V.generate (l2 + 1) . levij)

Your code looks good. You might try it with Array next, to two-dimensional Index. The google results for haskell levenshtein Array are only marginally better than your Vector approach.