Data.Monoid.Monus

Class of Abelian monoids with monus.

The monus operation <\> is a synonym for both stripPrefixOverlap and stripSuffixOverlap, which must be equivalent as <> is both associative and commutative:

(<\>) = flip stripPrefixOverlap
(<\>) = flip stripSuffixOverlap

In addition, the monus operation <\> must satisfy the following laws:

a <\> a == mempty

mempty <\> a == mempty

a <> (b <\> a) == b <> (a <\> b)

(a <\> b) <\> c == a <\> (b <> c)

Class of monoids for which the greatest overlap can be found between any two values, such that

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 == b

The 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 == a

Identity

overlap mempty a == mempty

overlap a mempty == mempty