-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Generic diff and patch
--
-- Get an efficient, optimal, type-safe diff and patch function for your
-- datatypes of choice by defining a simple GADT and some class
-- instances.
--
-- Extracted from Eelco Lempsink's Thesis
-- (http://eelco.lempsink.nl/thesis.pdf).
@package gdiff
@version 1.0
-- | Use this library to get an efficient, optimal, type-safe diff
-- and patch function for your datatypes of choice by defining a
-- simple GADT and some class instances. The process is explained in the
-- documentation of the Family type class.
--
-- The result of diff is an optimal EditScript that
-- contains the operations that need to be performed to get from the
-- source value to the destination value. The edit script
-- can be used by patch, inspected with show and used for
-- all kinds of interesting stuff you come up with.
--
-- The library has been extracted from Eelco Lempsink's Master's Thesis
-- Generic type-safe diff and patch for families of datatypes
-- (available online: http://eelco.lempsink.nl/thesis.pdf). See
-- Appendix C for a large example. Note that some types and functions
-- have been renamed for the benefit of the API (e.g., diff to
-- diffL, diff1 to diff, Diff to
-- EditScriptL).
module Data.Generic.Diff
-- | Calculate the difference between two values in the form of an edit
-- script.
--
-- See the documentation for Family for how to make your own data
-- types work with this function.
diff :: (Type f x, Type f y) => x -> y -> EditScript f x y
-- | Apply the edit script to value.
patch :: EditScript f x y -> x -> y
-- | Underlying implementation of diff, works with (heterogeneous)
-- lists of values.
diffL :: (Family f, List f txs, List f tys) => txs -> tys -> EditScriptL f txs tys
-- | Underlying implementation of patch, works with (heterogeneous)
-- lists of values.
patchL :: EditScriptL f txs tys -> txs -> tys
compress :: Family f => EditScriptL f txs tys -> EditScriptL f txs tys
-- | The EditScriptL datatype captures the result of diffL
-- and can be used as the input to patchL (and compress).
--
-- The diffL function use a depth-first preorder traversal to
-- traverse the expression trees. The edit script it outputs contains the
-- operation that must be applied to the constructor at that point:
-- either keeping it (Cpy), removing it (Del, which does
-- not remove the complete subtree, but contracts the edge of the
-- removed node) or inserting a new constructor (Ins, which can
-- only be done if the available subtrees at that point correspond to the
-- types the constructor expects). (The CpyTree is only used when
-- running compress over an existing edit script.)
--
-- For more information about this datatype, you're advised to look at
-- Eelco Lempsink's thesis at http://eelco.lempsink.nl/thesis.pdf.
data EditScriptL :: (* -> * -> *) -> * -> * -> *
Ins :: f t ts -> EditScriptL f txs (Append ts tys) -> EditScriptL f txs (Cons t tys)
Del :: f t ts -> EditScriptL f (Append ts txs) tys -> EditScriptL f (Cons t txs) tys
Cpy :: f t ts -> EditScriptL f (Append ts txs) (Append ts tys) -> EditScriptL f (Cons t txs) (Cons t tys)
CpyTree :: EditScriptL f txs tys -> EditScriptL f (Cons t txs) (Cons t tys)
End :: EditScriptL f Nil Nil
-- | Edit script type for two single values.
type EditScript f x y = EditScriptL f (Cons x Nil) (Cons y Nil)
-- | To use diff and patch on your datatypes, you must create
-- an instance of Family.
--
-- There are four steps to set up everything for diff and
-- patch.
--
--
-- - Define your datatypes. (Presumable, you already have done
-- this.)
-- - Create a family datatype, grouping your datatypes together.
-- - Make the family datatype an instance of Family
-- - Create Type instances for each member of the family.
--
--
-- Steps 1-3 are explained below, step 4 is explained in the
-- documentation for Type.
--
-- As a running example, we create a simple family of datatypes (step 1):
--
--
-- data Expr = Min Expr Term
-- data Term = Parens Expr
-- | Number Int
--
--
-- The second step is creating the family datatype. Each constructor in
-- the datatypes above gets a constructor in a family GADT:
--
--
-- data ExprTermFamily :: * -> * -> * where
-- Min' :: ExprTermFamily Expr (Cons Expr (Cons Term Nil))
-- Parens' :: ExprTermFamily Term (Cons Expr Nil)
-- Number' :: ExprTermFamily Term (Cons Int Nil)
-- Int' :: Int -> ExprTermFamily Int Nil
--
--
-- The first type argument of the datatype must be the resulting type of
-- the constructor. The second argument captures the types of the
-- arguments the constructor expects. Note how to use Cons and
-- Nil to create type level lists.
--
-- The Int' constructor is special, in the sense that it
-- captures the Int type abstractly (listing all Int's
-- constructors would be quite impossible).
--
-- Caveat emptor: polymorphic datatypes (like lists) are
-- ill-supported and require family constructors for each instance. It
-- might require another master thesis project to solve this.
--
-- Step 3 is to create the instance for the Family class. For each
-- function you will have to implement four functions. It's
-- straightforward albeit a bit boring.
--
--
-- instance Family ExprTermFamily where
-- decEq Min' Min' = Just (Refl, Refl)
-- decEq Parens' Parens' = Just (Refl, Refl)
-- decEq Number' Number' = Just (Refl, Refl)
-- decEq (Int' x) (Int' y) | x == y = Just (Refl, Refl)
-- | otherwise = Nothing
-- decEq _ _ = Nothing
--
-- fields Min' (Min e t) = Just (CCons e (CCons t CNil))
-- fields Parens' (Parens e) = Just (CCons e CNil)
-- fields Number' (Number i) = Just (CCons i CNil)
-- fields (Int' _) _ = Just CNil
-- fields _ _ = Nothing
--
-- apply Min' (CCons e (CCons t CNil)) = Min e t
-- apply Parens' (CCons e CNil) = Parens e
-- apply Number' (CCons i CNil) = Number i
-- apply (Int' i) CNil = i
--
-- string Min' = "Min"
-- string Parens' = "Parens"
-- string Number' = "Number"
-- string (Int' i) = show i
--
class Family f
decEq :: Family f => f tx txs -> f ty tys -> Maybe (tx :=: ty, txs :=: tys)
fields :: Family f => f t ts -> t -> Maybe ts
apply :: Family f => f t ts -> ts -> t
string :: Family f => f t ts -> String
-- | For each type in the family, you need to create an instance of
-- Type, listing all the members of the family GADT which belong
-- to one type.
--
-- This is step 4 of the four steps needed to be able to use diff
-- and patch. Steps 1-3 are explained in the documentation for
-- Family.
--
-- Continuing the example from the Family documentation, the
-- instances for Type are:
--
--
-- instance Type ExprTermFamily Term where
-- constructors = [Concr Number', Concr Parens']
--
-- instance Type ExprTermFamily Expr where
-- constructors = [Concr Min']
--
-- instance Type ExprTermFamily Int where
-- constructors = [Abstr Int']
--
class Family f => Type f t
constructors :: Type f t => [Con f t]
-- | Equality GADT, see the documentation for Family for an example
-- of its use.
data (:=:) a b
Refl :: a :=: a
-- | Con wraps both concrete and abstract constructors to a simple
-- type so constructors for a single type can be put together in a list,
-- see Type for more information and an example.
--
-- Use Concr for concrete constructors (e.g., for simple abstract
-- datatypes).
--
-- Use Abstr for abstract constructors (e.g., for build-in types
-- or types with many (or infinite) constructors)
data Con :: (* -> * -> *) -> * -> *
Concr :: f t ts -> Con f t
Abstr :: (t -> f t ts) -> Con f t
-- | Datatype for type level lists, corresponding to '[]'. Use when
-- creating your Family instance.
data Nil
CNil :: Nil
-- | Datatype for type level lists, corresponding to '(:)'. Use when
-- creating your Family instance.
data Cons x xs
CCons :: x -> xs -> Cons x xs
instance [overlap ok] Eq Nat
instance [overlap ok] Show Nat
instance [overlap ok] Show (EditScriptL f txs tys)
instance [overlap ok] (Type f t, List f ts) => List f (Cons t ts)
instance [overlap ok] List f Nil