Safe Haskell | Safe |
---|---|

Language | Haskell98 |

## Synopsis

- editDistance :: Eq a => [a] -> [a] -> Int

# Documentation

editDistance :: Eq a => [a] -> [a] -> Int Source #

Calculate the Damerau-Levenshtein edit distance between two lists (strings).

This is modified from https://wiki.haskell.org/Edit_distance and is originally from Lloyd Allison's paper "Lazy Dynamic-Programming can be Eager"

It's been changed though from Levenshtein to Damerau-Levenshtein, which treats transposition of adjacent characters as one change instead of two.

Complexity O(|a|*(1 + editDistance a b))