Estou tentando implementar a distância levenshtein (ou editar distância) em Haskell, mas seu desempenho diminui rapidamente quando o comprimento da string aument

Eu ainda sou bastante novo em Haskell, então seria bom se você pudesse me dar alguns conselhos sobre como eu poderia melhorar o algoritmo. Eu já tentei "pré-calcular" os valores (inits), mas como não mudou nada, reverti essa alteração.

Eu sei que já existe um editDistance implementação no Hackage, mas preciso que ele funcione em listas de tokens arbitrários, não necessariamente em strings. Além disso, acho um pouco complicado, pelo menos em comparação com a minha versã

Então, aqui está o código:

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

Parece ser uma implementação correta, pelo menos fornece exatamente os mesmos resultados que esteonline tool.

Agradeço antecipadamente por sua ajuda! Se precisar de mais informações, entre em contato.

Greetings, bzn