Edit Question - KnowledgeHub

Title Body

I'm trying to implement the levenshtein distance (or edit distance) in Haskell, but its performance decreases rapidly when the string lenght increases. I'm still quite new to Haskell, so it would be nice if you could give me some advice on how I could improve the algorithm. I already tried to "precompute" values (the inits), but since it didn't change anything I reverted that change. I know there's already an editDistance implementation on Hackage, but I need it to work on lists of arbitrary tokens, not necessarily strings. Also, I find it a bit complicated, at least compared to my version. So, here's the code: -- standard levenshtein distance between two lists editDistance :: Eq a => [a] -> [a] -> Int editDistance s1 s2 = editDistance' 1 1 1 s1 s2 -- weighted levenshtein distance -- ins, sub and del are the costs for the various operations editDistance' :: Eq a => Int -> Int -> Int -> [a] -> [a] -> Int editDistance' _ _ ins s1 [] = ins * length s1 editDistance' _ _ ins [] s2 = ins * length s2 editDistance' del sub ins s1 s2 | last s1 == last s2 = editDistance' del sub ins (init s1) (init s2) | otherwise = minimum [ editDistance' del sub ins s1 (init s2) + del -- deletion , editDistance' del sub ins (init s1) (init s2) + sub -- substitution , editDistance' del sub ins (init s1) s2 + ins -- insertion ] It seems to be a correct implementation, at least it gives exactly the same results as this online tool . Thanks in advance for your help! If you need any additional information, please let me know. Greetings, bzn

Tags (comma-separated) Cancel