Safe Haskell | Trustworthy |
---|---|
Language | Haskell2010 |
For day-to-day use, please see Data.Patch
- newtype Patch a = Patch [Edit a]
- data Edit a
- inverse :: Patch a -> Patch a
- index :: Lens' (Edit a) Int
- old :: Traversal' (Edit a) a
- new :: Traversal' (Edit a) a
- toList :: Patch a -> [Edit a]
- unsafeFromList :: [Edit a] -> Patch a
- fromList :: Eq a => [Edit a] -> Patch a
- normalise :: [Edit a] -> [Edit a]
- apply :: Patch a -> Vector a -> Vector a
- transformWith :: Eq a => (a -> a -> a) -> Patch a -> Patch a -> (Patch a, Patch a)
- ours :: a -> a -> a
- theirs :: a -> a -> a
- transform :: (Eq a, Monoid a) => Patch a -> Patch a -> (Patch a, Patch a)
- diff :: Eq a => Vector a -> Vector a -> Patch a
Documentation
>>>
import Test.QuickCheck
>>>
:{
let nonEmpty :: Vector a -> Bool nonEmpty = (>0) . Vector.length editsTo :: Arbitrary a => Vector a -> Gen (Edit a) editsTo v = do i <- choose (0, Vector.length v -1) c <- elements [const (Insert i), \o _ -> Delete i o, Replace i] x <- arbitrary return $ c (v Vector.! i) x patchesFrom' :: (Eq a, Arbitrary a) => Vector a -> Gen (Patch a) patchesFrom' v | Vector.length v > 0 = fromList <$> listOf (editsTo v) patchesFrom' _ | otherwise = fromList <$> listOf (Insert 0 <$> arbitrary) patchesFrom :: Vector Int -> Gen (Patch Int) patchesFrom = patchesFrom' divergingPatchesFrom :: Vector Int -> Gen (Patch Int, Patch Int) divergingPatchesFrom v = (,) <$> patchesFrom v <*> patchesFrom v historyFrom d 0 = return [] historyFrom d m = do p <- patchesFrom d r <- historyFrom (apply p d) $ m - 1 return (p:r) :}
>>>
:set -XScopedTypeVariables
>>>
instance Arbitrary a => Arbitrary (Vector a) where arbitrary = Vector.fromList <$> listOf arbitrary
Blah
forAll (patchesFrom d) $ \ x -> read (show x) == x
A patch is a collection of edits performed to a document, in this case a Vector
. They are
implemented as a list
of Edit
, and can be converted to and from raw lists of edits using toList
and fromList
respectively.
Patches form a group (a Monoid
with inverses), where the inverse element can be computed with
inverse
and the group operation is composition of patches. Applying p1 <> p2
is the
same as applying p1
then p2
(see apply
). This composition operator may produce structurally
different patches depending on associativity, however the patches are guaranteed to be equivalent
in the sense that the resultant document will be the same when they are applied.
forAll (patchesFrom d) $ \a -> a <> mempty == a
forAll (patchesFrom d) $ \a -> mempty <> a == a
forAll (historyFrom d 3) $ \[a, b, c] -> apply (a <> (b <> c)) d == apply ((a <> b) <> c) d
The indices of the Edit
s are all based on the original document, so:
>>>
Vector.toList $ apply (fromList [Insert 0 'a', Insert 1 'b']) (Vector.fromList "123")
"a1b23"
>>>
Vector.toList $ apply (fromList [Insert 0 'a', Insert 0 'b']) (Vector.fromList "123")
"ab123"
Note that the first Insert
didn't introduce an offset for the second.
An Edit
is a single alteration of the vector, either inserting, removing, or replacing an element.
Useful optics are provided below, for the index
, the old
element, and the new
element.
inverse :: Patch a -> Patch a Source
Compute the inverse of a patch, such that:
forAll (patchesFrom d) $ \p -> p <> inverse p == mempty
forAll (patchesFrom d) $ \p -> inverse p <> p == mempty
forAll (patchesFrom d) $ \p -> inverse (inverse p) == p
forAll (historyFrom d 2) $ \[p, q] -> inverse (p <> q) == inverse q <> inverse p
forAll (patchesFrom d) $ \p -> inverse mempty == mempty
index :: Lens' (Edit a) Int Source
A lens for the index where an edit is to be performed.
nonEmpty d ==> forAll (editsTo d) $ \e -> set index v e ^. index == v
nonEmpty d ==> forAll (editsTo d) $ \e -> set index (e ^. index) e == e
nonEmpty d ==> forAll (editsTo d) $ \e -> set index v' (set index v e) == set index v' e
old :: Traversal' (Edit a) a Source
A traversal for the old element to be replaced/deleted. Empty in the case of an Insert
.
new :: Traversal' (Edit a) a Source
A traversal for the new value to be inserted or replacing the old value. Empty in the case of a Delete
.
unsafeFromList :: [Edit a] -> Patch a Source
Directly convert a list of edits to a patch, without sorting edits by index, and resolving contradictory edits. Use this function if you know that the input list is already a wellformed patch.
fromList :: Eq a => [Edit a] -> Patch a Source
Convert a list of edits to a patch, making sure to eliminate conflicting edits and sorting by index.
apply :: Patch a -> Vector a -> Vector a Source
Apply a patch to a document.
Technically, apply
is a monoid morphism to the monoid of endomorphisms Vector a -> Vector a
,
and that's how we can derive the following two laws:
forAll (historyFrom d 2) $ \[a, b] -> apply b (apply a d) == apply (a <> b) d
apply mempty d == d
transformWith :: Eq a => (a -> a -> a) -> Patch a -> Patch a -> (Patch a, Patch a) Source
Given two diverging patches p
and q
, transform m p q
returns
a pair of updated patches (p',q')
such that q <> p'
and
p <> q'
are equivalent patches that incorporate the changes
of both p
and q
, up to merge conflicts, which are handled by
the provided function m
.
This is the standard transform
function of Operational Transformation
patch resolution techniques.
forAll (divergingPatchesFrom d) $ \(p,q) -> let (p', q') = transformWith ours p q in apply (p <> q') d == apply (q <> p') d
This function is commutative iff m
is commutative.
forAll (divergingPatchesFrom d) $ \(p,q) -> let (p', q') = transformWith (*) p q; (q'', p'') = transformWith (*) q p in p' == p'' && q' == q''
Some example conflict strategies are provided below.