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

Safe HaskellNone
LanguageHaskell2010

Data.TreeDiff.Tree

Description

Tree diffing working on containers Tree.

Synopsis

Documentation

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

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

Show a => Show (EditTree a) Source # 

Methods

showsPrec :: 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

Show a => Show (Edit a) Source # 

Methods

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

show :: Edit a -> String #

showList :: [Edit a] -> ShowS #