Levenshtein Distance with Haskell Vectors and Memoization

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?

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.

• Thanks. I also read about the repa library but it is bit mysterious to me. Would you be able to help me translate this to use repa? It could be a tutorial for me and also we can see whether it would perform better. – ana Apr 20 '15 at 19:37