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

Copyright(c) Sterling Clover 2008-2011 Kevin Charter 2011
LicenseBSD 3 Clause
Maintainers.clover@gmail.com
Stabilityexperimental
Portabilityportable
Safe HaskellSafe
LanguageHaskell98

Data.Algorithm.Diff

Contents

Description

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

Synopsis

Documentation

type Diff a = PolyDiff a a Source #

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

data PolyDiff a b 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).

Constructors

First a 
Second b 
Both a b 
Instances
(Eq a, Eq b) => Eq (PolyDiff a b) Source # 
Instance details

Defined in Data.Algorithm.Diff

Methods

(==) :: PolyDiff a b -> PolyDiff a b -> Bool #

(/=) :: PolyDiff a b -> PolyDiff a b -> Bool #

(Show a, Show b) => Show (PolyDiff a b) Source # 
Instance details

Defined in Data.Algorithm.Diff

Methods

showsPrec :: Int -> PolyDiff a b -> ShowS #

show :: PolyDiff a b -> String #

showList :: [PolyDiff a b] -> ShowS #

Comparing lists for differences

getDiff :: Eq a => [a] -> [a] -> [Diff a] Source #

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

getDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff a b] 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 a => [a] -> [a] -> [Diff [a]] Source #

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

getGroupedDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff [a] [b]] Source #