{-# LANGUAGE DeriveDataTypeable, DeriveGeneric, DeriveTraversable, Safe #-}

{-|
Module      : Data.Foldable.Levenshtein
Description : A module to determine the edit distance and the 'Edit's to rewrite a given 'Foldable' to another 'Foldable'.
Maintainer  : hapytexeu+gh@gmail.com
Stability   : experimental
Portability : POSIX

The /Levenshtein distance/ is the /minimal/ number of additions, removals, and updates one has to make to
convert one list of items into another list of items. In this module we provide some functions that makes
it convenient to calculate the distance and the sequence of 'Edit's, and furthermore ways to alter the score
for an addition, removal, edit that can depend on what item is modified.
-}

module Data.Foldable.Levenshtein (
    -- * Calculate the Levenshtein distance
    genericLevenshteinDistance, genericLevenshteinDistance', levenshteinDistance, levenshteinDistance'
    -- * Obtain the Levenshtein distance together with the path of 'Edit's
  , genericLevenshtein, genericLevenshtein', levenshtein, levenshtein'
    -- * 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
  ) where

import Control.Arrow(second)
import Control.DeepSeq(NFData, NFData1)

import Data.Binary(Binary(put, get), getWord8, putWord8)
import Data.Data(Data)
import Data.Foldable(toList)
import Data.Functor.Classes(Eq1(liftEq), Ord1(liftCompare))
import Data.Hashable(Hashable)
import Data.Hashable.Lifted(Hashable1)

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

-- | A data type that is used to list how to edit a sequence to form another sequence.
data Edit a
  = 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.
  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))
$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
    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
_ -> 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 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

-- | 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.
  -> [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 :: [Edit a] -> [a] -> Maybe [a]
applyEdits [] [a]
ys = [a] -> Maybe [a]
forall a. a -> Maybe a
Just [a]
ys
applyEdits (Add a
x : [Edit 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
<$> [Edit a] -> [a] -> Maybe [a]
forall a. Eq a => [Edit a] -> [a] -> Maybe [a]
applyEdits [Edit a]
xs [a]
ys
applyEdits (Rem a
x : [Edit a]
xs) (a
y : [a]
ys)
  | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y = [Edit a] -> [a] -> Maybe [a]
forall a. Eq a => [Edit a] -> [a] -> Maybe [a]
applyEdits [Edit a]
xs [a]
ys
applyEdits (Swap a
y a
x : [Edit 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
<$> [Edit a] -> [a] -> Maybe [a]
forall a. Eq a => [Edit a] -> [a] -> Maybe [a]
applyEdits [Edit a]
xs [a]
ys
applyEdits (Copy a
x : [Edit 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
<$> [Edit a] -> [a] -> Maybe [a]
forall a. Eq a => [Edit a] -> [a] -> Maybe [a]
applyEdits [Edit a]
xs [a]
ys
applyEdits [Edit a]
_ [a]
_ = Maybe [a]
forall a. Maybe a
Nothing

-- | Determine the edit distance where an addition, removal, and change all count as one, and where
-- the 'Eq' instance is used to determine whether two items are equivalent, this is for example useful
-- for case-insensitve matching.
levenshteinDistance :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
  => f a  -- ^ The given original sequence.
  -> g a  -- ^ The given target sequence.
  -> b  -- ^ The edit distance between the two 'Foldable's.
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
(==)

-- | Determine the edit distance together with the steps to transform the first 'Foldable'
-- (as list) into a second 'Foldable' (as list). Add, remove and swapping items all count
-- as one edit distance.
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.
levenshtein :: f a -> g a -> (b, [Edit a])
levenshtein = (a -> a -> Bool) -> f a -> g a -> (b, [Edit a])
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool) -> f a -> g a -> (b, [Edit a])
levenshtein' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)

-- | Determine the edit distance together with the steps to transform the first 'Foldable'
-- (as list) into a second 'Foldable' (as list). Add, remove and swapping items all count
-- as one edit distance. The first parameter is a function to determine if two items
-- are of the 'Foldable's are considered equivalent.
levenshtein' :: (Foldable f, Foldable g, Num b, Ord b)
  => (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.
levenshtein' :: (a -> a -> Bool) -> f a -> g a -> (b, [Edit a])
levenshtein' = ((a -> b)
 -> (a -> b) -> (a -> a -> b) -> f a -> g a -> (b, [Edit a]))
-> f a -> g a -> (b, [Edit 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, [Edit a]))
 -> f a -> g a -> (b, [Edit a]))
-> ((a -> a -> Bool)
    -> (a -> b)
    -> (a -> b)
    -> (a -> a -> b)
    -> f a
    -> g a
    -> (b, [Edit a]))
-> (a -> a -> Bool)
-> f a
-> g a
-> (b, [Edit 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, [Edit 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, [Edit a])
genericLevenshtein'

-- | Determine the edit distance together with the steps to transform the first 'Foldable'
-- (as list) into a second 'Foldable' (as list). Add, remove and swapping items all count
-- as one edit distance. The equality function '(==)' is used to determine if two items are
-- equivalent.
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.
reversedLevenshtein :: f a -> g a -> (b, [Edit a])
reversedLevenshtein = (a -> a -> Bool) -> f a -> g a -> (b, [Edit a])
forall (f :: * -> *) (g :: * -> *) b a.
(Foldable f, Foldable g, Num b, Ord b) =>
(a -> a -> Bool) -> f a -> g a -> (b, [Edit a])
reversedLevenshtein' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)

-- | Determine the edit distance together with the steps to transform the first 'Foldable'
-- (as list) into a second 'Foldable' (as list) in /reversed/ order. Add, remove and
-- swapping items all count as one edit distance. The given equality function is used
-- to determine if two items are equivalent.
reversedLevenshtein' :: (Foldable f, Foldable g, Num b, Ord b)
  => (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.
reversedLevenshtein' :: (a -> a -> Bool) -> f a -> g a -> (b, [Edit a])
reversedLevenshtein' = ((a -> b)
 -> (a -> b) -> (a -> a -> b) -> f a -> g a -> (b, [Edit a]))
-> f a -> g a -> (b, [Edit 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, [Edit a]))
 -> f a -> g a -> (b, [Edit a]))
-> ((a -> a -> Bool)
    -> (a -> b)
    -> (a -> b)
    -> (a -> a -> b)
    -> f a
    -> g a
    -> (b, [Edit a]))
-> (a -> a -> Bool)
-> f a
-> g a
-> (b, [Edit 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, [Edit 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, [Edit a])
genericReversedLevenshtein'

-- | Determine the edit distance to transform the first 'Foldable' (as list)
-- into a second 'Foldable' (as list). Add, remove and swapping items all count
-- as one edit distance. The first parameter is an equivalence relation that
-- is used to determine if two items are considered equivalent.
levenshteinDistance' :: (Foldable f, Foldable g, Num b, Ord b)
  => (a -> a -> Bool)  -- ^ The given equivalence relation to work with.
  -> f a  -- ^ The given original sequence.
  -> g a  -- ^ The given target sequence.
  -> b  -- ^ The edit distance between the two 'Foldable's.
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'

-- | 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 '(==)' function is used
-- to determine if two items are equivalent.
genericLevenshteinDistance :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
  => (a -> b)  -- ^ The cost of adding the given item. The return value should be positive.
  -> (a -> b)  -- ^ The cost of removing the given item. The return value should be positive.
  -> (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  -- ^ The edit distance between the two 'Foldable's.
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
(==)

-- | 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.
genericLevenshteinDistance' :: (Foldable f, Foldable g, Num b, Ord b)
  => (a -> a -> Bool)  -- ^ The given equivalence relation to work with.
  -> (a -> b)  -- ^ The cost of adding the given item. The return value should be positive.
  -> (a -> b)  -- ^ The cost of removing the given item. The return value should be positive.
  -> (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  -- ^ The edit distance between the two 'Foldable's.
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'

-- | 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)
-- The cost functions of adding, removing and editing characters will be used to minimize
-- the total edit distance. The first parameter is an equivalence relation that is used
-- to determine if two items of the 'Foldable's are considered equivalent.
genericLevenshtein' :: (Foldable f, Foldable g, Num b, Ord b)
  => (a -> a -> Bool)  -- ^ The given equivalence relation to work with.
  -> (a -> b)  -- ^ The cost of adding the given item. The return value should be positive.
  -> (a -> b)  -- ^ The cost of removing the given item. The return value should be positive.
  -> (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.
genericLevenshtein' :: (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, [Edit a])
genericLevenshtein' a -> a -> Bool
eq a -> b
ad a -> b
rm a -> a -> b
sw f a
xs' = ([Edit a] -> [Edit a]) -> (b, [Edit a]) -> (b, [Edit a])
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second [Edit a] -> [Edit a]
forall a. [a] -> [a]
reverse ((b, [Edit a]) -> (b, [Edit a]))
-> (g a -> (b, [Edit a])) -> g a -> (b, [Edit 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, [Edit 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, [Edit a])
genericReversedLevenshtein' a -> a -> Bool
eq a -> b
ad a -> b
rm a -> a -> b
sw f a
xs'

-- | 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)
-- The cost functions of adding, removing and editing characters will be used to minimize
-- the total edit distance. The '(==)' function is used to determine if two items of the
-- 'Foldable's are considered equivalent.
genericLevenshtein :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
  => (a -> b)  -- ^ The cost of adding the given item. The return value should be positive.
  -> (a -> b)  -- ^ The cost of removing the given item. The return value should be positive.
  -> (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.
genericLevenshtein :: (a -> b)
-> (a -> b) -> (a -> a -> b) -> f a -> g a -> (b, [Edit a])
genericLevenshtein = (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, [Edit 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, [Edit a])
genericLevenshtein' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)

-- | 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
-- will be used to minimize the total edit distance. The first parameter is an
-- equivalence relation that is used to determine if two items of the 'Foldable's are considered equivalent.
genericReversedLevenshtein' :: (Foldable f, Foldable g, Num b, Ord b)
  => (a -> a -> Bool)  -- ^ The given equivalence relation to work with.
  -> (a -> b)  -- ^ The cost of adding the given item. The return value should be positive.
  -> (a -> b)  -- ^ The cost of removing the given item. The return value should be positive.
  -> (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).
genericReversedLevenshtein' :: (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, [Edit a])
genericReversedLevenshtein' a -> a -> Bool
eq a -> b
ad a -> b
rm a -> a -> b
sw f a
xs' g a
ys' = [(b, [Edit a])] -> (b, [Edit a])
forall a. [a] -> a
last (([(b, [Edit a])] -> a -> [(b, [Edit a])])
-> [(b, [Edit a])] -> f a -> [(b, [Edit a])]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ([a] -> [(b, [Edit a])] -> a -> [(b, [Edit a])]
nextRow [a]
tl) [(b, [Edit a])]
row0 f a
xs')
  where
    row0 :: [(b, [Edit a])]
row0 = ((b, [Edit a]) -> a -> (b, [Edit a]))
-> (b, [Edit a]) -> [a] -> [(b, [Edit a])]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (\(b
w, [Edit 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 -> [Edit a] -> [Edit a]
forall a. a -> [a] -> [a]
: [Edit a]
is)) (b
0, []) [a]
tl
    nextCell :: a
-> (b, [Edit a])
-> a
-> (b, [Edit a])
-> (b, [Edit a])
-> (b, [Edit a])
nextCell a
x (b
l, [Edit a]
le) a
y (b
lt, [Edit a]
lte) (b
t, [Edit 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 -> [Edit a] -> [Edit a]
forall a. a -> [a] -> [a]
: [Edit 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 -> [Edit a] -> [Edit a]
forall a. a -> [a] -> [a]
:[Edit 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 -> [Edit a] -> [Edit a]
forall a. a -> [a] -> [a]
:[Edit a]
le)
      | Bool
otherwise = (b
scr, a -> Edit a
forall a. a -> Edit a
Rem a
xEdit a -> [Edit a] -> [Edit a]
forall a. a -> [a] -> [a]
:[Edit 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, [Edit a])
-> ((a, (b, [Edit a])), (b, [Edit a]))
-> (b, [Edit a])
curryNextCell a
x (b, [Edit a])
l = ((a, (b, [Edit a])) -> (b, [Edit a]) -> (b, [Edit a]))
-> ((a, (b, [Edit a])), (b, [Edit a])) -> (b, [Edit a])
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((a -> (b, [Edit a]) -> (b, [Edit a]) -> (b, [Edit a]))
-> (a, (b, [Edit a])) -> (b, [Edit a]) -> (b, [Edit a])
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (a
-> (b, [Edit a])
-> a
-> (b, [Edit a])
-> (b, [Edit a])
-> (b, [Edit a])
nextCell a
x (b, [Edit a])
l))
    nextRow :: [a] -> [(b, [Edit a])] -> a -> [(b, [Edit a])]
nextRow [a]
ys da :: [(b, [Edit a])]
da@(~(~(b
dn, [Edit a]
de):[(b, [Edit a])]
ds)) a
x = ((b, [Edit a])
 -> ((a, (b, [Edit a])), (b, [Edit a])) -> (b, [Edit a]))
-> (b, [Edit a])
-> [((a, (b, [Edit a])), (b, [Edit a]))]
-> [(b, [Edit a])]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (a
-> (b, [Edit a])
-> ((a, (b, [Edit a])), (b, [Edit a]))
-> (b, [Edit 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 -> [Edit a] -> [Edit a]
forall a. a -> [a] -> [a]
:[Edit a]
de) ([(a, (b, [Edit a]))]
-> [(b, [Edit a])] -> [((a, (b, [Edit a])), (b, [Edit a]))]
forall a b. [a] -> [b] -> [(a, b)]
zip ([a] -> [(b, [Edit a])] -> [(a, (b, [Edit a]))]
forall a b. [a] -> [b] -> [(a, b)]
zip [a]
ys [(b, [Edit a])]
da) [(b, [Edit a])]
ds)
    tl :: [a]
tl = g a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList g a
ys'

-- | 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
-- will be used to minimize the total edit distance. The '(==)' function is used
-- to determine if two items of the 'Foldable's are considered equivalent.
genericReversedLevenshtein :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
  => (a -> b)  -- ^ The cost of adding the given item. The return value should be positive.
  -> (a -> b)  -- ^ The cost of removing the given item. The return value should be positive.
  -> (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).
genericReversedLevenshtein :: (a -> b)
-> (a -> b) -> (a -> a -> b) -> f a -> g a -> (b, [Edit a])
genericReversedLevenshtein = (a -> a -> Bool)
-> (a -> b)
-> (a -> b)
-> (a -> a -> b)
-> f a
-> g a
-> (b, [Edit 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, [Edit a])
genericReversedLevenshtein' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)