hdiff-0.0.1: Pattern-Expression-based differencing of arbitrary types.

Safe HaskellNone
LanguageHaskell2010

Data.HDiff.Diff

Synopsis

Documentation

diffOpts' :: forall ki codes phi at. (EqHO ki, DigestibleHO ki, DigestibleHO phi) => DiffOptions -> Holes ki codes phi at -> Holes ki codes phi at -> (Int, Delta (Holes ki codes (Sum phi (MetaVarIK ki))) at) Source #

Diffs two generic merkelized structures. The outline of the process is:

i) Annotate each tree with the info we need (digest and height) ii) Build the sharing trie iii) Identify the proper shares iv) Substitute the proper shares by a metavar in both the source and deletion context v) Extract the spine and compute the closure.

diffOpts :: (EqHO ki, DigestibleHO ki, IsNat ix) => DiffOptions -> Fix ki codes ix -> Fix ki codes ix -> Patch ki codes ix Source #

When running the diff for two fixpoints, we can cast the resulting deletion and insertion context into an actual patch.

diff :: (EqHO ki, DigestibleHO ki, IsNat ix) => MinHeight -> Fix ki codes ix -> Fix ki codes ix -> Patch ki codes ix Source #

data DiffMode Source #

Diffing Algorithm modes. This is better illustrated with an example. Supposte we have the following source and destination trees:

src = Bin (Bin t k) u
dst = Bin (Bin t k) t

Constructors

DM_ProperShare

The proper share algorithm will only share the trees that are supposed to be a proper share. With the src and dst above, it will produce:

diff src dst = Bin (Bin 0 1) u |-> Bin (Bin 0 1) 0

A good intuition is that this approach will prefer maximum sharing as opposed to sharing bigger trees.

DM_NoNested

The first algoritm we produced. Does not share nested trees. In fact, with this mode we will get the following result:

diff src dst = Bin 0 u |-> Bin 0 t
DM_Patience

Similar to git --patience, we share only unique trees. In this example, this would result in the same as DM_NoNested, but if we take u = (Bin t k), no sharing would be performed whatsoever.