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

Data.TreeDiff.Tree

Description

Tree diffing working on containers Tree.

Synopsis

# Documentation

treeDiff :: (Show a, Eq a) => Tree a -> Tree a -> Edit (EditTree a) Source #

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

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

Instances details
 Show a => Show (EditTree a) Source # Instance detailsDefined in Data.TreeDiff.Tree MethodsshowsPrec :: Int -> EditTree a -> ShowS #show :: EditTree a -> String #showList :: [EditTree a] -> ShowS #

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

Instances details
 Eq a => Eq (Edit a) Source # Instance detailsDefined in Data.TreeDiff.List Methods(==) :: Edit a -> Edit a -> Bool #(/=) :: Edit a -> Edit a -> Bool # Show a => Show (Edit a) Source # Instance detailsDefined in Data.TreeDiff.List MethodsshowsPrec :: Int -> Edit a -> ShowS #show :: Edit a -> String #showList :: [Edit a] -> ShowS # NFData a => NFData (Edit a) Source # Instance detailsDefined in Data.TreeDiff.List Methodsrnf :: Edit a -> () #