Data.TreeDiff.Tree

Tree diffing working on containers Tree.

Documentation

treeDiff :: Eq a => Tree a -> Tree a -> Edit (EditTree a)

A breadth-traversal diff.

It's different from gdiff, as it doesn't produce a flat edit script, but edit script iself is a tree. This makes visualising the diff much simpler.

Examples

Let's start from simple tree. We pretty print them as s-expressions.

>>> let x = Node 'a' [Node 'b' [], Node 'c' [return 'd', return 'e'], Node 'f' []]
>>> ppTree PP.char x
(a b (c d e) f)

If we modify an argument in a tree, we'll notice it's changed:

>>> let y = Node 'a' [Node 'b' [], Node 'c' [return 'x', return 'e'], Node 'f' []]
>>> ppTree PP.char y
(a b (c x e) f)

>>> ppEditTree PP.char (treeDiff x y)
(a b (c -d +x e) f)

If we modify a constructor, the whole sub-trees is replaced, though there might be common subtrees.

>>> let z = Node 'a' [Node 'b' [], Node 'd' [], Node 'f' []]
>>> ppTree PP.char z
(a b d f)

>>> ppEditTree PP.char (treeDiff x z)
(a b -(c d e) +d f)

If we add arguments, they are spotted too:

>>> let w = Node 'a' [Node 'b' [], Node 'c' [return 'd', return 'x', return 'e'], Node 'f' []]
>>> ppTree PP.char w
(a b (c d x e) f)

>>> ppEditTree PP.char (treeDiff x w)
(a b (c d +x e) f)

data EditTree a

Type used in the result of treeDiff.

It's essentially a Tree, but the forest list is changed from [tree a] to [Edit (tree a)]. This highlights that treeDiff performs a list diff on each tree level.

Constructors

EditNode a [Edit (EditTree a)]

Instances

Show a => Show (EditTree a)

Methods

showsPrec :: Int -> EditTree a -> ShowS

show :: EditTree a -> String

showList :: [EditTree a] -> ShowS

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