Copyright	(c) Sterling Clover 2008-2011 Kevin Charter 2011
License	BSD 3 Clause
Maintainer	s.clover@gmail.com
Stability	experimental
Portability	portable
Safe Haskell	Safe
Language	Haskell98

Data.Algorithm.Diff

Contents

Comparing lists for differences
Finding chunks of differences

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

type Diff a = PolyDiff a a
data PolyDiff a b
- = First a
- | Second b
- | Both a b
getDiff :: Eq a => [a] -> [a] -> [Diff a]
getDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff a b]
getGroupedDiff :: Eq a => [a] -> [a] -> [Diff [a]]
getGroupedDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff [a] [b]]

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 #