Diff-0.2.0: O(ND) diff algorithm in haskell.

Safe HaskellSafe-Inferred




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= It is O(mn) in space. The algorithm is the same one used by standared Unix diff.



data Diff a Source

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 newtype to only perform equality on side of a tuple).


First a 
Second a 
Both a a 


Eq a => Eq (Diff a) 
Show a => Show (Diff a) 

Comparing lists for differences

getDiff :: Eq t => [t] -> [t] -> [Diff t]Source

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

getDiffBy :: (t -> t -> Bool) -> [t] -> [t] -> [Diff t]Source

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

Finding chunks of differences

getGroupedDiff :: Eq t => [t] -> [t] -> [Diff [t]]Source

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

getGroupedDiffBy :: (t -> t -> Bool) -> [t] -> [t] -> [Diff [t]]Source