Skip to content

Instantly share code, notes, and snippets.

@jdoiwork

jdoiwork/LevenshteinDistance.hs

Last active May 11, 2017 07:22
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jdoiwork/2e05e7df51608109c1590cfa0bfe1857 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jdoiwork/2e05e7df51608109c1590cfa0bfe1857 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
LevenshteinDistance.hs
-- https://en.wikipedia.org/wiki/Levenshtein_distance
type Length = Int
type Distance = Int
levenshteinDistance :: String -> String -> Distance
levenshteinDistance a b = lev a b i j
where i = length a
j = length b
lev :: String -> String -> Length -> Length -> Distance
lev _ _ 0 j = j
lev _ _ i 0 = i
lev a b i j = minimum [ (lev (tail a) ( b) (i - 1) (j )) + 1
, (lev ( a) (tail b) (i ) (j - 1)) + 1
, (lev (tail a) (tail b) (i - 1) (j - 1)) + cost
]
where cost = if (head a) == (head b) then 0 else 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment