ModuleDiff-2.0.1Haskell2010

Data.Algorithm.Diff

This is an implementation of the diff algorithm as described in An O(ND) Difference Algorithm and Its Variations (1986) by Eugene W. Myers. For inputs of size O(N) with the number of differences D it has O(ND) time and O(D^2) space complexity.

Algorithm overview

Finding the shortest edit script (SES) from a list as to a list bs is modelled as a shortest-path search on an edit graph: an (M+1) \times (N+1) grid of nodes (i, j) , where M and N are the lengths of as and bs respectively, with i increasing rightward and j increasing downward. Each node represents the state of having consumed i elements of as and j elements of bs . Three types of move are possible:

A rightward move (i,j) \to (i+1,j) represents deleting as[i] and costs one edit.
A downward move (i,j) \to (i,j+1) represents inserting bs[j] and costs one edit.
A diagonal move (i,j) \to (i+1,j+1) is free (zero edit cost) and is only available when as[i] = bs[j] .

The SES corresponds to a path from (0,0) to (M,N) that minimises the number of non-diagonal moves.

Both input lists are 0-indexed, which leads to a slightly different interpretation of the edit graph than in the original paper. In the paper, each node represents the state of the traversal after an edit, so a move is the edit that produced that node. Here, each node represents the state before an edit, so a move is the edit performed on that node to yield its successor. This distinction is only relevant when reading the implementation alongside the paper.

K-diagonals and the wave front

Every node (i,j) lies on the k-diagonal k = i - j . After exactly D non-diagonal moves, every reachable node lies on one of at most D+1 k-diagonals k \in \{-D,\,-D+2,\,\ldots,\,D-2,\,D\} . On each diagonal it suffices to track only the furthest-reaching node (the one with the largest i ), collapsing the two-dimensional grid to a one-dimensional wave front indexed by k .

The algorithm performs a breadth-first search over D = 0, 1, 2, \ldots , advancing the wave front by one edit at a time until a node reaches the goal (M, N) . The edit trace stored in that node is the SES, which getDiffBy reconstructs into a PolyDiff list. The term trace here differs from the paper, where it denotes the sequence of k-diagonals visited by the SES path; that structure is not materialised in this implementation.

2 types
4 values

PackageDiff-2.0.1
Exports6
LanguageHaskell2010
LicenceBSD-3-Clause
SourceDiff.hs

typetype Diff a = PolyDiff a a

This is PolyDiff specialized so both sides are the same type.

datadata PolyDiff a b

A value tagged with which of two input sequences it came from. The type parameters a and b may differ, which is useful when comparing sequences of different element types via a custom equality predicate.

Each constructor corresponds to one outcome for a position in the aligned sequences:

First — the element exists only in the first input (a deletion).
Second — the element exists only in the second input (an insertion).
Both — the element is common to both inputs. Both the left and right values are retained so that the original elements can be recovered even when equality ignores some fields.

Constructors

First a
Second b
Both a b

Instances4Bifunctor, Functor, Eq, Show

Bifunctor PolyDiffDefined in Diff-2.0.1 · Data.Algorithm.Diff.Type
Functor (PolyDiff a)Defined in Diff-2.0.1 · Data.Algorithm.Diff.Type
(Eq a, Eq b) => Eq (PolyDiff a b)Defined in Diff-2.0.1 · Data.Algorithm.Diff.Type
(Show a, Show b) => Show (PolyDiff a b)Defined in Diff-2.0.1 · Data.Algorithm.Diff.Type

Comparing lists for differences

2 declarations

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

Takes two lists and returns a list of differences between them. This is getDiffBy with == used as predicate.

> getDiff ["a","b","c","d","e"] ["a","c","d","f"]
[Both "a" "a",First "b",Both "c" "c",Both "d" "d",First "e",Second "f"]
> getDiff "abcde" "acdf"
[Both 'a' 'a',First 'b',Both 'c' 'c',Both 'd' 'd',First 'e',Second 'f']

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

A form of getDiff with no Eq constraint. Instead, an equality predicate is taken as the first argument.

Finding chunks of differences

2 declarations

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

Takes two lists and returns a list of differences between them, grouped into chunks. This is getGroupedDiffBy with == used as predicate.

> getGroupedDiff "abcde" "acdf"
[Both "a" "a",First "b",Both "cd" "cd",First "e",Second "f"]

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

Like getGroupedDiff but accepts a custom equality predicate.

Postcondition: the output list is guaranteed to be chunked. i.e. no two adjacent elements share the same constructor.