Skip to content

Instantly share code, notes, and snippets.

@rampion

rampion/Levenshtein.hs

Forked from jberryman/med.hs
Created March 22, 2012 13:44
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save rampion/2158429 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save rampion/2158429 to your computer and use it in GitHub Desktop.
Download ZIP
an optimized haskell Levenshtein distance, using the vector library
Raw
med.hs
import qualified Data.Vector.Unboxed.Safe as V
med :: String -> String -> Int
med s1 = V.last . V.ifoldl' scanS1 costs_i . V.fromList
where vs1 = V.fromList s1
costs_i = V.enumFromN 1 $ V.length vs1 -- [0.. length s1]
scanS1 costs_W costSW_i c2 =
let v = V.zip vs1 costs_W
v' = V.postscanl' scanVec (costSW_i, costSW_i + 1) v
scanVec (costSW, costS) (c1, costW) =
(costW, min (min costS costW + 1)
(costSW + if c1 == c2 then 0 else 2))
in snd $ V.unzip v'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment