алгоритм редактирования расстояния в Haskell - настройка производительности

Я пытаюсь реализовать расстояние Левенштейна (или расстояние редактирования) в Haskell, но его производительность быстро снижается при увеличении длины строки.

Я все еще новичок в Haskell, поэтому было бы неплохо, если бы вы дали мне несколько советов о том, как я могу улучшить алгоритм. Я уже пробовал «предварительно вычислить» значения (инициалы), но, поскольку это ничего не изменило, я отменил это изменение.

Я знаю, что на Hackage уже есть реализация editDistance , но мне нужно, чтобы он работал со списками произвольных токенов, не обязательно строк. Кроме того, я нахожу это немного сложным, по крайней мере, по сравнению с моей версией.

Итак, вот код:

-- 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
                                   ]

Кажется, это правильная реализация, по крайней мере, она дает точно такие же результаты, как и эта в Интернете инструмент .

Заранее благодарим за помощь! Если вам нужна дополнительная информация, дайте мне знать.

Приветствую, bzn