{-# LANGUAGE CPP, DeriveDataTypeable, DeriveGeneric, DeriveTraversable, Safe #-}
module Data.Foldable.Levenshtein (
genericLevenshteinDistance, genericLevenshteinDistance', genericLevenshteinDistanceWithScore, genericLevenshteinDistanceWithScore', levenshteinDistance, levenshteinDistance'
, genericLevenshtein, genericLevenshtein', genericLevenshteinWithScore, genericLevenshteinWithScore', levenshtein, levenshtein'
, genericReversedLevenshtein, genericReversedLevenshtein', genericReversedLevenshteinWithScore, genericReversedLevenshteinWithScore', reversedLevenshtein, reversedLevenshtein'
, Edit(Add, Rem, Copy, Swap), Edits, applyEdits
, EditScore(editAdd, editRemove, editReplace, editTranspose), editCost, editsCost, constantEditScore
) where
import Control.Arrow(second)
import Control.DeepSeq(NFData, NFData1)
import Data.Binary(Binary(put, get), getWord8, putWord8)
import Data.Data(Data)
import Data.Default.Class(Default(def))
import Data.Foldable(toList)
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)
import Test.QuickCheck(oneof)
import Test.QuickCheck.Arbitrary(Arbitrary(arbitrary), Arbitrary1(liftArbitrary), arbitrary1)
_defaddrem :: Num b => a -> b
_defaddrem :: a -> b
_defaddrem = b -> a -> b
forall a b. a -> b -> a
const b
1
_defswap :: Num b => a -> a -> b
_defswap :: a -> a -> b
_defswap = (a -> b) -> a -> a -> b
forall a b. a -> b -> a
const a -> b
forall b a. Num b => a -> b
_defaddrem
_addDefaults :: Num b => ((a -> b) -> (a -> b) -> (a -> a -> b) -> c) -> c
_addDefaults :: ((a -> b) -> (a -> b) -> (a -> a -> b) -> c) -> c
_addDefaults (a -> b) -> (a -> b) -> (a -> a -> b) -> c
f = (a -> b) -> (a -> b) -> (a -> a -> b) -> c
f a -> b
forall b a. Num b => a -> b
_defaddrem a -> b
forall b a. Num b => a -> b
_defaddrem a -> a -> b
forall b a. Num b => a -> a -> b
_defswap
data EditScore a b
= EditScore {
EditScore a b -> a -> b
editAdd :: a -> b
, EditScore a b -> a -> b
editRemove :: a -> b
, EditScore a b -> a -> a -> b
editReplace :: a -> a -> b
, EditScore a b -> a -> a -> b
editTranspose :: a -> a -> b
}
deriving (a -> EditScore a b -> EditScore a a
(a -> b) -> EditScore a a -> EditScore a b
(forall a b. (a -> b) -> EditScore a a -> EditScore a b)
-> (forall a b. a -> EditScore a b -> EditScore a a)
-> Functor (EditScore a)
forall a b. a -> EditScore a b -> EditScore a a
forall a b. (a -> b) -> EditScore a a -> EditScore a b
forall a a b. a -> EditScore a b -> EditScore a a
forall a a b. (a -> b) -> EditScore a a -> EditScore a b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> EditScore a b -> EditScore a a
$c<$ :: forall a a b. a -> EditScore a b -> EditScore a a
fmap :: (a -> b) -> EditScore a a -> EditScore a b
$cfmap :: forall a a b. (a -> b) -> EditScore a a -> EditScore a b
Functor, (forall x. EditScore a b -> Rep (EditScore a b) x)
-> (forall x. Rep (EditScore a b) x -> EditScore a b)
-> Generic (EditScore a b)
forall x. Rep (EditScore a b) x -> EditScore a b
forall x. EditScore a b -> Rep (EditScore a b) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a b x. Rep (EditScore a b) x -> EditScore a b
forall a b x. EditScore a b -> Rep (EditScore a b) x
$cto :: forall a b x. Rep (EditScore a b) x -> EditScore a b
$cfrom :: forall a b x. EditScore a b -> Rep (EditScore a b) x
Generic, (forall a. EditScore a a -> Rep1 (EditScore a) a)
-> (forall a. Rep1 (EditScore a) a -> EditScore a a)
-> Generic1 (EditScore a)
forall a. Rep1 (EditScore a) a -> EditScore a a
forall a. EditScore a a -> Rep1 (EditScore a) a
forall a a. Rep1 (EditScore a) a -> EditScore a a
forall a a. EditScore a a -> Rep1 (EditScore a) a
forall k (f :: k -> *).
(forall (a :: k). f a -> Rep1 f a)
-> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
$cto1 :: forall a a. Rep1 (EditScore a) a -> EditScore a a
$cfrom1 :: forall a a. EditScore a a -> Rep1 (EditScore a) a
Generic1)
constantEditScore
:: b
-> EditScore a b
constantEditScore :: b -> EditScore a b
constantEditScore b
x = (a -> b)
-> (a -> b) -> (a -> a -> b) -> (a -> a -> b) -> EditScore a b
forall a b.
(a -> b)
-> (a -> b) -> (a -> a -> b) -> (a -> a -> b) -> EditScore a b
EditScore a -> b
forall b. b -> b
c1 a -> b
forall b. b -> b
c1 a -> a -> b
forall b b. b -> b -> b
c2 a -> a -> b
forall b b. b -> b -> b
c2
where c1 :: b -> b
c1 = b -> b -> b
forall a b. a -> b -> a
const b
x
c2 :: b -> b -> b
c2 = (b -> b) -> b -> b -> b
forall a b. a -> b -> a
const b -> b
forall b. b -> b
c1
instance Num b => Default (EditScore a b) where
def :: EditScore a b
def = b -> EditScore a b
forall b a. b -> EditScore a b
constantEditScore b
1
data Edit a
= Add a
| Rem a
| Copy a
| Swap a a
| Transpose a a
deriving (Typeable (Edit a)
DataType
Constr
Typeable (Edit a)
-> (forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Edit a -> c (Edit a))
-> (forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Edit a))
-> (Edit a -> Constr)
-> (Edit a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Edit a)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Edit a)))
-> ((forall b. Data b => b -> b) -> Edit a -> Edit a)
-> (forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Edit a -> r)
-> (forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Edit a -> r)
-> (forall u. (forall d. Data d => d -> u) -> Edit a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> Edit a -> u)
-> (forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Edit a -> m (Edit a))
-> (forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Edit a -> m (Edit a))
-> (forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Edit a -> m (Edit a))
-> Data (Edit a)
Edit a -> DataType
Edit a -> Constr
(forall d. Data d => c (t d)) -> Maybe (c (Edit a))
(forall b. Data b => b -> b) -> Edit a -> Edit a
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Edit a -> c (Edit a)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Edit a)
forall a. Data a => Typeable (Edit a)
forall a. Data a => Edit a -> DataType
forall a. Data a => Edit a -> Constr
forall a.
Data a =>
(forall b. Data b => b -> b) -> Edit a -> Edit a
forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> Edit a -> u
forall a u. Data a => (forall d. Data d => d -> u) -> Edit a -> [u]
forall a r r'.
Data a =>
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Edit a -> r
forall a r r'.
Data a =>
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Edit a -> r
forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> Edit a -> m (Edit a)
forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Edit a -> m (Edit a)
forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Edit a)
forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Edit a -> c (Edit a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Edit a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Edit a))
forall a.
Typeable a
-> (forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> Edit a -> u
forall u. (forall d. Data d => d -> u) -> Edit a -> [u]
forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Edit a -> r
forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Edit a -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Edit a -> m (Edit a)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Edit a -> m (Edit a)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Edit a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Edit a -> c (Edit a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Edit a))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Edit a))
$cTranspose :: Constr
$cSwap :: Constr
$cCopy :: Constr
$cRem :: Constr
$cAdd :: Constr
$tEdit :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> Edit a -> m (Edit a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Edit a -> m (Edit a)
gmapMp :: (forall d. Data d => d -> m d) -> Edit a -> m (Edit a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Edit a -> m (Edit a)
gmapM :: (forall d. Data d => d -> m d) -> Edit a -> m (Edit a)
$cgmapM :: forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> Edit a -> m (Edit a)
gmapQi :: Int -> (forall d. Data d => d -> u) -> Edit a -> u
$cgmapQi :: forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> Edit a -> u
gmapQ :: (forall d. Data d => d -> u) -> Edit a -> [u]
$cgmapQ :: forall a u. Data a => (forall d. Data d => d -> u) -> Edit a -> [u]
gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Edit a -> r
$cgmapQr :: forall a r r'.
Data a =>
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Edit a -> r
gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Edit a -> r
$cgmapQl :: forall a r r'.
Data a =>
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Edit a -> r
gmapT :: (forall b. Data b => b -> b) -> Edit a -> Edit a
$cgmapT :: forall a.
Data a =>
(forall b. Data b => b -> b) -> Edit a -> Edit a
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Edit a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Edit a))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (Edit a))
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Edit a))
dataTypeOf :: Edit a -> DataType
$cdataTypeOf :: forall a. Data a => Edit a -> DataType
toConstr :: Edit a -> Constr
$ctoConstr :: forall a. Data a => Edit a -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Edit a)
$cgunfold :: forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Edit a)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Edit a -> c (Edit a)
$cgfoldl :: forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Edit a -> c (Edit a)
$cp1Data :: forall a. Data a => Typeable (Edit a)
Data, Edit a -> Edit a -> Bool
(Edit a -> Edit a -> Bool)
-> (Edit a -> Edit a -> Bool) -> Eq (Edit a)
forall a. Eq a => Edit a -> Edit a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Edit a -> Edit a -> Bool
$c/= :: forall a. Eq a => Edit a -> Edit a -> Bool
== :: Edit a -> Edit a -> Bool
$c== :: forall a. Eq a => Edit a -> Edit a -> Bool
Eq, Edit a -> Bool
(a -> m) -> Edit a -> m
(a -> b -> b) -> b -> Edit a -> b
(forall m. Monoid m => Edit m -> m)
-> (forall m a. Monoid m => (a -> m) -> Edit a -> m)
-> (forall m a. Monoid m => (a -> m) -> Edit a -> m)
-> (forall a b. (a -> b -> b) -> b -> Edit a -> b)
-> (forall a b. (a -> b -> b) -> b -> Edit a -> b)
-> (forall b a. (b -> a -> b) -> b -> Edit a -> b)
-> (forall b a. (b -> a -> b) -> b -> Edit a -> b)
-> (forall a. (a -> a -> a) -> Edit a -> a)
-> (forall a. (a -> a -> a) -> Edit a -> a)
-> (forall a. Edit a -> [a])
-> (forall a. Edit a -> Bool)
-> (forall a. Edit a -> Int)
-> (forall a. Eq a => a -> Edit a -> Bool)
-> (forall a. Ord a => Edit a -> a)
-> (forall a. Ord a => Edit a -> a)
-> (forall a. Num a => Edit a -> a)
-> (forall a. Num a => Edit a -> a)
-> Foldable Edit
forall a. Eq a => a -> Edit a -> Bool
forall a. Num a => Edit a -> a
forall a. Ord a => Edit a -> a
forall m. Monoid m => Edit m -> m
forall a. Edit a -> Bool
forall a. Edit a -> Int
forall a. Edit a -> [a]
forall a. (a -> a -> a) -> Edit a -> a
forall m a. Monoid m => (a -> m) -> Edit a -> m
forall b a. (b -> a -> b) -> b -> Edit a -> b
forall a b. (a -> b -> b) -> b -> Edit a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: Edit a -> a
$cproduct :: forall a. Num a => Edit a -> a
sum :: Edit a -> a
$csum :: forall a. Num a => Edit a -> a
minimum :: Edit a -> a
$cminimum :: forall a. Ord a => Edit a -> a
maximum :: Edit a -> a
$cmaximum :: forall a. Ord a => Edit a -> a
elem :: a -> Edit a -> Bool
$celem :: forall a. Eq a => a -> Edit a -> Bool
length :: Edit a -> Int
$clength :: forall a. Edit a -> Int
null :: Edit a -> Bool
$cnull :: forall a. Edit a -> Bool
toList :: Edit a -> [a]
$ctoList :: forall a. Edit a -> [a]
foldl1 :: (a -> a -> a) -> Edit a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Edit a -> a
foldr1 :: (a -> a -> a) -> Edit a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Edit a -> a
foldl' :: (b -> a -> b) -> b -> Edit a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Edit a -> b
foldl :: (b -> a -> b) -> b -> Edit a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Edit a -> b
foldr' :: (a -> b -> b) -> b -> Edit a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Edit a -> b
foldr :: (a -> b -> b) -> b -> Edit a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Edit a -> b
foldMap' :: (a -> m) -> Edit a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Edit a -> m
foldMap :: (a -> m) -> Edit a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Edit a -> m
fold :: Edit m -> m
$cfold :: forall m. Monoid m => Edit m -> m
Foldable, a -> Edit b -> Edit a
(a -> b) -> Edit a -> Edit b
(forall a b. (a -> b) -> Edit a -> Edit b)
-> (forall a b. a -> Edit b -> Edit a) -> Functor Edit
forall a b. a -> Edit b -> Edit a
forall a b. (a -> b) -> Edit a -> Edit b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Edit b -> Edit a
$c<$ :: forall a b. a -> Edit b -> Edit a
fmap :: (a -> b) -> Edit a -> Edit b
$cfmap :: forall a b. (a -> b) -> Edit a -> Edit b
Functor, (forall x. Edit a -> Rep (Edit a) x)
-> (forall x. Rep (Edit a) x -> Edit a) -> Generic (Edit a)
forall x. Rep (Edit a) x -> Edit a
forall x. Edit a -> Rep (Edit a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (Edit a) x -> Edit a
forall a x. Edit a -> Rep (Edit a) x
$cto :: forall a x. Rep (Edit a) x -> Edit a
$cfrom :: forall a x. Edit a -> Rep (Edit a) x
Generic, (forall a. Edit a -> Rep1 Edit a)
-> (forall a. Rep1 Edit a -> Edit a) -> Generic1 Edit
forall a. Rep1 Edit a -> Edit a
forall a. Edit a -> Rep1 Edit a
forall k (f :: k -> *).
(forall (a :: k). f a -> Rep1 f a)
-> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
$cto1 :: forall a. Rep1 Edit a -> Edit a
$cfrom1 :: forall a. Edit a -> Rep1 Edit a
Generic1, Eq (Edit a)
Eq (Edit a)
-> (Edit a -> Edit a -> Ordering)
-> (Edit a -> Edit a -> Bool)
-> (Edit a -> Edit a -> Bool)
-> (Edit a -> Edit a -> Bool)
-> (Edit a -> Edit a -> Bool)
-> (Edit a -> Edit a -> Edit a)
-> (Edit a -> Edit a -> Edit a)
-> Ord (Edit a)
Edit a -> Edit a -> Bool
Edit a -> Edit a -> Ordering
Edit a -> Edit a -> Edit a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (Edit a)
forall a. Ord a => Edit a -> Edit a -> Bool
forall a. Ord a => Edit a -> Edit a -> Ordering
forall a. Ord a => Edit a -> Edit a -> Edit a
min :: Edit a -> Edit a -> Edit a
$cmin :: forall a. Ord a => Edit a -> Edit a -> Edit a
max :: Edit a -> Edit a -> Edit a
$cmax :: forall a. Ord a => Edit a -> Edit a -> Edit a
>= :: Edit a -> Edit a -> Bool
$c>= :: forall a. Ord a => Edit a -> Edit a -> Bool
> :: Edit a -> Edit a -> Bool
$c> :: forall a. Ord a => Edit a -> Edit a -> Bool
<= :: Edit a -> Edit a -> Bool
$c<= :: forall a. Ord a => Edit a -> Edit a -> Bool
< :: Edit a -> Edit a -> Bool
$c< :: forall a. Ord a => Edit a -> Edit a -> Bool
compare :: Edit a -> Edit a -> Ordering
$ccompare :: forall a. Ord a => Edit a -> Edit a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (Edit a)
Ord, ReadPrec [Edit a]
ReadPrec (Edit a)
Int -> ReadS (Edit a)
ReadS [Edit a]
(Int -> ReadS (Edit a))
-> ReadS [Edit a]
-> ReadPrec (Edit a)
-> ReadPrec [Edit a]
-> Read (Edit a)
forall a. Read a => ReadPrec [Edit a]
forall a. Read a => ReadPrec (Edit a)
forall a. Read a => Int -> ReadS (Edit a)
forall a. Read a => ReadS [Edit a]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [Edit a]
$creadListPrec :: forall a. Read a => ReadPrec [Edit a]
readPrec :: ReadPrec (Edit a)
$creadPrec :: forall a. Read a => ReadPrec (Edit a)
readList :: ReadS [Edit a]
$creadList :: forall a. Read a => ReadS [Edit a]
readsPrec :: Int -> ReadS (Edit a)
$creadsPrec :: forall a. Read a => Int -> ReadS (Edit a)
Read, Int -> Edit a -> ShowS
[Edit a] -> ShowS
Edit a -> String
(Int -> Edit a -> ShowS)
-> (Edit a -> String) -> ([Edit a] -> ShowS) -> Show (Edit a)
forall a. Show a => Int -> Edit a -> ShowS
forall a. Show a => [Edit a] -> ShowS
forall a. Show a => Edit a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Edit a] -> ShowS
$cshowList :: forall a. Show a => [Edit a] -> ShowS
show :: Edit a -> String
$cshow :: forall a. Show a => Edit a -> String
showsPrec :: Int -> Edit a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Edit a -> ShowS
Show, Functor Edit
Foldable Edit
Functor Edit
-> Foldable Edit
-> (forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Edit a -> f (Edit b))
-> (forall (f :: * -> *) a.
Applicative f =>
Edit (f a) -> f (Edit a))
-> (forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Edit a -> m (Edit b))
-> (forall (m :: * -> *) a. Monad m => Edit (m a) -> m (Edit a))
-> Traversable Edit
(a -> f b) -> Edit a -> f (Edit b)
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => Edit (m a) -> m (Edit a)
forall (f :: * -> *) a. Applicative f => Edit (f a) -> f (Edit a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Edit a -> m (Edit b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Edit a -> f (Edit b)
sequence :: Edit (m a) -> m (Edit a)
$csequence :: forall (m :: * -> *) a. Monad m => Edit (m a) -> m (Edit a)
mapM :: (a -> m b) -> Edit a -> m (Edit b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Edit a -> m (Edit b)
sequenceA :: Edit (f a) -> f (Edit a)
$csequenceA :: forall (f :: * -> *) a. Applicative f => Edit (f a) -> f (Edit a)
traverse :: (a -> f b) -> Edit a -> f (Edit b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Edit a -> f (Edit b)
$cp2Traversable :: Foldable Edit
$cp1Traversable :: Functor Edit
Traversable)
instance Arbitrary1 Edit where
liftArbitrary :: Gen a -> Gen (Edit a)
liftArbitrary Gen a
arb = [Gen (Edit a)] -> Gen (Edit a)
forall a. [Gen a] -> Gen a
oneof [a -> Edit a
forall a. a -> Edit a
Add (a -> Edit a) -> Gen a -> Gen (Edit a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Gen a
arb, a -> Edit a
forall a. a -> Edit a
Rem (a -> Edit a) -> Gen a -> Gen (Edit a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Gen a
arb, a -> Edit a
forall a. a -> Edit a
Copy (a -> Edit a) -> Gen a -> Gen (Edit a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Gen a
arb, a -> a -> Edit a
forall a. a -> a -> Edit a
Swap (a -> a -> Edit a) -> Gen a -> Gen (a -> Edit a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Gen a
arb Gen (a -> Edit a) -> Gen a -> Gen (Edit a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Gen a
arb]
instance Arbitrary a => Arbitrary (Edit a) where
arbitrary :: Gen (Edit a)
arbitrary = Gen (Edit a)
forall (f :: * -> *) a. (Arbitrary1 f, Arbitrary a) => Gen (f a)
arbitrary1
instance Binary a => Binary (Edit a) where
put :: Edit a -> Put
put (Add a
x) = Word8 -> Put
putWord8 Word8
0 Put -> Put -> Put
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> a -> Put
forall t. Binary t => t -> Put
put a
x
put (Rem a
x) = Word8 -> Put
putWord8 Word8
1 Put -> Put -> Put
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> a -> Put
forall t. Binary t => t -> Put
put a
x
put (Copy a
x) = Word8 -> Put
putWord8 Word8
2 Put -> Put -> Put
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> a -> Put
forall t. Binary t => t -> Put
put a
x
put (Swap a
xa a
xb) = Word8 -> Put
putWord8 Word8
3 Put -> Put -> Put
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> a -> Put
forall t. Binary t => t -> Put
put a
xa Put -> Put -> Put
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> a -> Put
forall t. Binary t => t -> Put
put a
xb
put (Transpose a
xa a
xb) = Word8 -> Put
putWord8 Word8
4 Put -> Put -> Put
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> a -> Put
forall t. Binary t => t -> Put
put a
xa Put -> Put -> Put
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> a -> Put
forall t. Binary t => t -> Put
put a
xb
get :: Get (Edit a)
get = do
Word8
tp <- Get Word8
getWord8
case Word8
tp of
Word8
0 -> a -> Edit a
forall a. a -> Edit a
Add (a -> Edit a) -> Get a -> Get (Edit a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Get a
forall t. Binary t => Get t
get
Word8
1 -> a -> Edit a
forall a. a -> Edit a
Rem (a -> Edit a) -> Get a -> Get (Edit a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Get a
forall t. Binary t => Get t
get
Word8
2 -> a -> Edit a
forall a. a -> Edit a
Copy (a -> Edit a) -> Get a -> Get (Edit a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Get a
forall t. Binary t => Get t
get
Word8
3 -> a -> a -> Edit a
forall a. a -> a -> Edit a
Swap (a -> a -> Edit a) -> Get a -> Get (a -> Edit a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Get a
forall t. Binary t => Get t
get Get (a -> Edit a) -> Get a -> Get (Edit a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Get a
forall t. Binary t => Get t
get
Word8
4 -> a -> a -> Edit a
forall a. a -> a -> Edit a
Transpose (a -> a -> Edit a) -> Get a -> Get (a -> Edit a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Get a
forall t. Binary t => Get t
get Get (a -> Edit a) -> Get a -> Get (Edit a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Get a
forall t. Binary t => Get t
get
Word8
_ -> String -> Get (Edit a)
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String
"The number " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Word8 -> String
forall a. Show a => a -> String
show Word8
tp String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" is not a valid Edit item.")
instance Eq1 Edit where
liftEq :: (a -> b -> Bool) -> Edit a -> Edit b -> Bool
liftEq a -> b -> Bool
eq = Edit a -> Edit b -> Bool
go
where go :: Edit a -> Edit b -> Bool
go (Add a
xa) (Add b
xb) = a -> b -> Bool
eq a
xa b
xb
go (Rem a
xa) (Rem b
xb) = a -> b -> Bool
eq a
xa b
xb
go (Copy a
xa) (Copy b
xb) = a -> b -> Bool
eq a
xa b
xb
go (Swap a
xa a
ya) (Swap b
xb b
yb) = a -> b -> Bool
eq a
xa b
xb Bool -> Bool -> Bool
&& a -> b -> Bool
eq a
ya b
yb
go (Transpose a
xa a
ya) (Transpose b
xb b
yb) = a -> b -> Bool
eq a
xa b
xb Bool -> Bool -> Bool
&& a -> b -> Bool
eq a
ya b
yb
go Edit a
_ Edit b
_ = Bool
False
instance Hashable a => Hashable (Edit a)
instance Hashable1 Edit
instance NFData a => NFData (Edit a)
instance NFData1 Edit
instance Ord1 Edit where
liftCompare :: (a -> b -> Ordering) -> Edit a -> Edit b -> Ordering
liftCompare a -> b -> Ordering
cmp = Edit a -> Edit b -> Ordering
go
where go :: Edit a -> Edit b -> Ordering
go (Add a
a) (Add b
b) = a -> b -> Ordering
cmp a
a b
b
go (Add a
_) Edit b
_ = Ordering
LT
go Edit a
_ (Add b
_) = Ordering
GT
go (Rem a
a) (Rem b
b) = a -> b -> Ordering
cmp a
a b
b
go (Rem a
_) Edit b
_ = Ordering
LT
go Edit a
_ (Rem b
_) = Ordering
GT
go (Copy a
a) (Copy b
b) = a -> b -> Ordering
cmp a
a b
b
go (Copy a
_) Edit b
_ = Ordering
LT
go Edit a
_ (Copy b
_) = Ordering
GT
go (Swap a
xa a
ya) (Swap b
xb b
yb) = a -> b -> Ordering
cmp a
xa b
xb Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> a -> b -> Ordering
cmp a
ya b
yb
go (Swap a
_ a
_) Edit b
_ = Ordering
LT
go Edit a
_ (Swap b
_ b
_) = Ordering
GT
go (Transpose a
xa a
ya) (Transpose b
xb b
yb) = a -> b -> Ordering
cmp a
xa b
xb Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> a -> b -> Ordering
cmp a
ya b
yb
type Edits a = [Edit a]
editCost :: Num b
=> EditScore a b
-> Edit a
-> b
editCost :: EditScore a b -> Edit a -> b
editCost EditScore { editAdd :: forall a b. EditScore a b -> a -> b
editAdd=a -> b
ad, editRemove :: forall a b. EditScore a b -> a -> b
editRemove=a -> b
rm, editReplace :: forall a b. EditScore a b -> a -> a -> b
editReplace=a -> a -> b
rp, editTranspose :: forall a b. EditScore a b -> a -> a -> b
editTranspose=a -> a -> b
tp } = Edit a -> b
go
where go :: Edit a -> b
go (Add a
x) = a -> b
ad a
x
go (Rem a
x) = a -> b
rm a
x
go (Copy a
_) = b
0
go (Swap a
x a
y) = a -> a -> b
rp a
x a
y
go (Transpose a
x a
y) = a -> a -> b
tp a
x a
y
editsCost :: (Foldable f, Num b)
=> EditScore a b
-> f (Edit a)
-> b
editsCost :: EditScore a b -> f (Edit a) -> b
editsCost EditScore a b
es = (Edit a -> b -> b) -> b -> f (Edit a) -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (b -> b -> b
forall a. Num a => a -> a -> a
(+) (b -> b -> b) -> (Edit a -> b) -> Edit a -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. EditScore a b -> Edit a -> b
forall b a. Num b => EditScore a b -> Edit a -> b
editCost EditScore a b
es) b
0
applyEdits :: Eq a
=> Edits a
-> [a]
-> Maybe [a]
applyEdits :: Edits a -> [a] -> Maybe [a]
applyEdits [] [a]
ys = [a] -> Maybe [a]
forall a. a -> Maybe a
Just [a]
ys
applyEdits (Add a
x : Edits a
xs) [a]
ys = (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> Maybe [a] -> Maybe [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Edits a -> [a] -> Maybe [a]
forall a. Eq a => Edits a -> [a] -> Maybe [a]
applyEdits Edits a
xs [a]
ys
applyEdits (Rem a
x : Edits a
xs) (a
y : [a]
ys)
| a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y = Edits a -> [a] -> Maybe [a]
forall a. Eq a => Edits a -> [a] -> Maybe [a]
applyEdits Edits a
xs [a]
ys
applyEdits (Swap a
y a
x : Edits a
xs) (a
y' : [a]
ys)
| a
y a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y' = (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> Maybe [a] -> Maybe [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Edits a -> [a] -> Maybe [a]
forall a. Eq a => Edits a -> [a] -> Maybe [a]
applyEdits Edits a
xs [a]
ys
applyEdits (Copy a
x : Edits a
xs) (a
y : [a]
ys)
| a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y = (a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> Maybe [a] -> Maybe [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Edits a -> [a] -> Maybe [a]
forall a. Eq a => Edits a -> [a] -> Maybe [a]
applyEdits Edits a
xs [a]
ys
applyEdits (Transpose a
xa a
xb : Edits a
xs) (a
ya : a
yb : [a]
ys)
| a
xa a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
yb Bool -> Bool -> Bool
&& a
xb a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
ya = (a
yb a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
ya a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> Maybe [a] -> Maybe [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Edits a -> [a] -> Maybe [a]
forall a. Eq a => Edits a -> [a] -> Maybe [a]
applyEdits Edits a
xs [a]
ys
applyEdits Edits a
_ [a]
_ = Maybe [a]
forall a. Maybe a
Nothing
levenshteinDistance :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
=> f a
-> g a
-> b
levenshteinDistance :: f a -> g a -> b
levenshteinDistance = (a -> a -> Bool) -> f a -> g a -> b
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool) -> f a -> g a -> b
levenshteinDistance' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
levenshtein :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
=> f a
-> g a
-> (b, Edits a)
levenshtein :: f a -> g a -> (b, Edits a)
levenshtein = (a -> a -> Bool) -> f a -> g a -> (b, Edits a)
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool) -> f a -> g a -> (b, Edits a)
levenshtein' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
levenshtein' :: (Foldable f, Foldable g, Num b, Ord b)
=> (a -> a -> Bool)
-> f a
-> g a
-> (b, Edits a)
levenshtein' :: (a -> a -> Bool) -> f a -> g a -> (b, Edits a)
levenshtein' = ((a -> b)
-> (a -> b) -> (a -> a -> b) -> f a -> g a -> (b, Edits a))
-> f a -> g a -> (b, Edits a)
forall b a c.
Num b =>
((a -> b) -> (a -> b) -> (a -> a -> b) -> c) -> c
_addDefaults (((a -> b)
-> (a -> b) -> (a -> a -> b) -> f a -> g a -> (b, Edits a))
-> f a -> g a -> (b, Edits a))
-> ((a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a))
-> (a -> a -> Bool)
-> f a
-> g a
-> (b, Edits a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericLevenshtein'
reversedLevenshtein :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
=> f a
-> g a
-> (b, Edits a)
reversedLevenshtein :: f a -> g a -> (b, Edits a)
reversedLevenshtein = (a -> a -> Bool) -> f a -> g a -> (b, Edits a)
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool) -> f a -> g a -> (b, Edits a)
reversedLevenshtein' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
reversedLevenshtein' :: (Foldable f, Foldable g, Num b, Ord b)
=> (a -> a -> Bool)
-> f a
-> g a
-> (b, Edits a)
reversedLevenshtein' :: (a -> a -> Bool) -> f a -> g a -> (b, Edits a)
reversedLevenshtein' = ((a -> b)
-> (a -> b) -> (a -> a -> b) -> f a -> g a -> (b, Edits a))
-> f a -> g a -> (b, Edits a)
forall b a c.
Num b =>
((a -> b) -> (a -> b) -> (a -> a -> b) -> c) -> c
_addDefaults (((a -> b)
-> (a -> b) -> (a -> a -> b) -> f a -> g a -> (b, Edits a))
-> f a -> g a -> (b, Edits a))
-> ((a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a))
-> (a -> a -> Bool)
-> f a
-> g a
-> (b, Edits a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericReversedLevenshtein'
levenshteinDistance' :: (Foldable f, Foldable g, Num b, Ord b)
=> (a -> a -> Bool)
-> f a
-> g a
-> b
levenshteinDistance' :: (a -> a -> Bool) -> f a -> g a -> b
levenshteinDistance' = ((a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> b)
-> f a -> g a -> b
forall b a c.
Num b =>
((a -> b) -> (a -> b) -> (a -> a -> b) -> c) -> c
_addDefaults (((a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> b)
-> f a -> g a -> b)
-> ((a -> a -> Bool)
-> (a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> b)
-> (a -> a -> Bool)
-> f a
-> g a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Bool)
-> (a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> b
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool)
-> (a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> b
genericLevenshteinDistance'
genericLevenshteinDistance :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
=> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> b
genericLevenshteinDistance :: (a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> b
genericLevenshteinDistance = (a -> a -> Bool)
-> (a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> b
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool)
-> (a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> b
genericLevenshteinDistance' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
genericLevenshteinDistanceWithScore :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
=> EditScore a b
-> f a
-> g a
-> b
genericLevenshteinDistanceWithScore :: EditScore a b -> f a -> g a -> b
genericLevenshteinDistanceWithScore = (a -> a -> Bool) -> EditScore a b -> f a -> g a -> b
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool) -> EditScore a b -> f a -> g a -> b
genericLevenshteinDistanceWithScore' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
genericLevenshteinDistanceWithScore' :: (Foldable f, Foldable g, Num b, Ord b)
=> (a -> a -> Bool)
-> EditScore a b
-> f a
-> g a
-> b
genericLevenshteinDistanceWithScore' :: (a -> a -> Bool) -> EditScore a b -> f a -> g a -> b
genericLevenshteinDistanceWithScore' a -> a -> Bool
cmp (EditScore a -> b
ad a -> b
rm a -> a -> b
sw a -> a -> b
_) = (a -> a -> Bool)
-> (a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> b
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool)
-> (a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> b
genericLevenshteinDistance' a -> a -> Bool
cmp a -> b
ad a -> b
rm a -> a -> b
sw
genericLevenshteinDistance' :: (Foldable f, Foldable g, Num b, Ord b)
=> (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> b
genericLevenshteinDistance' :: (a -> a -> Bool)
-> (a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> b
genericLevenshteinDistance' a -> a -> Bool
eq a -> b
ad a -> b
rm a -> a -> b
sw f a
xs' g a
ys' = [b] -> b
forall a. [a] -> a
last (([b] -> a -> [b]) -> [b] -> f a -> [b]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ([a] -> [b] -> a -> [b]
nextRow [a]
tl) [b]
row0 f a
xs')
where
row0 :: [b]
row0 = (b -> a -> b) -> b -> [a] -> [b]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (\b
w a
i -> b
w b -> b -> b
forall a. Num a => a -> a -> a
+ a -> b
ad a
i) b
0 [a]
tl
nextCell :: a -> b -> a -> b -> b -> b
nextCell a
x b
l a
y b
lt b
t
| a -> a -> Bool
eq a
x a
y = b
lt
| b
scs b -> b -> Bool
forall a. Ord a => a -> a -> Bool
<= b
scr Bool -> Bool -> Bool
&& b
scs b -> b -> Bool
forall a. Ord a => a -> a -> Bool
<= b
sca = b
scs
| b
sca b -> b -> Bool
forall a. Ord a => a -> a -> Bool
<= b
scr = b
sca
| Bool
otherwise = b
scr
where sca :: b
sca = b
l b -> b -> b
forall a. Num a => a -> a -> a
+ a -> b
ad a
y
scr :: b
scr = b
t b -> b -> b
forall a. Num a => a -> a -> a
+ a -> b
rm a
x
scs :: b
scs = b
lt b -> b -> b
forall a. Num a => a -> a -> a
+ a -> a -> b
sw a
x a
y
curryNextCell :: a -> b -> ((a, b), b) -> b
curryNextCell a
x b
l = ((a, b) -> b -> b) -> ((a, b), b) -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((a -> b -> b -> b) -> (a, b) -> b -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (a -> b -> a -> b -> b -> b
nextCell a
x b
l))
nextRow :: [a] -> [b] -> a -> [b]
nextRow [a]
ys da :: [b]
da@(~(b
dn:[b]
ds)) a
x = (b -> ((a, b), b) -> b) -> b -> [((a, b), b)] -> [b]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (a -> b -> ((a, b), b) -> b
curryNextCell a
x) (b
dnb -> b -> b
forall a. Num a => a -> a -> a
+a -> b
rm a
x) ([(a, b)] -> [b] -> [((a, b), b)]
forall a b. [a] -> [b] -> [(a, b)]
zip ([a] -> [b] -> [(a, b)]
forall a b. [a] -> [b] -> [(a, b)]
zip [a]
ys [b]
da) [b]
ds)
tl :: [a]
tl = g a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList g a
ys'
genericLevenshtein' :: (Foldable f, Foldable g, Num b, Ord b)
=> (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericLevenshtein' :: (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericLevenshtein' a -> a -> Bool
eq a -> b
ad a -> b
rm a -> a -> b
sw f a
xs' = (Edits a -> Edits a) -> (b, Edits a) -> (b, Edits a)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second Edits a -> Edits a
forall a. [a] -> [a]
reverse ((b, Edits a) -> (b, Edits a))
-> (g a -> (b, Edits a)) -> g a -> (b, Edits a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericReversedLevenshtein' a -> a -> Bool
eq a -> b
ad a -> b
rm a -> a -> b
sw f a
xs'
genericLevenshtein :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
=> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericLevenshtein :: (a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> (b, Edits a)
genericLevenshtein = (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericLevenshtein' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
genericLevenshteinWithScore' :: (Foldable f, Foldable g, Num b, Ord b)
=> (a -> a -> Bool)
-> EditScore a b
-> f a
-> g a
-> (b, Edits a)
genericLevenshteinWithScore' :: (a -> a -> Bool) -> EditScore a b -> f a -> g a -> (b, Edits a)
genericLevenshteinWithScore' a -> a -> Bool
eq (EditScore a -> b
ad a -> b
rm a -> a -> b
sw a -> a -> b
_) = (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericLevenshtein' a -> a -> Bool
eq a -> b
ad a -> b
rm a -> a -> b
sw
genericLevenshteinWithScore :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
=> EditScore a b
-> f a
-> g a
-> (b, Edits a)
genericLevenshteinWithScore :: EditScore a b -> f a -> g a -> (b, Edits a)
genericLevenshteinWithScore = (a -> a -> Bool) -> EditScore a b -> f a -> g a -> (b, Edits a)
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool) -> EditScore a b -> f a -> g a -> (b, Edits a)
genericLevenshteinWithScore' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
genericReversedLevenshtein' :: (Foldable f, Foldable g, Num b, Ord b)
=> (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericReversedLevenshtein' :: (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericReversedLevenshtein' a -> a -> Bool
eq a -> b
ad a -> b
rm a -> a -> b
sw f a
xs' g a
ys' = [(b, Edits a)] -> (b, Edits a)
forall a. [a] -> a
last (([(b, Edits a)] -> a -> [(b, Edits a)])
-> [(b, Edits a)] -> f a -> [(b, Edits a)]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ([a] -> [(b, Edits a)] -> a -> [(b, Edits a)]
nextRow [a]
tl) [(b, Edits a)]
row0 f a
xs')
where
row0 :: [(b, Edits a)]
row0 = ((b, Edits a) -> a -> (b, Edits a))
-> (b, Edits a) -> [a] -> [(b, Edits a)]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (\(b
w, Edits a
is) a
i -> (b
wb -> b -> b
forall a. Num a => a -> a -> a
+a -> b
ad a
i, a -> Edit a
forall a. a -> Edit a
Add a
iEdit a -> Edits a -> Edits a
forall a. a -> [a] -> [a]
: Edits a
is)) (b
0, []) [a]
tl
nextCell :: a
-> (b, Edits a)
-> a
-> (b, Edits a)
-> (b, Edits a)
-> (b, Edits a)
nextCell a
x (b
l, Edits a
le) a
y (b
lt, Edits a
lte) (b
t, Edits a
te)
| a -> a -> Bool
eq a
x a
y = (b
lt, a -> Edit a
forall a. a -> Edit a
Copy a
x Edit a -> Edits a -> Edits a
forall a. a -> [a] -> [a]
: Edits a
lte)
| b
scs b -> b -> Bool
forall a. Ord a => a -> a -> Bool
<= b
scr Bool -> Bool -> Bool
&& b
scs b -> b -> Bool
forall a. Ord a => a -> a -> Bool
<= b
sca = (b
scs, a -> a -> Edit a
forall a. a -> a -> Edit a
Swap a
x a
yEdit a -> Edits a -> Edits a
forall a. a -> [a] -> [a]
:Edits a
lte)
| b
sca b -> b -> Bool
forall a. Ord a => a -> a -> Bool
<= b
scr = (b
sca, a -> Edit a
forall a. a -> Edit a
Add a
yEdit a -> Edits a -> Edits a
forall a. a -> [a] -> [a]
:Edits a
le)
| Bool
otherwise = (b
scr, a -> Edit a
forall a. a -> Edit a
Rem a
xEdit a -> Edits a -> Edits a
forall a. a -> [a] -> [a]
:Edits a
te)
where sca :: b
sca = b
l b -> b -> b
forall a. Num a => a -> a -> a
+ a -> b
ad a
y
scr :: b
scr = b
t b -> b -> b
forall a. Num a => a -> a -> a
+ a -> b
rm a
x
scs :: b
scs = b
lt b -> b -> b
forall a. Num a => a -> a -> a
+ a -> a -> b
sw a
x a
y
curryNextCell :: a
-> (b, Edits a)
-> ((a, (b, Edits a)), (b, Edits a))
-> (b, Edits a)
curryNextCell a
x (b, Edits a)
l = ((a, (b, Edits a)) -> (b, Edits a) -> (b, Edits a))
-> ((a, (b, Edits a)), (b, Edits a)) -> (b, Edits a)
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((a -> (b, Edits a) -> (b, Edits a) -> (b, Edits a))
-> (a, (b, Edits a)) -> (b, Edits a) -> (b, Edits a)
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (a
-> (b, Edits a)
-> a
-> (b, Edits a)
-> (b, Edits a)
-> (b, Edits a)
nextCell a
x (b, Edits a)
l))
nextRow :: [a] -> [(b, Edits a)] -> a -> [(b, Edits a)]
nextRow [a]
ys da :: [(b, Edits a)]
da@(~(~(b
dn, Edits a
de):[(b, Edits a)]
ds)) a
x = ((b, Edits a) -> ((a, (b, Edits a)), (b, Edits a)) -> (b, Edits a))
-> (b, Edits a)
-> [((a, (b, Edits a)), (b, Edits a))]
-> [(b, Edits a)]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (a
-> (b, Edits a)
-> ((a, (b, Edits a)), (b, Edits a))
-> (b, Edits a)
curryNextCell a
x) (b
dnb -> b -> b
forall a. Num a => a -> a -> a
+a -> b
rm a
x,a -> Edit a
forall a. a -> Edit a
Rem a
xEdit a -> Edits a -> Edits a
forall a. a -> [a] -> [a]
:Edits a
de) ([(a, (b, Edits a))]
-> [(b, Edits a)] -> [((a, (b, Edits a)), (b, Edits a))]
forall a b. [a] -> [b] -> [(a, b)]
zip ([a] -> [(b, Edits a)] -> [(a, (b, Edits a))]
forall a b. [a] -> [b] -> [(a, b)]
zip [a]
ys [(b, Edits a)]
da) [(b, Edits a)]
ds)
tl :: [a]
tl = g a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList g a
ys'
genericReversedLevenshtein :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
=> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericReversedLevenshtein :: (a -> b) -> (a -> b) -> (a -> a -> b) -> f a -> g a -> (b, Edits a)
genericReversedLevenshtein = (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericReversedLevenshtein' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
genericReversedLevenshteinWithScore' :: (Foldable f, Foldable g, Num b, Ord b)
=> (a -> a -> Bool)
-> EditScore a b
-> f a
-> g a
-> (b, Edits a)
genericReversedLevenshteinWithScore' :: (a -> a -> Bool) -> EditScore a b -> f a -> g a -> (b, Edits a)
genericReversedLevenshteinWithScore' a -> a -> Bool
cmp (EditScore a -> b
ad a -> b
rm a -> a -> b
sw a -> a -> b
_) = (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, Edits a)
genericReversedLevenshtein' a -> a -> Bool
cmp a -> b
ad a -> b
rm a -> a -> b
sw
genericReversedLevenshteinWithScore :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
=> EditScore a b
-> f a
-> g a
-> (b, Edits a)
genericReversedLevenshteinWithScore :: EditScore a b -> f a -> g a -> (b, Edits a)
genericReversedLevenshteinWithScore = (a -> a -> Bool) -> EditScore a b -> f a -> g a -> (b, Edits a)
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool) -> EditScore a b -> f a -> g a -> (b, Edits a)
genericReversedLevenshteinWithScore' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)