tree-diff-0.0.2.1: Diffing of (expression) trees.

Safe HaskellNone
LanguageHaskell2010

Data.TreeDiff.List

Description

A list diff.

Synopsis

Documentation

diffBy :: forall a. (a -> a -> Bool) -> [a] -> [a] -> [Edit a] Source #

List difference.

>>> diffBy (==) "hello" "world"
[Swp 'h' 'w',Swp 'e' 'o',Swp 'l' 'r',Cpy 'l',Swp 'o' 'd']

>>> diffBy (==) "kitten" "sitting"
[Swp 'k' 's',Cpy 'i',Cpy 't',Cpy 't',Swp 'e' 'i',Cpy 'n',Ins 'g']

\xs ys -> length (diffBy (==) xs ys) >= max (length xs) (length (ys :: String))
\xs ys -> length (diffBy (==) xs ys) <= length xs + length (ys :: String)

Note: currently this has O(n*m) memory requirements, for the sake of more obviously correct implementation.

data Edit a Source #

List edit operations

The Swp constructor is redundant, but it let us spot a recursion point when performing tree diffs.

Constructors

Ins a

insert

Del a

delete

Cpy a

copy unchanged

Swp a a

swap, i.e. delete + insert

Instances
Show a => Show (Edit a) Source # 
Instance details

Defined in Data.TreeDiff.List

Methods

showsPrec :: Int -> Edit a -> ShowS #

show :: Edit a -> String #

showList :: [Edit a] -> ShowS #