| Maintainer | hapytexeu+gh@gmail.com |
|---|---|
| Stability | experimental |
| Portability | POSIX |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Dep.Algorithm.Levenshtein
Description
This module exports functions to help determine how different two sequences are. This is used to guess the name of the command if the command given by the user does not map on an action.
Synopsis
- data Edit a
- editScore :: Edit a -> Int
- editScore' :: Foldable f => f (Edit a) -> Int
- levenshtein :: Eq a => [a] -> [a] -> (Int, [Edit a])
- levenshtein' :: (a -> a -> Bool) -> [a] -> [a] -> (Int, [Edit a])
- reversedLevenshtein :: Eq a => [a] -> [a] -> (Int, [Edit a])
- reversedLevenshtein' :: (a -> a -> Bool) -> [a] -> [a] -> (Int, [Edit a])
- genericReversedLevenshtein :: Eq a => (a -> Int) -> (a -> Int) -> (a -> a -> Int) -> [a] -> [a] -> (Int, [Edit a])
- genericReversedLevenshtein' :: (a -> a -> Bool) -> (a -> Int) -> (a -> Int) -> (a -> a -> Int) -> [a] -> [a] -> (Int, [Edit a])
Present edits to a sequence
A data type that is used to list how to edit a sequence to form another sequence.
Constructors
| Add a | We add the given element to the sequence. |
| Rem a | We remove the given element to the sequence. |
| Copy a | We copy an element from the sequence, this basically act as a no-op. |
| Swap a a | We modify the given first item into the second item, this thus denotes a replacement. |
Instances
Edit distance score
Determine the standard edit score for the Levenshtein distance.
Determine the most optimal edit
Arguments
| :: Eq a | |
| => [a] | The original given sequence. |
| -> [a] | The target given sequence. |
| -> (Int, [Edit a]) | A 2-tuple with the edit score as first item, and a list of modifications as second item to transform the first sequence to the second one. |
Obtain the Levenshtein distance from one sequence ot another, given we each time add one point for an addition, deletion and substitution.
Arguments
| :: (a -> a -> Bool) | A function that determines whether the two items of the sequences are equivalent. |
| -> [a] | The original given sequence. |
| -> [a] | The target given sequence. |
| -> (Int, [Edit a]) | A 2-tuple with the edit score as first item, and a list of modifications as second item to transform the first sequence to the second one. |
Obtain the Levenshtein distance from one sequence ot another, given we each time add one point for an addition, deletion and substitution. The equality relation is given, for example to perform case-insensitive matching.
Arguments
| :: Eq a | |
| => [a] | The original given sequence. |
| -> [a] | The target given sequence. |
| -> (Int, [Edit a]) | A 2-tuple with the edit score as first item, and a list of modifications in reversed order as second item to transform the first sequence to the second one. |
Obtain the Levenshtein distance where the list of edits is in reverse order. This because this is more efficient and is thus useful if the order of
the Edits does not matter much.
Arguments
| :: (a -> a -> Bool) | The given equivalence relation to work with. |
| -> [a] | The original given sequence. |
| -> [a] | The target sequence. |
| -> (Int, [Edit a]) | A 2-tuple with the edit score as first item, and a list of modifications in reversed order as second item to transform the first sequence to the second one. |
Obtain the Levenshtein distance where the list of edits is in reverse order. This because this is more efficient and is thus useful if the order of
the Edits does not matter much. The equivalence relation is given through a parameter, and thus can for example allow case-insensitive matching.
Advanced Levenshtein distances
genericReversedLevenshtein Source #
Arguments
| :: Eq a | |
| => (a -> Int) | The cost of adding the given item. |
| -> (a -> Int) | The cost of removing the given item. |
| -> (a -> a -> Int) | The cost that it takes to replace an item of the first parameter with one of the second parameter. |
| -> [a] | The original given sequence. |
| -> [a] | The target sequence. |
| -> (Int, [Edit a]) | A 2-tuple with the edit score as first item, and a list of modifications in reversed order as second item to transform the first sequence to the second one. |
A function to determine the Levenshtein distance by specifying the cost functions of adding, removing and editing characters. The 2-tuple returns the distance
as first item of the 2-tuple, and the list of Edits in reverse order as second item.
genericReversedLevenshtein' Source #
Arguments
| :: (a -> a -> Bool) | The given equivalence relation to work with. |
| -> (a -> Int) | The cost of adding the given item. |
| -> (a -> Int) | The cost of removing the given item. |
| -> (a -> a -> Int) | The cost that it takes to replace an item of the first parameter with one of the second parameter. |
| -> [a] | The original given sequence. |
| -> [a] | The target sequence. |
| -> (Int, [Edit a]) | A 2-tuple with the edit score as first item, and a list of modifications in reversed order as second item to transform the first sequence to the second one. |
A function to determine the Levenshtein distance by specifying the cost functions of adding, removing and editing characters. The 2-tuple returns the distance
as first item of the 2-tuple, and the list of Edits in reverse order as second item.