Data.TreeDiff.List

A list diff.

Documentation

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

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

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)

Methods

showsPrec :: Int -> Edit a -> ShowS

show :: Edit a -> String

showList :: [Edit a] -> ShowS