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

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-Inferred
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

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

# Documentation

data Diff a #

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 a |
Both a a |

#### Instances

Instances details

Eq a => Eq (Diff a) # |
Instance details Defined in Data.Algorithm.Diff Methods (==) :: Diff a -> Diff a -> Bool # (/=) :: Diff a -> Diff a -> Bool #
Show a => Show (Diff a) # |
Instance details Defined in Data.Algorithm.Diff Methods showsPrec :: Int -> Diff a -> ShowS # show :: Diff a -> String # showList :: [Diff a] -> ShowS #

# Comparing lists for differences

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

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

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

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