Data.Foldable.Levenshtein

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 Edits, and furthermore ways to alter the score for an addition, removal, edit that can depend on what item is modified.

Calculate the Levenshtein distance

genericLevenshteinDistance

Arguments

:: (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 Foldables.

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'

Arguments

:: (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 Foldables.

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.

levenshteinDistance

Arguments

:: (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 Foldables.

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'

Arguments

:: (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 Foldables.

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.

Obtain the Levenshtein distance together with the path of Edits

genericLevenshtein

Arguments

:: (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.

A function to determine the Levenshtein distance together with a list of Edits 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 Foldables are considered equivalent.

genericLevenshtein'

Arguments

:: (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.

A function to determine the Levenshtein distance together with a list of Edits 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 Foldables are considered equivalent.

levenshtein

Arguments

:: (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 Foldables.

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'

Arguments

:: (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 Foldables together with a list of Edits to transform the first Foldable to the second one.

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 Foldables are considered equivalent.

Obtain the Levenshtein distance together with a reversed path of Edits

genericReversedLevenshtein

Arguments

:: (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).

A function to determine the Levenshtein distance together with a list of Edits 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 Foldables are considered equivalent.

genericReversedLevenshtein'

Arguments

:: (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).

A function to determine the Levenshtein distance together with a list of Edits 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 Foldables are considered equivalent.

reversedLevenshtein

Arguments

:: (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 Foldables together with the Edits to make to convert the first sequence into the second.

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'

Arguments

:: (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 Foldables together with a reversed list of Edits to transform the original sequence into the target sequence.

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.

Data type to present modifications from one Foldable to the other.a

data Edit a

A data type that is used to list how to edit a sequence to form another sequence.

Constructors

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.

Instances

Functor Edit

Defined in Data.Foldable.Levenshtein

Methods

fmap :: (a -> b) -> Edit a -> Edit b

(<$) :: a -> Edit b -> Edit a

Foldable Edit

Defined in Data.Foldable.Levenshtein

Methods

fold :: Monoid m => Edit m -> m

foldMap :: Monoid m => (a -> m) -> Edit a -> m

foldMap' :: Monoid m => (a -> m) -> Edit a -> m

foldr :: (a -> b -> b) -> b -> Edit a -> b

foldr' :: (a -> b -> b) -> b -> Edit a -> b

foldl :: (b -> a -> b) -> b -> Edit a -> b

foldl' :: (b -> a -> b) -> b -> Edit a -> b

foldr1 :: (a -> a -> a) -> Edit a -> a

foldl1 :: (a -> a -> a) -> Edit a -> a

toList :: Edit a -> [a]

null :: Edit a -> Bool

length :: Edit a -> Int

elem :: Eq a => a -> Edit a -> Bool

maximum :: Ord a => Edit a -> a

minimum :: Ord a => Edit a -> a

sum :: Num a => Edit a -> a

product :: Num a => Edit a -> a

Traversable Edit

Defined in Data.Foldable.Levenshtein

Methods

traverse :: Applicative f => (a -> f b) -> Edit a -> f (Edit b)

sequenceA :: Applicative f => Edit (f a) -> f (Edit a)

mapM :: Monad m => (a -> m b) -> Edit a -> m (Edit b)

sequence :: Monad m => Edit (m a) -> m (Edit a)

Arbitrary1 Edit

Defined in Data.Foldable.Levenshtein

Methods

liftArbitrary :: Gen a -> Gen (Edit a)

liftShrink :: (a -> [a]) -> Edit a -> [Edit a]

Eq1 Edit

Defined in Data.Foldable.Levenshtein

Methods

liftEq :: (a -> b -> Bool) -> Edit a -> Edit b -> Bool

Ord1 Edit

Defined in Data.Foldable.Levenshtein

Methods

liftCompare :: (a -> b -> Ordering) -> Edit a -> Edit b -> Ordering

NFData1 Edit

Defined in Data.Foldable.Levenshtein

Methods

liftRnf :: (a -> ()) -> Edit a -> ()

Hashable1 Edit

Defined in Data.Foldable.Levenshtein

Methods

liftHashWithSalt :: (Int -> a -> Int) -> Int -> Edit a -> Int

Eq a => Eq (Edit a)

Defined in Data.Foldable.Levenshtein

Methods

(==) :: Edit a -> Edit a -> Bool

(/=) :: Edit a -> Edit a -> Bool

Data a => Data (Edit a)

Defined in Data.Foldable.Levenshtein

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Edit a -> c (Edit a)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Edit a)

toConstr :: Edit a -> Constr

dataTypeOf :: Edit a -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Edit a))

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Edit a))

gmapT :: (forall b. Data b => b -> b) -> Edit a -> Edit a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Edit a -> r

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Edit a -> r

gmapQ :: (forall d. Data d => d -> u) -> Edit a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> Edit a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Edit a -> m (Edit a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Edit a -> m (Edit a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Edit a -> m (Edit a)

Ord a => Ord (Edit a)

Defined in Data.Foldable.Levenshtein

Methods

compare :: 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

max :: Edit a -> Edit a -> Edit a

min :: Edit a -> Edit a -> Edit a

Read a => Read (Edit a)

Defined in Data.Foldable.Levenshtein

Methods

readsPrec :: Int -> ReadS (Edit a)

readList :: ReadS [Edit a]

readPrec :: ReadPrec (Edit a)

readListPrec :: ReadPrec [Edit a]

Show a => Show (Edit a)

Defined in Data.Foldable.Levenshtein

Methods

showsPrec :: Int -> Edit a -> ShowS

show :: Edit a -> String

showList :: [Edit a] -> ShowS

Generic (Edit a)

Defined in Data.Foldable.Levenshtein

Associated Types

type Rep (Edit a) :: Type -> Type

Methods

from :: Edit a -> Rep (Edit a) x

to :: Rep (Edit a) x -> Edit a

Arbitrary a => Arbitrary (Edit a)

Defined in Data.Foldable.Levenshtein

Methods

arbitrary :: Gen (Edit a)

shrink :: Edit a -> [Edit a]

Binary a => Binary (Edit a)

Defined in Data.Foldable.Levenshtein

Methods

put :: Edit a -> Put

get :: Get (Edit a)

putList :: [Edit a] -> Put

NFData a => NFData (Edit a)

Defined in Data.Foldable.Levenshtein

Methods

rnf :: Edit a -> ()

Hashable a => Hashable (Edit a)

Defined in Data.Foldable.Levenshtein

Methods

hashWithSalt :: Int -> Edit a -> Int

hash :: Edit a -> Int

Generic1 Edit

Defined in Data.Foldable.Levenshtein

Associated Types

type Rep1 Edit :: k -> Type

Methods

from1 :: forall (a :: k). Edit a -> Rep1 Edit a

to1 :: forall (a :: k). Rep1 Edit a -> Edit a

type Rep (Edit a)

Defined in Data.Foldable.Levenshtein

type Rep (Edit a) = D1 ('MetaData "Edit" "Data.Foldable.Levenshtein" "levenshtein-0.1.0.0-IcHGnpnufdYEHYl8i3kjhH" 'False) ((C1 ('MetaCons "Add" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons "Rem" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a))) :+: (C1 ('MetaCons "Copy" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons "Swap" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a))))

type Rep1 Edit

Defined in Data.Foldable.Levenshtein

type Rep1 Edit = D1 ('MetaData "Edit" "Data.Foldable.Levenshtein" "levenshtein-0.1.0.0-IcHGnpnufdYEHYl8i3kjhH" 'False) ((C1 ('MetaCons "Add" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1) :+: C1 ('MetaCons "Rem" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1)) :+: (C1 ('MetaCons "Copy" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1) :+: C1 ('MetaCons "Swap" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1 :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1)))

applyEdits

Arguments

:: Eq a

=> [Edit a]

The given list of Edits to apply to the given list.

-> [a]

The list of items to edit with the given Edits.

-> Maybe [a]

The modified list, given the checks hold about what item to remove/replace wrapped in a Just; Nothing otherwise.

Apply the given list of Edits to the given list. If the Edits 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.