| CARVIEW |
levenshtein: Calculate the edit distance between two foldables.
A package to determine the edit distance between two Foldables.
These are converted to lists, and the Levenshtein distance determine
how many additions, removals and changes are necessary to change
the first list into the second list.
[Skip to Readme]
Downloads
- levenshtein-0.2.1.0.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
| Versions [RSS] | 0.1.0.0, 0.1.1.0, 0.1.2.0, 0.1.3.0, 0.2.0.0, 0.2.1.0 |
|---|---|
| Change log | CHANGELOG.md |
| Dependencies | base (>=4.7 && <5), binary (>=0.2), data-default-class (>=0.0.1), deepseq (>=1.4.3.0), hashable (>=1.2.7.0), QuickCheck [details] |
| License | BSD-3-Clause |
| Copyright | 2021 Willem Van Onsem |
| Author | Willem Van Onsem |
| Maintainer | hapytexteu+gh@gmail.com |
| Uploaded | by wvanonsem90 at 2022-07-27T22:34:21Z |
| Category | tools |
| Home page | https://github.com/hapytex/levenshtein#readme |
| Source repo | head: git clone https://github.com/hapytex/levenshtein |
| Distributions | NixOS:0.2.1.0 |
| Reverse Dependencies | 1 direct, 0 indirect [details] |
| Downloads | 1006 total (21 in the last 30 days) |
| Rating | (no votes yet) [estimated by Bayesian average] |
| Your Rating |
|
| Status | Docs available [build log] Last success reported on 2022-07-27 [all 1 reports] |
Readme for levenshtein-0.2.1.0
[back to package description]levenshtein
Usage
The module Data.Foldable.Levenshtein exports a data type Edit that
represent the possible ways to edit a list by Adding an element, Removing
an element, Copying (do nothing with the element), and Swap with a new value.
One can apply such edits to a list with the applyEdits function, for example:
Prelude> applyEdits [Copy 1,Swap 3 4,Swap 0 2,Swap 2 5] [1,3,0,2]
Just [1,4,2,5]
We can also calculate the minimal list of edits necessary to turn one list into another one, for example:
Prelude> levenshtein [1,3,0,2] [1,4,2,5]
(3,[Copy 1,Swap 3 4,Swap 0 2,Swap 2 5])
here it means that the smallest edit distance is three, and that in order to transform
[1,3,0,2] to [1,4,2,5] we copy 1 change 3 for 4, change 0 for 2, and change 2 for 5.
Package structure
The package contains one module: Data.Foldable.Levenshtein.
This module provides functions to determine the edit distance and
a list of edits to turn one Foldable of items to another Foldable
of items. The foldables are first converted to a list, so the edits
always eventually produce a list of edits, even if (one of) the Foldables
is for example a Tree, Maybe, etc.
Besides the Edit object, the module exports three types of functions:
- functions that return the edit distance together with a list of reversed edits;
- functions that return the edit distance with a list of edits (not reversed); and
- functions that only calculate the edit distance, not the edits itself.
The third type is more an optimized version of the first two types since it will take less memory and finish slightly faster.
Some functions allow to specify the penalty for an insertion, deletion, and replacement, and this even per item.
In the table below, we show the different implementations to determine the Levenshtein distance:
| Edits | Eq | Equality function | Eq | |
|---|---|---|---|---|
| penalty functions | default | |||
| Normal | genericLevenshtein |
genericLevenshtein' |
levenshtein' |
levenshtein |
| Reversed | genericReversedLevenshtein |
genericReversedLevenshtein' |
reversedLevenshtein' |
reversedLevenshtein |
| Without | genericLevenshteinDistance |
genericLevenshteinDistance' |
levenshteinDistance' |
levenshteinDistance |
levenshtein is safe Haskell
The levenshtein package does not work with arrays, vectors,
etc. but only vanilla lists, making this a safe package.
Contribute
You can contribute by making a pull request on the GitHub repository.
You can contact the package maintainer by sending a mail to
hapytexeu+gh@gmail.com.