gcd a b == commonPrefix a b == commonSuffix a b Just a' = a </> p && Just b' = b </> p where p = gcd a bIn addition, the gcd operation must satisfy the following properties: Uniqueness
all isJust [ a </> c , b </> c , c </> gcd a b ] ==> (c == gcd a b)Idempotence
gcd a a == aIdentity
gcd mempty a == mempty
gcd a mempty == memptyCommutativity
gcd a b == gcd b aAssociativity
gcd (gcd a b) c == gcd a (gcd b c)
commonPrefix (a <> b) (a <> c) == a <> commonPrefix b c
stripCommonPrefix a b == (p, a', b') where p = commonPrefix a b Just a' = stripPrefix p a Just b' = stripPrefix p b p == commonPrefix a b && p <> a' == a && p <> b' == b where (p, a', b') = stripCommonPrefix a bFurthermore, commonPrefix must return the unique greatest common prefix that contains, as its prefix, any other prefix x of both values:
not (x `isPrefixOf` a && x `isPrefixOf` b) || x `isPrefixOf` commonPrefix a band it cannot itself be a suffix of any other common prefix y of both values:
not (y `isPrefixOf` a && y `isPrefixOf` b && commonPrefix a b `isSuffixOf` y)In addition, the commonPrefix operation must satisfy the following properties: Idempotence
commonPrefix a a == aIdentity
commonPrefix mempty a == mempty
commonPrefix a mempty == memptyCommutativity
commonPrefix a b == commonPrefix b aAssociativity
commonPrefix (commonPrefix a b) c == commonPrefix a (commonPrefix b c)
a == a' <> overlap a b b == overlap a b <> b'The methods must satisfy the following laws:
stripOverlap a b == (stripSuffixOverlap b a, overlap a b, stripPrefixOverlap a b) stripSuffixOverlap b a <> overlap a b == a overlap a b <> stripPrefixOverlap a b == bThe result of overlap a b must be the largest prefix of b and suffix of a, in the sense that it contains any other value x that satifies the property (x isPrefixOf b) && (x isSuffixOf a):
∀x. (x `isPrefixOf` b && x `isSuffixOf` a) => (x `isPrefixOf` overlap a b && x `isSuffixOf` overlap a b)and it must be unique so there's no other value y that satisfies the same properties for every such x:
∀y. ((∀x. (x `isPrefixOf` b && x `isSuffixOf` a) => x `isPrefixOf` y && x `isSuffixOf` y) => y == overlap a b)In addition, the overlap operation must satisfy the following properties: Idempotence
overlap a a == aIdentity
overlap mempty a == mempty
overlap a mempty == mempty
commonSuffix (a <> c) (b <> c) == commonSuffix a b <> c
stripCommonSuffix a b == (a', b', s) where s = commonSuffix a b Just a' = stripSuffix p a Just b' = stripSuffix p b s == commonSuffix a b && a' <> s == a && b' <> s == b where (a', b', s) = stripCommonSuffix a bFurthermore, commonSuffix must return the unique greatest common suffix that contains, as its suffix, any other suffix x of both values:
not (x `isSuffixOf` a && x `isSuffixOf` b) || x `isSuffixOf` commonSuffix a band it cannot itself be a prefix of any other common suffix y of both values:
not (y `isSuffixOf` a && y `isSuffixOf` b && commonSuffix a b `isPrefixOf` y)In addition, the commonSuffix operation must satisfy the following properties: Idempotence
commonSuffix a a == aIdentity
commonSuffix mempty a == mempty
commonSuffix a mempty == memptyCommutativity
commonSuffix a b == commonSuffix b aAssociativity
commonSuffix (commonSuffix a b) c == commonSuffix a (commonSuffix b c)