levenshtein 0.1.0.0 → 0.1.1.0

raw patch · 3 files changed

+40/−14 lines, 3 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• levenshtein.cabal +1/−1
• src/Data/Foldable/Levenshtein.hs +17/−11
• test/Data/Foldable/LevenshteinSpec.hs +22/−2

@@ -1,5 +1,5 @@ name:                levenshtein-version:             0.1.0.0+version:             0.1.1.0 synopsis:            Calculate the edit distance between two foldables. description:   A package to determine the edit distance between two 'Foldable's.

@@ -1,4 +1,4 @@-{-# LANGUAGE DeriveDataTypeable, DeriveGeneric, DeriveTraversable, Safe #-}+{-# LANGUAGE CPP, DeriveDataTypeable, DeriveGeneric, DeriveTraversable, Safe #-}  {-| Module      : Data.Foldable.Levenshtein@@ -21,7 +21,7 @@     -- * Obtain the Levenshtein distance together with a reversed path of 'Edit's   , genericReversedLevenshtein, genericReversedLevenshtein', reversedLevenshtein, reversedLevenshtein'     -- * Data type to present modifications from one 'Foldable' to the other.a-  , Edit(Add, Rem, Copy, Swap), applyEdits+  , Edit(Add, Rem, Copy, Swap), Edits, applyEdits   ) where  import Control.Arrow(second)@@ -33,6 +33,9 @@ import Data.Functor.Classes(Eq1(liftEq), Ord1(liftCompare)) import Data.Hashable(Hashable) import Data.Hashable.Lifted(Hashable1)+#if __GLASGOW_HASKELL__ < 803+import Data.Semigroup(Semigroup((<>)))+#endif  import GHC.Generics(Generic, Generic1) @@ -105,12 +108,15 @@           go _ (Copy _) = GT           go (Swap xa ya) (Swap xb yb) = cmp xa xb <> cmp ya yb +-- | A type alias for a /list/ of 'Edit's.+type Edits a = [Edit a]+ -- | Apply the given list of 'Edit's to the given list. -- If the 'Edit's make sense, it returns the result wrapped -- in a 'Just', if a check with the item that is removed/replaced -- fails, the function will return 'Nothing'. applyEdits :: Eq a-  => [Edit a]  -- ^ The given list of 'Edit's to apply to the given list.+  => Edits a  -- ^ The given list of 'Edit's to apply to the given list.   -> [a]  -- ^ The list of items to edit with the given 'Edit's.   -> Maybe [a]  -- ^ The modified list, given the checks hold about what item to remove/replace wrapped in a 'Just'; 'Nothing' otherwise. applyEdits [] ys = Just ys@@ -138,7 +144,7 @@ levenshtein :: (Foldable f, Foldable g, Eq a, Num b, Ord b)   => f a  -- ^ The given original sequence.   -> g a  -- ^ The given target sequence.-  -> (b, [Edit a])  -- ^ The edit distance between the two 'Foldable's.+  -> (b, Edits a)  -- ^ The edit distance between the two 'Foldable's. levenshtein = levenshtein' (==)  -- | Determine the edit distance together with the steps to transform the first 'Foldable'@@ -149,7 +155,7 @@   => (a -> a -> Bool)  -- ^ The given equivalence relation to work with.   -> f a  -- ^ The given original sequence.   -> g a  -- ^ The given target sequence.-  -> (b, [Edit a])  -- ^ The edit distance between the two 'Foldable's together with a list of 'Edit's to transform the first 'Foldable' to the second one.+  -> (b, Edits a)  -- ^ The edit distance between the two 'Foldable's together with a list of 'Edit's to transform the first 'Foldable' to the second one. levenshtein' = _addDefaults . genericLevenshtein'  -- | Determine the edit distance together with the steps to transform the first 'Foldable'@@ -159,7 +165,7 @@ reversedLevenshtein :: (Foldable f, Foldable g, Eq a, Num b, Ord b)   => f a  -- ^ The given original sequence.   -> g a  -- ^ The given target sequence.-  -> (b, [Edit a])  -- ^ The edit distance between the two 'Foldable's together with the 'Edit's to make to convert the first sequence into the second.+  -> (b, Edits a)  -- ^ The edit distance between the two 'Foldable's together with the 'Edit's to make to convert the first sequence into the second. reversedLevenshtein = reversedLevenshtein' (==)  -- | Determine the edit distance together with the steps to transform the first 'Foldable'@@ -170,7 +176,7 @@   => (a -> a -> Bool)  -- ^ The given equivalence relation to work with.   -> f a  -- ^ The given original sequence.   -> g a  -- ^ The given target sequence.-  -> (b, [Edit a])  -- ^ The edit distance between the two 'Foldable's together with a reversed list of 'Edit's to transform the original sequence into the target sequence.+  -> (b, Edits a)  -- ^ The edit distance between the two 'Foldable's together with a reversed list of 'Edit's to transform the original sequence into the target sequence. reversedLevenshtein' = _addDefaults . genericReversedLevenshtein'  -- | Determine the edit distance to transform the first 'Foldable' (as list)@@ -234,7 +240,7 @@   -> (a -> a -> b)  -- ^ The cost that it takes to replace an item of the first parameter with one of the second parameter. The return value should be positive.   -> f a  -- ^ The given original sequence.   -> g a  -- ^ The given target sequence.-  -> (b, [Edit a])  -- ^ A 2-tuple with the edit score as first item, and a list of modifications in /normal/ order as second item to transform the first sequence to the second one.+  -> (b, Edits a)  -- ^ A 2-tuple with the edit score as first item, and a list of modifications in /normal/ order as second item to transform the first sequence to the second one. genericLevenshtein' eq ad rm sw xs' = second reverse . genericReversedLevenshtein' eq ad rm sw xs'  -- | A function to determine the /Levenshtein distance/ together with a list of 'Edit's@@ -248,7 +254,7 @@   -> (a -> a -> b)  -- ^ The cost that it takes to replace an item of the first parameter with one of the second parameter. The return value should be positive.   -> f a  -- ^ The given original sequence.   -> g a  -- ^ The given target sequence.-  -> (b, [Edit a])  -- ^ A 2-tuple with the edit score as first item, and a list of modifications in /normal/ order as second item to transform the first sequence to the second one.+  -> (b, Edits a)  -- ^ A 2-tuple with the edit score as first item, and a list of modifications in /normal/ order as second item to transform the first sequence to the second one. genericLevenshtein = genericLevenshtein' (==)  -- | A function to determine the /Levenshtein distance/ together with a list of 'Edit's@@ -263,7 +269,7 @@   -> (a -> a -> b)  -- ^ The cost that it takes to replace an item of the first parameter with one of the second parameter. The return value should be positive.   -> f a  -- ^ The given original sequence.   -> g a  -- ^ The given target sequence.-  -> (b, [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 'Foldable' (as list) to the second 'Foldable' (as list).+  -> (b, Edits 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 'Foldable' (as list) to the second 'Foldable' (as list). genericReversedLevenshtein' eq ad rm sw xs' ys' = last (foldl (nextRow tl) row0 xs')   where     row0 = scanl (\(w, is) i -> (w+ad i, Add i: is)) (0, []) tl@@ -290,5 +296,5 @@   -> (a -> a -> b)  -- ^ The cost that it takes to replace an item of the first parameter with one of the second parameter. The return value should be positive.   -> f a  -- ^ The given original sequence.   -> g a  -- ^ The given target sequence.-  -> (b, [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 'Foldable' (as list) to the second 'Foldable' (as list).+  -> (b, Edits 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 'Foldable' (as list) to the second 'Foldable' (as list). genericReversedLevenshtein = genericReversedLevenshtein' (==)

@@ -1,10 +1,10 @@-{-# LANGUAGE ExistentialQuantification, RankNTypes, TypeApplications #-}+{-# LANGUAGE ExistentialQuantification, RankNTypes, ScopedTypeVariables, TypeApplications #-}  module Data.Foldable.LevenshteinSpec (     spec   ) where -import Data.Foldable.Levenshtein(applyEdits, levenshtein, levenshteinDistance)+import Data.Foldable.Levenshtein(Edits, applyEdits, genericLevenshteinDistance, genericLevenshteinDistance', levenshteinDistance, levenshteinDistance', genericLevenshtein, genericLevenshtein', levenshtein, levenshtein', genericReversedLevenshtein, genericReversedLevenshtein', reversedLevenshtein, reversedLevenshtein')  import Test.Hspec(Spec, it) import Test.QuickCheck(maxSuccess, property, quickCheckWith, stdArgs)@@ -20,18 +20,38 @@   it "test triangle inequality" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (triangleInequality @ Int)))   it "test applying edits" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (testApplyingEdits @ Int)))   it "Hamming distance bound" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (hammingDistanceBound @ Int)))+  it "Test if all distance metrics report the same" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (allDistancesSame @ Int)))   it "lowerbound string difference" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (lowerBoundLengthDiff @ Char)))   it "upperbound largest string" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (upperBoundLengthDiff @ Char)))   it "if zero then same list" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (ifZeroThenSame @ Char)))   it "test triangle inequality" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (triangleInequality @ Char)))   it "test applying edits" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (testApplyingEdits @ Char)))   it "Hamming distance bound" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (hammingDistanceBound @ Char)))+  it "Test if all distance metrics report the same" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (allDistancesSame @ Char)))   it "lowerbound string difference" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (lowerBoundLengthDiff @ Bool)))   it "upperbound largest string" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (upperBoundLengthDiff @ Bool)))   it "if zero then same list" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (ifZeroThenSame @ Bool)))   it "test triangle inequality" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (triangleInequality @ Bool)))   it "test applying edits" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (testApplyingEdits @ Bool)))   it "Hamming distance bound" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (hammingDistanceBound @ Bool)))+  it "Test if all distance metrics report the same" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (allDistancesSame @ Bool)))++allDistancesSame :: forall a . Eq a => [a] -> [a] -> Bool+allDistancesSame xs ys = da == db && db == dc && dc == dd && dd == de && de == df && df == dg && dg == dh+                      && dh == di && di == dj && dj == dk && dk == dl && efa == efb && efb == efc+                      && efc == efd && reverse efd == era && era == erb && erb == erc && erc == erd+  where da = genericLevenshteinDistance (const 1) (const 1) (const (const 1)) xs ys :: Int+        db = genericLevenshteinDistance' (==) (const 1) (const 1) (const (const 1)) xs ys :: Int+        dc = levenshteinDistance xs ys :: Int+        dd = levenshteinDistance' (==) xs ys :: Int+        (de, efa) = genericLevenshtein (const 1) (const 1) (const (const 1)) xs ys :: (Int, Edits a)+        (df, efb) = genericLevenshtein' (==) (const 1) (const 1) (const (const 1)) xs ys :: (Int, Edits a)+        (dg, efc) = levenshtein xs ys :: (Int, Edits a)+        (dh, efd) = levenshtein' (==) xs ys :: (Int, Edits a)+        (di, era) = genericReversedLevenshtein (const 1) (const 1) (const (const 1)) xs ys :: (Int, Edits a)+        (dj, erb) = genericReversedLevenshtein' (==) (const 1) (const 1) (const (const 1)) xs ys :: (Int, Edits a)+        (dk, erc) = reversedLevenshtein xs ys :: (Int, Edits a)+        (dl, erd) = reversedLevenshtein' (==) xs ys :: (Int, Edits a)   lowerBoundLengthDiff :: forall a . Eq a => [a] -> [a] -> Bool