{-# LANGUAGE CPP, 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', genericLevenshteinDistanceWithScore, genericLevenshteinDistanceWithScore', levenshteinDistance, levenshteinDistance'
    -- * Obtain the Levenshtein distance together with the path of 'Edit's
  , genericLevenshtein, genericLevenshtein', genericLevenshteinWithScore, genericLevenshteinWithScore', levenshtein, levenshtein'
    -- * Obtain the Levenshtein distance together with a reversed path of 'Edit's
  , genericReversedLevenshtein, genericReversedLevenshtein', genericReversedLevenshteinWithScore, genericReversedLevenshteinWithScore', reversedLevenshtein, reversedLevenshtein'
    -- * Data type to present modifications from one 'Foldable' to another.
  , Edit(Add, Rem, Copy, Swap), Edits, applyEdits
    -- * Present the modification costs
  , EditScore(editAdd, editRemove, editReplace, editTranspose), editCost, editsCost, 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

-- | A data type that provides information about how costly a certain edit is. One can make use
-- of this data type to change the cost functions in an effective way. The 'EditScore' scales linear,
-- this means that if we double all the costs, the minimal edit cost will also double.
data EditScore a b
  = EditScore {
      EditScore a b -> a -> b
editAdd :: a -> b  -- ^ A function that determines the penalty to insert a given item.
    , EditScore a b -> a -> b
editRemove :: a -> b  -- ^ A function that determines the penalty of removing a given item.
    , EditScore a b -> a -> a -> b
editReplace :: a -> a -> b  -- ^ A function that determines the penalty of replacing a given item with another given item.
    , EditScore a b -> a -> a -> b
editTranspose :: a -> a -> b  -- ^ A function that determines the penalty of transposing two items.
  }
  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)

-- | A function to construct an 'EditScore' object where the cost of adding, removing, replacing
-- and transposing all have the same given cost.
constantEditScore
  :: b  -- ^ The given cost for all the operations.
  -> EditScore a b  -- ^ The corresponding 'EditScore' object.
constantEditScore :: 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

-- | 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.
  | Transpose a a -- ^ We swap two characters for the given string, this edit is only available for the /Damerau-Levenshtein distance/.
  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

-- | A type alias for a /list/ of 'Edit's.
type Edits a = [Edit a]

-- | Determine the cost of a given 'Edit' as described with the given 'EditScore' object.
editCost :: Num b
  => EditScore a b  -- ^ An 'EditScore' object that determines how costly each transformation is.
  -> Edit a  -- ^ The given 'Edit' for which we want to calculate the score.
  -> b  -- ^ The given edit distance for the given 'Edit' with the given 'EditScore'.
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

-- | Determine the cost of the given sequence of 'Edit's with the given 'EditScore' object
-- that determines the cost for each edit. The sum of the 'Edit's is returned.
editsCost :: (Foldable f, Num b)
  => EditScore a b  -- ^ An 'EditScore' object that determines how costly each transformation is.
  -> f (Edit a)  -- ^ The given 'Foldable' of 'Edit's for which we want to calculate the score.
  -> b  -- ^ The given edit distance for all the given 'Edit's with the given 'EditScore'.
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

-- | 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
  => Edits a  -- ^ The given list of 'Edit's to apply to the given list.
  -> [a]  -- ^ The list of items to edit with the given 'Edit's.
  -> Maybe [a]  -- ^ The modified list, given the checks hold about what item to remove/replace wrapped in a 'Just'; 'Nothing' otherwise.
applyEdits :: 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

-- | 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, Edits a)  -- ^ The edit distance between the two 'Foldable's.
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
(==)

-- | 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, Edits a)  -- ^ The edit distance between the two 'Foldable's together with a list of 'Edit's to transform the first 'Foldable' to the second one.
levenshtein' :: (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'

-- | 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, Edits a)  -- ^ The edit distance between the two 'Foldable's together with the 'Edit's to make to convert the first sequence into the second.
reversedLevenshtein :: 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
(==)

-- | 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, Edits a)  -- ^ The edit distance between the two 'Foldable's together with a reversed list of 'Edit's to transform the original sequence into the target sequence.
reversedLevenshtein' :: (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'

-- | 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
(==)

-- | Calculate the Levenshtein distance with the given 'EditScore' object that determine how costly each edit is.
-- The function determines the minimal score with 'Add', 'Rem', 'Copy' and 'Swap' edits. We determine if two
-- items are the same with the 'Eq' instance for the item type.
genericLevenshteinDistanceWithScore :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
  => EditScore a b  -- ^ The given 'EditScore' object that determines the cost per edit.
  -> f a  -- ^ The given original sequence.
  -> g a  -- ^ The given target sequence.
  -> b  -- ^ The edit distance between the two 'Foldable's.
genericLevenshteinDistanceWithScore :: 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
(==)

-- | Calculate the Levenshtein distance with the given equivalence relation, and the given 'EditScore' object that determine how costly each edit is.
-- The function determines the minimal score with 'Add', 'Rem', 'Copy' and 'Swap' edits.
genericLevenshteinDistanceWithScore' :: (Foldable f, Foldable g, Num b, Ord b)
  => (a -> a -> Bool)  -- ^ The given equivalence relation to work with.
  -> EditScore a b  -- ^ The given 'EditScore' object that determines the cost per edit.
  -> f a  -- ^ The given original sequence.
  -> g a  -- ^ The given target sequence.
  -> b  -- ^ The edit distance between the two 'Foldable's.
genericLevenshteinDistanceWithScore' :: (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

-- | 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, Edits a)  -- ^ A 2-tuple with the edit score as first item, and a list of modifications in /normal/ order as second item to transform the first sequence to the second one.
genericLevenshtein' :: (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'

-- | 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, Edits a)  -- ^ A 2-tuple with the edit score as first item, and a list of modifications in /normal/ order as second item to transform the first sequence to the second one.
genericLevenshtein :: (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
(==)

-- | Calculate the Levenshtein distance and the modifications with the given equivalence relation, and the given 'EditScore' object that determine how costly each edit is.
-- The function determines the minimal score with 'Add', 'Rem', 'Copy' and 'Swap' edits.
genericLevenshteinWithScore' :: (Foldable f, Foldable g, Num b, Ord b)
  => (a -> a -> Bool)  -- ^ The given equivalence relation to determine if two items are the same.
  -> EditScore a b  -- ^ The given 'EditScore' object that specifies the cost of each mutation (add, remove, replace).
  -> f a  -- ^ The given original sequence.
  -> g a  -- ^ The given target sequence.
  -> (b, Edits a)  -- ^ A 2-tuple with the edit score as first item, and a list of modifications as second item to transform the first 'Foldable' (as list) to the second 'Foldable' (as list).
genericLevenshteinWithScore' :: (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

-- | Calculate the Levenshtein distance and the modifications with the given 'EditScore' object that determine how costly each edit is.
-- The function determines the minimal score with 'Add', 'Rem', 'Copy' and 'Swap' edits. The 'Eq' instance of the elements is used
-- to determine if two items are equivalent.
genericLevenshteinWithScore :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
  => EditScore a b  -- ^ The given 'EditScore' object that specifies the cost of each mutation (add, remove, replace).
  -> f a  -- ^ The given original sequence.
  -> g a  -- ^ The given target sequence.
  -> (b, Edits a)  -- ^ A 2-tuple with the edit score as first item, and a list of modifications as second item to transform the first 'Foldable' (as list) to the second 'Foldable' (as list).
genericLevenshteinWithScore :: 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
(==)

-- | 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, Edits a)  -- ^ A 2-tuple with the edit score as first item, and a list of modifications in /reversed/ order as second item to transform the first 'Foldable' (as list) to the second 'Foldable' (as list).
genericReversedLevenshtein' :: (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'

-- | 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, Edits a)  -- ^ A 2-tuple with the edit score as first item, and a list of modifications in /reversed/ order as second item to transform the first 'Foldable' (as list) to the second 'Foldable' (as list).
genericReversedLevenshtein :: (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
(==)

-- | Calculate the Levenshtein distance and the modifications with the given equivalence relation, and the given 'EditScore' object that determine how costly each edit is.
-- The function determines the minimal score with 'Add', 'Rem', 'Copy' and 'Swap' edits.
genericReversedLevenshteinWithScore' :: (Foldable f, Foldable g, Num b, Ord b)
  => (a -> a -> Bool)  -- ^ The given equivalence relation to determine if two items are the same.
  -> EditScore a b  -- ^ The given 'EditScore' object that specifies the cost of each mutation (add, remove, replace).
  -> f a  -- ^ The given original sequence.
  -> g a  -- ^ The given target sequence.
  -> (b, Edits a)  -- ^ A 2-tuple with the edit score as first item, and a list of modifications in /reversed/ order as second item to transform the first 'Foldable' (as list) to the second 'Foldable' (as list).
genericReversedLevenshteinWithScore' :: (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

-- | Calculate the Levenshtein distance and the modifications with the given 'EditScore' object that determine how costly each edit is.
-- The function determines the minimal score with 'Add', 'Rem', 'Copy' and 'Swap' edits. The 'Eq' instance of the items will determine
-- the equivalence relation.
genericReversedLevenshteinWithScore :: (Foldable f, Foldable g, Eq a, Num b, Ord b)
  => EditScore a b  -- ^ The given 'EditScore' object that specifies the cost of each mutation (add, remove, replace).
  -> f a  -- ^ The given original sequence.
  -> g a  -- ^ The given target sequence.
  -> (b, Edits a)  -- ^ A 2-tuple with the edit score as first item, and a list of modifications in /reversed/ order as second item to transform the first 'Foldable' (as list) to the second 'Foldable' (as list).
genericReversedLevenshteinWithScore :: 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
(==)