levenshtein 0.1.3.0 → 0.2.0.0

raw patch · 5 files changed

+198/−19 lines, 5 filesdep +criteriondep +data-default-classdep −data-defaultdep ~basedep ~deepseqPVP ok

version bump matches the API change (PVP)

Dependencies added: criterion, data-default-class

Dependencies removed: data-default

Dependency ranges changed: base, deepseq

API changes (from Hackage documentation)

Files

• CHANGELOG.md +4/−0
• bench/levenshtein-bench.hs +65/−0
• levenshtein.cabal +17/−2
• src/Data/Foldable/Levenshtein.hs +70/−6
• test/Data/Foldable/LevenshteinSpec.hs +42/−11

@@ -2,6 +2,10 @@  For a full list of changes, see the history on [*GitHub*](https://github.com/hapytex/levenshtein). +## Version 0.2.0.0++Use `data-default-class` instead of `data-default` as dependency.+ ## Version 0.1.0.0  The first version that can determine the Levenshtein distance and edits necessary.

@@ -0,0 +1,65 @@+{-# OPTIONS -fno-warn-orphans #-}+module Main (main) where++import Control.Exception(evaluate)+import Control.DeepSeq (rnf)++import Criterion.Main(bench, bgroup, defaultMain, nf)++import Data.Foldable.Levenshtein(levenshteinDistance)++smallA :: [Int]+smallB :: [Int]++smallA = [0, 5 .. 100]+smallB = [0, 3 .. 72]++bigA :: [Int]+bigA = [0, 5 .. 10000]++bigB :: [Int]+bigB = [0, 3 .. 7200]++levInt :: ([Int], [Int]) -> Int+levInt = uncurry levenshteinDistance++main :: IO ()+main = do+  evaluate (rnf smallA)+  evaluate (rnf smallB)++  evaluate (rnf bigA)+  evaluate (rnf bigB)++  defaultMain+    [ bgroup "same"+      [ bgroup "small"+        [ bench "lib" $ (nf levInt) (smallA, smallA)+        , bench "lib" $ (nf levInt) (smallB, smallB)+        ]+      , bgroup "big"+        [ bench "lib" $ (nf levInt) (bigA, bigA)+        , bench "lib" $ (nf levInt) (bigB, bigB)+        ]+      ]+    , bgroup "different"+      [ bgroup "small"+        [ bench "lib" $ (nf levInt) (smallA, smallB)+        , bench "lib" $ (nf levInt) (smallB, smallA)+        ]+      , bgroup "mixed"+        [ bench "lib" $ (nf levInt) (smallA, bigB)+        , bench "lib" $ (nf levInt) (bigB, smallA)+        , bench "lib" $ (nf levInt) (smallA, bigB)+        , bench "lib" $ (nf levInt) (bigB, smallA)+        , bench "lib" $ (nf levInt) (smallB, bigB)+        , bench "lib" $ (nf levInt) (bigB, smallB)+        , bench "lib" $ (nf levInt) (smallB, bigA)+        , bench "lib" $ (nf levInt) (bigA, smallB)+        ]+      , bgroup "big"+        [ bench "lib" $ (nf levInt) (bigA, bigB)+        , bench "lib" $ (nf levInt) (bigB, bigA)+        ]+      ]+    ]

@@ -1,5 +1,5 @@ name:                levenshtein-version:             0.1.3.0+version:             0.2.0.0 synopsis:            Calculate the edit distance between two foldables. description:   A package to determine the edit distance between two 'Foldable's.@@ -28,7 +28,7 @@     , binary >= 0.2     , hashable >=1.2.7.0     , deepseq >=1.4.3.0-    , data-default >=0.2+    , data-default-class >=0.0.1     , QuickCheck   default-language:    Haskell2010 @@ -45,6 +45,7 @@   build-depends:       base     , levenshtein+    , data-default-class >=0.0.1     , hspec ==2.*     , QuickCheck >=2.13   build-tool-depends:@@ -57,3 +58,17 @@                      -Wincomplete-record-updates                      -Wincomplete-uni-patterns                      -Wredundant-constraints++benchmark damerau+  default-language: Haskell2010+  type:             exitcode-stdio-1.0+  main-is:          levenshtein-bench.hs+  hs-source-dirs:   bench+  ghc-options:      -Wall -threaded++  -- dependencies from library+  build-depends:+      base+    , deepseq+    , levenshtein+    , criterion >=0.4.0.0

@@ -15,15 +15,15 @@  module Data.Foldable.Levenshtein (     -- * Calculate the Levenshtein distance-    genericLevenshteinDistance, genericLevenshteinDistance', levenshteinDistance, levenshteinDistance'+    genericLevenshteinDistance, genericLevenshteinDistance', genericLevenshteinDistanceWithScore, genericLevenshteinDistanceWithScore', levenshteinDistance, levenshteinDistance'     -- * Obtain the Levenshtein distance together with the path of 'Edit's-  , genericLevenshtein, genericLevenshtein', levenshtein, levenshtein'+  , genericLevenshtein, genericLevenshtein', genericLevenshteinWithScore, genericLevenshteinWithScore', levenshtein, levenshtein'     -- * Obtain the Levenshtein distance together with a reversed path of 'Edit's-  , genericReversedLevenshtein, genericReversedLevenshtein', reversedLevenshtein, reversedLevenshtein'+  , genericReversedLevenshtein, genericReversedLevenshtein', genericReversedLevenshteinWithScore, genericReversedLevenshteinWithScore', reversedLevenshtein, reversedLevenshtein'     -- * Data type to present modifications from one 'Foldable' to another.   , Edit(Add, Rem, Copy, Swap), Edits, applyEdits     -- * Present the modification costs-  , EditScore(editAdd, editRemove, editReplace, editTranspose), editCost, editsCost+  , EditScore(editAdd, editRemove, editReplace, editTranspose), editCost, editsCost, constantEditScore   ) where  import Control.Arrow(second)@@ -31,7 +31,7 @@  import Data.Binary(Binary(put, get), getWord8, putWord8) import Data.Data(Data)-import Data.Default(Default(def))+import Data.Default.Class(Default(def)) import Data.Foldable(toList) import Data.Functor.Classes(Eq1(liftEq), Ord1(liftCompare)) import Data.Hashable(Hashable)@@ -66,7 +66,11 @@   }   deriving (Functor, Generic, Generic1) -constantEditScore :: b -> EditScore a b+-- | A function to construct an 'EditScore' object where the cost of adding, removing, replacing+-- and transposing all have the same given cost.+constantEditScore+  :: b  -- ^ The given cost for all the operations.+  -> EditScore a b  -- ^ The corresponding 'EditScore' object. constantEditScore x = EditScore c1 c1 c2 c2   where c1 = const x         c2 = const c1@@ -254,6 +258,26 @@   -> b  -- ^ The edit distance between the two 'Foldable's. genericLevenshteinDistance = genericLevenshteinDistance' (==) +-- | Calculate the Levenshtein distance with the given 'EditScore' object that determine how costly each edit is.+-- The function determines the minimal score with 'Add', 'Rem', 'Copy' and 'Swap' edits. We determine if two+-- items are the same with the 'Eq' instance for the item type.+genericLevenshteinDistanceWithScore :: (Foldable f, Foldable g, Eq a, Num b, Ord b)+  => EditScore a b  -- ^ The given 'EditScore' object that determines the cost per edit.+  -> f a  -- ^ The given original sequence.+  -> g a  -- ^ The given target sequence.+  -> b  -- ^ The edit distance between the two 'Foldable's.+genericLevenshteinDistanceWithScore = genericLevenshteinDistanceWithScore' (==)++-- | Calculate the Levenshtein distance with the given equivalence relation, and the given 'EditScore' object that determine how costly each edit is.+-- The function determines the minimal score with 'Add', 'Rem', 'Copy' and 'Swap' edits.+genericLevenshteinDistanceWithScore' :: (Foldable f, Foldable g, Num b, Ord b)+  => (a -> a -> Bool)  -- ^ The given equivalence relation to work with.+  -> EditScore a b  -- ^ The given 'EditScore' object that determines the cost per edit.+  -> f a  -- ^ The given original sequence.+  -> g a  -- ^ The given target sequence.+  -> b  -- ^ The edit distance between the two 'Foldable's.+genericLevenshteinDistanceWithScore' cmp (EditScore ad rm sw _) = genericLevenshteinDistance' cmp ad rm sw+ -- | A function to determine the /Levenshtein distance/ by specifying the cost functions of adding, removing and editing characters. This function returns -- the sum of the costs to transform the first 'Foldable' (as list) into the second 'Foldable' (as list). The first parameter is an equivalence relation -- to determine if two items are considered equivalent.@@ -309,6 +333,26 @@   -> (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' (==) +-- | Calculate the Levenshtein distance and the modifications with the given equivalence relation, and the given 'EditScore' object that determine how costly each edit is.+-- The function determines the minimal score with 'Add', 'Rem', 'Copy' and 'Swap' edits.+genericLevenshteinWithScore' :: (Foldable f, Foldable g, Num b, Ord b)+  => (a -> a -> Bool)  -- ^ The given equivalence relation to determine if two items are the same.+  -> EditScore a b  -- ^ The given 'EditScore' object that specifies the cost of each mutation (add, remove, replace).+  -> f a  -- ^ The given original sequence.+  -> g a  -- ^ The given target sequence.+  -> (b, Edits a)  -- ^ A 2-tuple with the edit score as first item, and a list of modifications as second item to transform the first 'Foldable' (as list) to the second 'Foldable' (as list).+genericLevenshteinWithScore' eq (EditScore ad rm sw _) = genericLevenshtein' eq ad rm sw++-- | Calculate the Levenshtein distance and the modifications with the given 'EditScore' object that determine how costly each edit is.+-- The function determines the minimal score with 'Add', 'Rem', 'Copy' and 'Swap' edits. The 'Eq' instance of the elements is used+-- to determine if two items are equivalent.+genericLevenshteinWithScore :: (Foldable f, Foldable g, Eq a, Num b, Ord b)+  => EditScore a b  -- ^ The given 'EditScore' object that specifies the cost of each mutation (add, remove, replace).+  -> f a  -- ^ The given original sequence.+  -> g a  -- ^ The given target sequence.+  -> (b, Edits a)  -- ^ A 2-tuple with the edit score as first item, and a list of modifications as second item to transform the first 'Foldable' (as list) to the second 'Foldable' (as list).+genericLevenshteinWithScore = genericLevenshteinWithScore' (==)+ -- | A function to determine the /Levenshtein distance/ together with a list of 'Edit's -- to apply to convert the first 'Foldable' (as list) into the second item (as list) -- in /reversed/ order. The cost functions of adding, removing and editing characters@@ -350,3 +394,23 @@   -> g a  -- ^ The given target sequence.   -> (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' (==)++-- | Calculate the Levenshtein distance and the modifications with the given equivalence relation, and the given 'EditScore' object that determine how costly each edit is.+-- The function determines the minimal score with 'Add', 'Rem', 'Copy' and 'Swap' edits.+genericReversedLevenshteinWithScore' :: (Foldable f, Foldable g, Num b, Ord b)+  => (a -> a -> Bool)  -- ^ The given equivalence relation to determine if two items are the same.+  -> EditScore a b  -- ^ The given 'EditScore' object that specifies the cost of each mutation (add, remove, replace).+  -> f a  -- ^ The given original sequence.+  -> g a  -- ^ The given target sequence.+  -> (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).+genericReversedLevenshteinWithScore' cmp (EditScore ad rm sw _) = genericReversedLevenshtein' cmp ad rm sw++-- | Calculate the Levenshtein distance and the modifications with the given 'EditScore' object that determine how costly each edit is.+-- The function determines the minimal score with 'Add', 'Rem', 'Copy' and 'Swap' edits. The 'Eq' instance of the items will determine+-- the equivalence relation.+genericReversedLevenshteinWithScore :: (Foldable f, Foldable g, Eq a, Num b, Ord b)+  => EditScore a b  -- ^ The given 'EditScore' object that specifies the cost of each mutation (add, remove, replace).+  -> f a  -- ^ The given original sequence.+  -> g a  -- ^ The given target sequence.+  -> (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).+genericReversedLevenshteinWithScore = genericReversedLevenshteinWithScore' (==)

@@ -4,7 +4,8 @@     spec   ) where -import Data.Foldable.Levenshtein(Edits, applyEdits, genericLevenshteinDistance, genericLevenshteinDistance', levenshteinDistance, levenshteinDistance', genericLevenshtein, genericLevenshtein', levenshtein, levenshtein', genericReversedLevenshtein, genericReversedLevenshtein', reversedLevenshtein, reversedLevenshtein')+import Data.Default.Class(def)+import Data.Foldable.Levenshtein(Edits, editsCost, applyEdits, genericLevenshteinDistance, genericLevenshteinDistance', genericLevenshteinDistanceWithScore, genericLevenshteinDistanceWithScore', levenshteinDistance, levenshteinDistance', genericLevenshtein, genericLevenshtein', genericLevenshteinWithScore, genericLevenshteinWithScore', levenshtein, levenshtein', genericReversedLevenshtein, genericReversedLevenshtein', genericReversedLevenshteinWithScore, genericReversedLevenshteinWithScore', reversedLevenshtein, reversedLevenshtein', constantEditScore)  import Test.Hspec(Spec, it) import Test.QuickCheck(maxSuccess, property, quickCheckWith, stdArgs)@@ -21,6 +22,9 @@   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 "Check if the score edit is linear" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (checkLinearCost @ Int)))+  it "Check if a linear modification yields the same edits" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (checkOptimalPathSame @ Int)))+  it "Check if a linear fmap yields the same edits" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (checkOptimalPathSameLinearFmap @ 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)))@@ -28,6 +32,9 @@   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 "Check if the score edit is linear" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (checkLinearCost @ Char)))+  it "Check if a linear modification yields the same edits" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (checkOptimalPathSame @ Char)))+  it "Check if a linear fmap yields the same edits" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (checkOptimalPathSameLinearFmap @ 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)))@@ -35,24 +42,48 @@   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)))+  it "Check if the score edit is linear" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (checkLinearCost @ Bool)))+  it "Check if a linear modification yields the same edits" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (checkOptimalPathSame @ Bool)))+  it "Check if a linear fmap yields the same edits" (quickCheckWith stdArgs { maxSuccess = ntimes } (property (checkOptimalPathSameLinearFmap @ 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+                      && dh == di && di == dj && dj == dk && dk == dl && dl == dm && dm == dn+                      && dn == do' && do' == dp && dp == dq && dq == dr+                      && efa == efb && efb == efc && efc == efd && efd == efe && efe == eff+                      && reverse eff == era && era == erb && erb == erc && erc == erd+                      && erd == ere && ere == erf+                      && editsCost def efa == editsCost @[] @Int def era && editsCost @[] @Int def efa == da   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)+        de = genericLevenshteinDistanceWithScore def xs ys :: Int+        df = genericLevenshteinDistanceWithScore' (==) def xs ys :: Int+        (dg, efa) = genericLevenshtein (const 1) (const 1) (const (const 1)) xs ys :: (Int, Edits a)+        (dh, efb) = genericLevenshtein' (==) (const 1) (const 1) (const (const 1)) xs ys :: (Int, Edits a)+        (di, efc) = genericLevenshteinWithScore def xs ys :: (Int, Edits a)+        (dj, efd) = genericLevenshteinWithScore' (==) def xs ys :: (Int, Edits a)+        (dk, efe) = levenshtein xs ys :: (Int, Edits a)+        (dl, eff) = levenshtein' (==) xs ys :: (Int, Edits a)+        (dm, era) = genericReversedLevenshtein (const 1) (const 1) (const (const 1)) xs ys :: (Int, Edits a)+        (dn, erb) = genericReversedLevenshtein' (==) (const 1) (const 1) (const (const 1)) xs ys :: (Int, Edits a)+        (do', erc) = genericReversedLevenshteinWithScore def xs ys :: (Int, Edits a)+        (dp, erd) = genericReversedLevenshteinWithScore' (==) def xs ys :: (Int, Edits a)+        (dq, ere) = reversedLevenshtein xs ys :: (Int, Edits a)+        (dr, erf) = reversedLevenshtein' (==) xs ys :: (Int, Edits a) +checkLinearCost :: forall a . Eq a => Int -> [a] -> [a] -> Bool+checkLinearCost n' xs ys = (genericLevenshteinDistanceWithScore def xs ys) * n == genericLevenshteinDistanceWithScore (constantEditScore n) xs ys+  where n = abs n' + 1++checkOptimalPathSame :: forall a . Eq a => Int -> [a] -> [a] -> Bool+checkOptimalPathSame n' xs ys = snd (genericLevenshteinWithScore @[] @[] @a @Int def xs ys) == snd (genericLevenshteinWithScore (constantEditScore n) xs ys)+  where n = abs n' + 1++checkOptimalPathSameLinearFmap :: forall a . Eq a => Int -> [a] -> [a] -> Bool+checkOptimalPathSameLinearFmap n' xs ys = snd (genericLevenshteinWithScore @[] @[] @a @Int def xs ys) == snd (genericLevenshteinWithScore ((n*) <$> def) xs ys)+  where n = abs n' + 1  lowerBoundLengthDiff :: forall a . Eq a => [a] -> [a] -> Bool lowerBoundLengthDiff xs ys = abs (length xs - length ys) <= levenshteinDistance xs ys