Either nothing changed, and we can keep a (sub)tree, or something changed.

When something changed, there are essentially 2 cases:

• the labels on the matching nodes were different. If so, we Replace the left with the right tree.
• the labels on this node were the same, but there was a difference in one or more of the children.

In case there was a different with the children, there is also the possibility that the length was different. This is described in the Tail of the Copy.

If the left node had more children than the right now, we get a Left tail with the trailing children from the left tree.

On the other hand, if the right node had more children we get a Right tail.

If both trees has the same number of children, the tail is Empty.

Diffing 2 trees (using standard equivalence (==)) produces a Diff!

import Tree.Diff as Diff
import Tree exposing (tree, singleton)


Diff.diff
    (tree "root"
        [ tree "folder"
            [ singleton "foo"
            , singleton "bar"
            ]
        , singleton "yeah"
        , singleton "keep me!"
        ]
    )
    (tree "root"
        [ tree "folder"
            [ singleton "foo" ]
        , tree "folder2"
            [ singleton "nice" ]
        , singleton "keep me!"
        ]
    )
--> Diff.Copy "root"
-->     [ Diff.Copy "folder"
-->         [ Diff.Keep (singleton "foo") ]
-->         (Diff.Left [ singleton "bar" ])
-->     , Diff.Replace
-->         (singleton "yeah")
-->         (tree "folder2" [ singleton "nice" ])
-->     , Diff.Keep (singleton "keep me!")
-->     ]
-->     Diff.Empty

Diff using custom equivalence.

This allows using a custom function to decide whether two labels are really equivalent. Perhaps you're using some custom datatype and you consider two instances of them to be equivalent if they hold the same data, regardless of their structural equality? Or perhaps your labels are floats, and you want to check using some epsilon value?

This is your function!

Diff using regular equality on a derived property of the label.

This is related to diffWith in the same way List.sortBy is related to List.sortWith. Imagine, for example, that your labels are tuples and you're only interested in the second value.

You could either write diffWith (\(_, x) (_, y) -> x == y) left right or the equivalent but much simple diffBy Tuple.second.

If you find yourself being worried about performance: Please benchmark!

Has the same relation to mergeWith as diffBy has to diffWith.

import Tree.Diff as Diff
import Tree exposing (tree, singleton)


Diff.mergeBy Tuple.second
    (tree ( 1, "root" )
        [ tree ( 1, "folder" )
            [ singleton ( 1, "foo" )
            , singleton ( 1, "bar" )
            ]
        , singleton ( 1, "yeah" )
        , singleton ( 1, "keep me!" )
        ]
    )
    (tree ( 2, "root" )
        [ tree ( 2, "folder" )
            [ singleton ( 2, "foo" ) ]
        , tree ( 2, "folder2" )
            [ singleton ( 2, "nice" ) ]
        , singleton ( 2, "keep me!" )
        ]
    )
--> tree ( 1, "root" )
-->     [ tree ( 1, "folder" )
-->         [ singleton ( 1, "foo" ) ]
-->     , tree ( 2, "folder2" )
-->         [ singleton ( 2, "nice" ) ]
-->     , singleton ( 1, "keep me!" )
-->     ]