Skip to content

HORIZON HASKELL Docs lts/ghc-10.0.x8fef28d2026-11-02Search packagesCtrl K

Theme: |

GHC 10.0.0.20260917 · lts/ghc-10.0.x · 8fef28d · 2026-11-02

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.

Contents

Diffing
Distance
Internals
Backwards compatibility with Diff

Synopsis

type Diff
data PolyDiff
value getTextDiff
value getStringDiff
value getGroupedStringDiff
value getVectorDiff
value getGroupedVectorDiff
value getVectorDiffBy
value getGroupedVectorDiffBy
value getTextEditDistance
value getStringEditDistance
value getEditDistance
value getEditDistanceBy
data Edit
value getEditScript
value getEditScriptBy
value computeDiffFromEditScript
value computeGroupedDiffFromEditScript
value getDiff
value getDiffBy
value getGroupedDiff
value getGroupedDiffBy

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

Diffing

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-1YSHkYt9JS1IHTaFizuMGW" '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]

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

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.