5
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – ana Apr 20 '15 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.