HORIZON HASKELLDocslts/ghc-9.10.xc74966e2026-09-27Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · c74966e · 2026-09-27

ModuleDiff-1.0.2Haskell2010

Data.Algorithm.Diff

This is an implementation of the 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. For inputs of size O(N) with the number of differences D it has O(ND) time and O(D^2) space complexity.

  • 2 types
  • 4 values
  • PackageDiff-1.0.2
  • Exports6
  • LanguageHaskell2010
  • LicenceBSD-3-Clause
  • SourceDiff.hs
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 newtype to only perform equality on side of a tuple).

Constructors

Instances4Bifunctor, Functor, Eq, Show

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"]