Modulefast-myers-diff-0.0.2Haskell2010

Myers.Diff

Myers Diff

This is an implementation of the O(ND) diff algorithm as described in "An O(ND) Difference Algorithm and Its Variations (1986)" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6927.

3 types
19 values

Packagefast-myers-diff-0.0.2
Exports22
LanguageHaskell2010
LicenceMIT
SourceDiff.hs

Diffing

9 declarations

typetype Diff a = PolyDiff a a

datadata PolyDiff a b

A value is either from the First list, the Second or from Both. Both contains both the left and right values, in case you are using a form of equality that doesn't check all data (for example, if you are using a custom equality relation to only perform equality on side of a tuple).

Constructors

First a
Second b
Both a b

Instances5Eq, Show, Generic, NFData, Rep

(Eq a, Eq b) => Eq (PolyDiff a b)Defined in fast-myers-diff-0.0.2 · Myers.Diff
(Show a, Show b) => Show (PolyDiff a b)Defined in fast-myers-diff-0.0.2 · Myers.Diff
Generic (PolyDiff a b)Defined in fast-myers-diff-0.0.2 · Myers.Diff
(NFData a, NFData b) => NFData (PolyDiff a b)Defined in fast-myers-diff-0.0.2 · Myers.Diff
type Rep (PolyDiff a b) = D1 ('MetaData "PolyDiff" "Myers.Diff" "fast-myers-diff-0.0.2-3xsv6P8AYuGK1mVVK9AcJO" 'False) (C1 ('MetaCons "First" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: (C1 ('MetaCons "Second" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 b)) :+: C1 ('MetaCons "Both" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 b))))Defined in fast-myers-diff-0.0.2 · Myers.Diff

valuegetTextDiff :: Text -> Text -> Vector (Diff Text)

Text diff

Uses pack and unpack, so does not roundtrip. It uses pack and unpack because Text is not the same as Vector Char; You can't index a text in O(1) time, it takes O(n) time.

valuegetStringDiff :: String -> String -> [Diff Char]

String diff

You probably want to use getTextDiff with packed strings instead, but this function doesn't have the roundtripping problem that getTextDiff has.

valuegetGroupedStringDiff :: String -> String -> [Diff String]

Grouped String diff

Like getStringDiff but with entire strings instead of individual characters.

valuegetVectorDiff :: Eq a => Vector a -> Vector a -> Vector (Diff a)

Diff two Vectors

Prefer getGroupedVectorDiff for performance reasons.

valuegetGroupedVectorDiff

:: Eq a
=> Vector a
-> Vector a
-> Vector (Diff (Vector a))

Diff two Vectors with grouped results

valuegetVectorDiffBy

:: a -> b -> Bool
-> Vector a
-> Vector b
-> Vector (PolyDiff a b)

Diff two Vectors with different types using a custom equality operator

Prefer getGroupedVectorDiffBy for performance reasons.

valuegetGroupedVectorDiffBy

:: a -> b -> Bool
-> Vector a
-> Vector b
-> Vector (PolyDiff (Vector a) (Vector b))

Diff two Vectors with grouped results using a custom equality operator

Distance

4 declarations

valuegetTextEditDistance :: Text -> Text -> Word

'Text edit distance

valuegetStringEditDistance :: String -> String -> Word

String edit distance

valuegetEditDistance :: Eq a => Vector a -> Vector a -> Word

Compute the total size of the edit script vector from 'getEditScript.

valuegetEditDistanceBy :: (a -> b -> Bool) -> Vector a -> Vector b -> Word

Compute the total size of the edit script vector from getEditScriptBy.

Internals

datadata Edit

Constructors

Delete Int Int
Delete from the old vector
Insert Int Int Int
Insert into the old vector

Instances3Eq, Ord, Show

Eq EditDefined in fast-myers-diff-0.0.2 · Myers.Diff
Ord EditDefined in fast-myers-diff-0.0.2 · Myers.Diff
Show EditDefined in fast-myers-diff-0.0.2 · Myers.Diff

valuegetEditScript :: Eq a => Vector a -> Vector a -> Vector Edit

Compute the edit script to turn a given Vector into the second given Vector

valuegetEditScriptBy :: (a -> b -> Bool) -> Vector a -> Vector b -> Vector Edit

Compute the edit script to turn a given Vector into the second given Vector with a custom equality relation

From https://blog.robertelder.org/diff-algorithm/

valuecomputeDiffFromEditScript

:: Vector a
-> Vector b
-> Vector Edit
-> Vector (PolyDiff a b)

Compute a diff using an edit script.

Prefer computeGroupedDiffFromEditScript for performance reasons.

valuecomputeGroupedDiffFromEditScript

:: Vector a
-> Vector b
-> Vector Edit
-> Vector (PolyDiff (Vector a) (Vector b))

Compute a diff using an edit script.

Prefer computeGroupedDiffFromEditScript for performance reasons.

Backwards compatibility with `Diff`

valuegetDiff :: Eq a => [a] -> [a] -> [Diff a]

For backward compatibility with Diff, use more specific functions if you can.

valuegetDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff a b]

For backward compatibility with Diff, use more specific functions if you can.

valuegetGroupedDiff :: Eq a => [a] -> [a] -> [Diff [a]]

For backward compatibility with Diff, use more specific functions if you can.

valuegetGroupedDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff [a] [b]]

For backward compatibility with Diff, use more specific functions if you can.

Diffing

Constructors

Distance

Internals

Constructors

Backwards compatibility with Diff

Backwards compatibility with `Diff`