Data.Monoid.Cancellative

This module defines the Monoid => ReductiveMonoid => (CancellativeMonoid, GCDMonoid) class hierarchy.

The ReductiveMonoid class introduces operation </> which is the inverse of <>. For the Sum monoid, this operation is subtraction; for Product it is division and for Set it's the set difference. A ReductiveMonoid is not a full group because </> may return Nothing.

The CancellativeMonoid subclass does not add any operation but it provides the additional guarantee that <> can always be undone with </>. Thus Sum is a CancellativeMonoid but Product is not because (0*n)/0 is not defined.

The GCDMonoid subclass adds the gcd operation which takes two monoidal arguments and finds their greatest common divisor, or (more generally) the greatest monoid that can be extracted with the </> operation from both.

All monoid subclasses listed above are for Abelian, i.e., commutative or symmetric monoids. Since most practical monoids in Haskell are not Abelian, each of the these classes has two symmetric superclasses:

• LeftReductiveMonoid
• LeftCancellativeMonoid
• LeftGCDMonoid
• RightReductiveMonoid
• RightCancellativeMonoid
• RightGCDMonoid

Symmetric, commutative monoid classes

class Monoid m => CommutativeMonoid m

Class of all Abelian ({i.e.}, commutative) monoids that satisfy the commutativity property:

a <> b == b <> a

Instances

CommutativeMonoid ()

CommutativeMonoid IntSet

CommutativeMonoid a => CommutativeMonoid (Dual a)

Num a => CommutativeMonoid (Sum a)

Num a => CommutativeMonoid (Product a)

Ord a => CommutativeMonoid (Set a)

(CommutativeMonoid a, CommutativeMonoid b) => CommutativeMonoid (a, b)

(CommutativeMonoid a, CommutativeMonoid b, CommutativeMonoid c) => CommutativeMonoid (a, b, c)

(CommutativeMonoid a, CommutativeMonoid b, CommutativeMonoid c, CommutativeMonoid d) => CommutativeMonoid (a, b, c, d)

class (CommutativeMonoid m, LeftReductiveMonoid m, RightReductiveMonoid m) => ReductiveMonoid m where

Class of Abelian monoids with a partial inverse for the Monoid <> operation. The inverse operation </> must satisfy the following laws:

maybe a (b <>) (a </> b) == a
maybe a (<> b) (a </> b) == a

Minimal complete definition

(</>)

Methods

(</>) :: m -> m -> Maybe m infix 5

Instances

ReductiveMonoid ()

Methods

(</>) :: () -> () -> Maybe ()

ReductiveMonoid IntSet

Methods

(</>) :: IntSet -> IntSet -> Maybe IntSet

ReductiveMonoid a => ReductiveMonoid (Dual a)

Methods

(</>) :: Dual a -> Dual a -> Maybe (Dual a)

Integral a => ReductiveMonoid (Sum a)

Methods

(</>) :: Sum a -> Sum a -> Maybe (Sum a)

Integral a => ReductiveMonoid (Product a)

Methods

(</>) :: Product a -> Product a -> Maybe (Product a)

Ord a => ReductiveMonoid (Set a)

Methods

(</>) :: Set a -> Set a -> Maybe (Set a)

(ReductiveMonoid a, ReductiveMonoid b) => ReductiveMonoid (a, b)

Methods

(</>) :: (a, b) -> (a, b) -> Maybe (a, b)

(ReductiveMonoid a, ReductiveMonoid b, ReductiveMonoid c) => ReductiveMonoid (a, b, c)

Methods

(</>) :: (a, b, c) -> (a, b, c) -> Maybe (a, b, c)

(ReductiveMonoid a, ReductiveMonoid b, ReductiveMonoid c, ReductiveMonoid d) => ReductiveMonoid (a, b, c, d)

Methods

(</>) :: (a, b, c, d) -> (a, b, c, d) -> Maybe (a, b, c, d)

class (LeftCancellativeMonoid m, RightCancellativeMonoid m, ReductiveMonoid m) => CancellativeMonoid m

Subclass of ReductiveMonoid where </> is a complete inverse of the Monoid <> operation. The class instances must satisfy the following additional laws:

(a <> b) </> a == Just b
(a <> b) </> b == Just a

Instances

CancellativeMonoid ()

CancellativeMonoid a => CancellativeMonoid (Dual a)

Integral a => CancellativeMonoid (Sum a)

(CancellativeMonoid a, CancellativeMonoid b) => CancellativeMonoid (a, b)

(CancellativeMonoid a, CancellativeMonoid b, CancellativeMonoid c) => CancellativeMonoid (a, b, c)

(CancellativeMonoid a, CancellativeMonoid b, CancellativeMonoid c, CancellativeMonoid d) => CancellativeMonoid (a, b, c, d)

class (ReductiveMonoid m, LeftGCDMonoid m, RightGCDMonoid m) => GCDMonoid m where

Class of Abelian monoids that allow the greatest common denominator to be found for any two given values. The operations must satisfy the following laws:

gcd a b == commonPrefix a b == commonSuffix a b
Just a' = a </> p && Just b' = b </> p
   where p = gcd a b

If a GCDMonoid happens to also be a CancellativeMonoid, it should additionally satisfy the following laws:

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

Minimal complete definition

gcd

Methods

gcd :: m -> m -> m

Instances

GCDMonoid ()

Methods

gcd :: () -> () -> ()

GCDMonoid IntSet

Methods

gcd :: IntSet -> IntSet -> IntSet

GCDMonoid a => GCDMonoid (Dual a)

Methods

gcd :: Dual a -> Dual a -> Dual a

(Integral a, Ord a) => GCDMonoid (Sum a)

Methods

gcd :: Sum a -> Sum a -> Sum a

Integral a => GCDMonoid (Product a)

Methods

gcd :: Product a -> Product a -> Product a

Ord a => GCDMonoid (Set a)

Methods

gcd :: Set a -> Set a -> Set a

(GCDMonoid a, GCDMonoid b) => GCDMonoid (a, b)

Methods

gcd :: (a, b) -> (a, b) -> (a, b)

(GCDMonoid a, GCDMonoid b, GCDMonoid c) => GCDMonoid (a, b, c)

Methods

gcd :: (a, b, c) -> (a, b, c) -> (a, b, c)

(GCDMonoid a, GCDMonoid b, GCDMonoid c, GCDMonoid d) => GCDMonoid (a, b, c, d)

Methods

gcd :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d)

Asymmetric monoid classes

class Monoid m => LeftReductiveMonoid m where

Class of monoids with a left inverse of mappend, satisfying the following law:

isPrefixOf a b == isJust (stripPrefix a b)
maybe b (a <>) (stripPrefix a b) == b
a `isPrefixOf` (a <> b)

| Every instance definition has to implement at least the stripPrefix method. Its complexity should be no worse than linear in the length of the prefix argument.

Minimal complete definition

stripPrefix

Methods

isPrefixOf :: m -> m -> Bool

stripPrefix :: m -> m -> Maybe m

Instances

LeftReductiveMonoid ()

Methods

isPrefixOf :: () -> () -> Bool

stripPrefix :: () -> () -> Maybe ()

LeftReductiveMonoid ByteString

Methods

isPrefixOf :: ByteString -> ByteString -> Bool

stripPrefix :: ByteString -> ByteString -> Maybe ByteString

LeftReductiveMonoid ByteString

Methods

isPrefixOf :: ByteString -> ByteString -> Bool

stripPrefix :: ByteString -> ByteString -> Maybe ByteString

LeftReductiveMonoid IntSet

Methods

isPrefixOf :: IntSet -> IntSet -> Bool

stripPrefix :: IntSet -> IntSet -> Maybe IntSet

LeftReductiveMonoid Text

Methods

isPrefixOf :: Text -> Text -> Bool

stripPrefix :: Text -> Text -> Maybe Text

LeftReductiveMonoid Text

Methods

isPrefixOf :: Text -> Text -> Bool

stripPrefix :: Text -> Text -> Maybe Text

LeftReductiveMonoid ByteStringUTF8

Methods

isPrefixOf :: ByteStringUTF8 -> ByteStringUTF8 -> Bool

stripPrefix :: ByteStringUTF8 -> ByteStringUTF8 -> Maybe ByteStringUTF8

Eq x => LeftReductiveMonoid [x]

Methods

isPrefixOf :: [x] -> [x] -> Bool

stripPrefix :: [x] -> [x] -> Maybe [x]

LeftReductiveMonoid x => LeftReductiveMonoid (Maybe x)

Methods

isPrefixOf :: Maybe x -> Maybe x -> Bool

stripPrefix :: Maybe x -> Maybe x -> Maybe (Maybe x)

RightReductiveMonoid a => LeftReductiveMonoid (Dual a)

Methods

isPrefixOf :: Dual a -> Dual a -> Bool

stripPrefix :: Dual a -> Dual a -> Maybe (Dual a)

Integral a => LeftReductiveMonoid (Sum a)

Methods

isPrefixOf :: Sum a -> Sum a -> Bool

stripPrefix :: Sum a -> Sum a -> Maybe (Sum a)

Integral a => LeftReductiveMonoid (Product a)

Methods

isPrefixOf :: Product a -> Product a -> Bool

stripPrefix :: Product a -> Product a -> Maybe (Product a)

LeftReductiveMonoid (IntMap a)

Methods

isPrefixOf :: IntMap a -> IntMap a -> Bool

stripPrefix :: IntMap a -> IntMap a -> Maybe (IntMap a)

Eq a => LeftReductiveMonoid (Seq a)

Methods

isPrefixOf :: Seq a -> Seq a -> Bool

stripPrefix :: Seq a -> Seq a -> Maybe (Seq a)

Ord a => LeftReductiveMonoid (Set a)

Methods

isPrefixOf :: Set a -> Set a -> Bool

stripPrefix :: Set a -> Set a -> Maybe (Set a)

Eq a => LeftReductiveMonoid (Vector a)

Methods

isPrefixOf :: Vector a -> Vector a -> Bool

stripPrefix :: Vector a -> Vector a -> Maybe (Vector a)

(StableFactorialMonoid m, TextualMonoid m, LeftReductiveMonoid m) => LeftReductiveMonoid (LinePositioned m)

Methods

isPrefixOf :: LinePositioned m -> LinePositioned m -> Bool

stripPrefix :: LinePositioned m -> LinePositioned m -> Maybe (LinePositioned m)

(StableFactorialMonoid m, LeftReductiveMonoid m) => LeftReductiveMonoid (OffsetPositioned m)

Methods

isPrefixOf :: OffsetPositioned m -> OffsetPositioned m -> Bool

stripPrefix :: OffsetPositioned m -> OffsetPositioned m -> Maybe (OffsetPositioned m)

(LeftReductiveMonoid a, StableFactorialMonoid a) => LeftReductiveMonoid (Measured a)

Methods

isPrefixOf :: Measured a -> Measured a -> Bool

stripPrefix :: Measured a -> Measured a -> Maybe (Measured a)

(LeftReductiveMonoid a, StableFactorialMonoid a) => LeftReductiveMonoid (Concat a)

Methods

isPrefixOf :: Concat a -> Concat a -> Bool

stripPrefix :: Concat a -> Concat a -> Maybe (Concat a)

(LeftReductiveMonoid a, LeftReductiveMonoid b) => LeftReductiveMonoid (a, b)

Methods

isPrefixOf :: (a, b) -> (a, b) -> Bool

stripPrefix :: (a, b) -> (a, b) -> Maybe (a, b)

Ord k => LeftReductiveMonoid (Map k a)

Methods

isPrefixOf :: Map k a -> Map k a -> Bool

stripPrefix :: Map k a -> Map k a -> Maybe (Map k a)

(LeftReductiveMonoid a, LeftReductiveMonoid b) => LeftReductiveMonoid (Stateful a b)

Methods

isPrefixOf :: Stateful a b -> Stateful a b -> Bool

stripPrefix :: Stateful a b -> Stateful a b -> Maybe (Stateful a b)

(LeftReductiveMonoid a, LeftReductiveMonoid b, LeftReductiveMonoid c) => LeftReductiveMonoid (a, b, c)

Methods

isPrefixOf :: (a, b, c) -> (a, b, c) -> Bool

stripPrefix :: (a, b, c) -> (a, b, c) -> Maybe (a, b, c)

(LeftReductiveMonoid a, LeftReductiveMonoid b, LeftReductiveMonoid c, LeftReductiveMonoid d) => LeftReductiveMonoid (a, b, c, d)

Methods

isPrefixOf :: (a, b, c, d) -> (a, b, c, d) -> Bool

stripPrefix :: (a, b, c, d) -> (a, b, c, d) -> Maybe (a, b, c, d)

class Monoid m => RightReductiveMonoid m where

Class of monoids with a right inverse of mappend, satisfying the following law:

isSuffixOf a b == isJust (stripSuffix a b)
maybe b (<> a) (stripSuffix a b) == b
b `isSuffixOf` (a <> b)

| Every instance definition has to implement at least the stripSuffix method. Its complexity should be no worse than linear in the length of the suffix argument.

Minimal complete definition

stripSuffix

Methods

isSuffixOf :: m -> m -> Bool

stripSuffix :: m -> m -> Maybe m

Instances

RightReductiveMonoid ()

Methods

isSuffixOf :: () -> () -> Bool

stripSuffix :: () -> () -> Maybe ()

RightReductiveMonoid ByteString

Methods

isSuffixOf :: ByteString -> ByteString -> Bool

stripSuffix :: ByteString -> ByteString -> Maybe ByteString

RightReductiveMonoid ByteString

Methods

isSuffixOf :: ByteString -> ByteString -> Bool

stripSuffix :: ByteString -> ByteString -> Maybe ByteString

RightReductiveMonoid IntSet

Methods

isSuffixOf :: IntSet -> IntSet -> Bool

stripSuffix :: IntSet -> IntSet -> Maybe IntSet

RightReductiveMonoid Text

Methods

isSuffixOf :: Text -> Text -> Bool

stripSuffix :: Text -> Text -> Maybe Text

RightReductiveMonoid Text

Methods

isSuffixOf :: Text -> Text -> Bool

stripSuffix :: Text -> Text -> Maybe Text

RightReductiveMonoid x => RightReductiveMonoid (Maybe x)

Methods

isSuffixOf :: Maybe x -> Maybe x -> Bool

stripSuffix :: Maybe x -> Maybe x -> Maybe (Maybe x)

LeftReductiveMonoid a => RightReductiveMonoid (Dual a)

Methods

isSuffixOf :: Dual a -> Dual a -> Bool

stripSuffix :: Dual a -> Dual a -> Maybe (Dual a)

Integral a => RightReductiveMonoid (Sum a)

Methods

isSuffixOf :: Sum a -> Sum a -> Bool

stripSuffix :: Sum a -> Sum a -> Maybe (Sum a)

Integral a => RightReductiveMonoid (Product a)

Methods

isSuffixOf :: Product a -> Product a -> Bool

stripSuffix :: Product a -> Product a -> Maybe (Product a)

Eq a => RightReductiveMonoid (Seq a)

Methods

isSuffixOf :: Seq a -> Seq a -> Bool

stripSuffix :: Seq a -> Seq a -> Maybe (Seq a)

Ord a => RightReductiveMonoid (Set a)

Methods

isSuffixOf :: Set a -> Set a -> Bool

stripSuffix :: Set a -> Set a -> Maybe (Set a)

Eq a => RightReductiveMonoid (Vector a)

Methods

isSuffixOf :: Vector a -> Vector a -> Bool

stripSuffix :: Vector a -> Vector a -> Maybe (Vector a)

(StableFactorialMonoid m, TextualMonoid m, RightReductiveMonoid m) => RightReductiveMonoid (LinePositioned m)

Methods

isSuffixOf :: LinePositioned m -> LinePositioned m -> Bool

stripSuffix :: LinePositioned m -> LinePositioned m -> Maybe (LinePositioned m)

(StableFactorialMonoid m, RightReductiveMonoid m) => RightReductiveMonoid (OffsetPositioned m)

Methods

isSuffixOf :: OffsetPositioned m -> OffsetPositioned m -> Bool

stripSuffix :: OffsetPositioned m -> OffsetPositioned m -> Maybe (OffsetPositioned m)

(RightReductiveMonoid a, StableFactorialMonoid a) => RightReductiveMonoid (Measured a)

Methods

isSuffixOf :: Measured a -> Measured a -> Bool

stripSuffix :: Measured a -> Measured a -> Maybe (Measured a)

(RightReductiveMonoid a, StableFactorialMonoid a) => RightReductiveMonoid (Concat a)

Methods

isSuffixOf :: Concat a -> Concat a -> Bool

stripSuffix :: Concat a -> Concat a -> Maybe (Concat a)

(RightReductiveMonoid a, RightReductiveMonoid b) => RightReductiveMonoid (a, b)

Methods

isSuffixOf :: (a, b) -> (a, b) -> Bool

stripSuffix :: (a, b) -> (a, b) -> Maybe (a, b)

(RightReductiveMonoid a, RightReductiveMonoid b) => RightReductiveMonoid (Stateful a b)

Methods

isSuffixOf :: Stateful a b -> Stateful a b -> Bool

stripSuffix :: Stateful a b -> Stateful a b -> Maybe (Stateful a b)

(RightReductiveMonoid a, RightReductiveMonoid b, RightReductiveMonoid c) => RightReductiveMonoid (a, b, c)

Methods

isSuffixOf :: (a, b, c) -> (a, b, c) -> Bool

stripSuffix :: (a, b, c) -> (a, b, c) -> Maybe (a, b, c)

(RightReductiveMonoid a, RightReductiveMonoid b, RightReductiveMonoid c, RightReductiveMonoid d) => RightReductiveMonoid (a, b, c, d)

Methods

isSuffixOf :: (a, b, c, d) -> (a, b, c, d) -> Bool

stripSuffix :: (a, b, c, d) -> (a, b, c, d) -> Maybe (a, b, c, d)

class LeftReductiveMonoid m => LeftCancellativeMonoid m

Subclass of LeftReductiveMonoid where stripPrefix is a complete inverse of <>, satisfying the following additional law:

stripPrefix a (a <> b) == Just b

Instances

LeftCancellativeMonoid ()

LeftCancellativeMonoid ByteString

LeftCancellativeMonoid ByteString

LeftCancellativeMonoid Text

LeftCancellativeMonoid Text

LeftCancellativeMonoid ByteStringUTF8

Eq x => LeftCancellativeMonoid [x]

RightCancellativeMonoid a => LeftCancellativeMonoid (Dual a)

Integral a => LeftCancellativeMonoid (Sum a)

Eq a => LeftCancellativeMonoid (Seq a)

Eq a => LeftCancellativeMonoid (Vector a)

(LeftCancellativeMonoid a, LeftCancellativeMonoid b) => LeftCancellativeMonoid (a, b)

(LeftCancellativeMonoid a, LeftCancellativeMonoid b, LeftCancellativeMonoid c) => LeftCancellativeMonoid (a, b, c)

(LeftCancellativeMonoid a, LeftCancellativeMonoid b, LeftCancellativeMonoid c, LeftCancellativeMonoid d) => LeftCancellativeMonoid (a, b, c, d)

class RightReductiveMonoid m => RightCancellativeMonoid m

Subclass of LeftReductiveMonoid where stripPrefix is a complete inverse of <>, satisfying the following additional law:

stripSuffix b (a <> b) == Just a

Instances

RightCancellativeMonoid ()

RightCancellativeMonoid ByteString

RightCancellativeMonoid ByteString

RightCancellativeMonoid Text

RightCancellativeMonoid Text

LeftCancellativeMonoid a => RightCancellativeMonoid (Dual a)

Integral a => RightCancellativeMonoid (Sum a)

Eq a => RightCancellativeMonoid (Seq a)

Eq a => RightCancellativeMonoid (Vector a)

(RightCancellativeMonoid a, RightCancellativeMonoid b) => RightCancellativeMonoid (a, b)

(RightCancellativeMonoid a, RightCancellativeMonoid b, RightCancellativeMonoid c) => RightCancellativeMonoid (a, b, c)

(RightCancellativeMonoid a, RightCancellativeMonoid b, RightCancellativeMonoid c, RightCancellativeMonoid d) => RightCancellativeMonoid (a, b, c, d)

class LeftReductiveMonoid m => LeftGCDMonoid m where

Class of monoids capable of finding the equivalent of greatest common divisor on the left side of two monoidal values. The methods' complexity should be no worse than linear in the length of the common prefix. The following laws must be respected:

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 b

Minimal complete definition

commonPrefix | stripCommonPrefix

Methods

commonPrefix :: m -> m -> m

stripCommonPrefix :: m -> m -> (m, m, m)

Instances

LeftGCDMonoid ()

Methods

commonPrefix :: () -> () -> ()

stripCommonPrefix :: () -> () -> ((), (), ())

LeftGCDMonoid ByteString

Methods

commonPrefix :: ByteString -> ByteString -> ByteString

stripCommonPrefix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)

LeftGCDMonoid ByteString

Methods

commonPrefix :: ByteString -> ByteString -> ByteString

stripCommonPrefix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)

LeftGCDMonoid IntSet

Methods

commonPrefix :: IntSet -> IntSet -> IntSet

stripCommonPrefix :: IntSet -> IntSet -> (IntSet, IntSet, IntSet)

LeftGCDMonoid Text

Methods

commonPrefix :: Text -> Text -> Text

stripCommonPrefix :: Text -> Text -> (Text, Text, Text)

LeftGCDMonoid Text

Methods

commonPrefix :: Text -> Text -> Text

stripCommonPrefix :: Text -> Text -> (Text, Text, Text)

LeftGCDMonoid ByteStringUTF8

Methods

commonPrefix :: ByteStringUTF8 -> ByteStringUTF8 -> ByteStringUTF8

stripCommonPrefix :: ByteStringUTF8 -> ByteStringUTF8 -> (ByteStringUTF8, ByteStringUTF8, ByteStringUTF8)

Eq x => LeftGCDMonoid [x]

Methods

commonPrefix :: [x] -> [x] -> [x]

stripCommonPrefix :: [x] -> [x] -> ([x], [x], [x])

LeftGCDMonoid x => LeftGCDMonoid (Maybe x)

Methods

commonPrefix :: Maybe x -> Maybe x -> Maybe x

stripCommonPrefix :: Maybe x -> Maybe x -> (Maybe x, Maybe x, Maybe x)

RightGCDMonoid a => LeftGCDMonoid (Dual a)

Methods

commonPrefix :: Dual a -> Dual a -> Dual a

stripCommonPrefix :: Dual a -> Dual a -> (Dual a, Dual a, Dual a)

(Integral a, Ord a) => LeftGCDMonoid (Sum a)

Methods

commonPrefix :: Sum a -> Sum a -> Sum a

stripCommonPrefix :: Sum a -> Sum a -> (Sum a, Sum a, Sum a)

Integral a => LeftGCDMonoid (Product a)

Methods

commonPrefix :: Product a -> Product a -> Product a

stripCommonPrefix :: Product a -> Product a -> (Product a, Product a, Product a)

Eq a => LeftGCDMonoid (IntMap a)

Methods

commonPrefix :: IntMap a -> IntMap a -> IntMap a

stripCommonPrefix :: IntMap a -> IntMap a -> (IntMap a, IntMap a, IntMap a)

Eq a => LeftGCDMonoid (Seq a)

Methods

commonPrefix :: Seq a -> Seq a -> Seq a

stripCommonPrefix :: Seq a -> Seq a -> (Seq a, Seq a, Seq a)

Ord a => LeftGCDMonoid (Set a)

Methods

commonPrefix :: Set a -> Set a -> Set a

stripCommonPrefix :: Set a -> Set a -> (Set a, Set a, Set a)

Eq a => LeftGCDMonoid (Vector a)

Methods

commonPrefix :: Vector a -> Vector a -> Vector a

stripCommonPrefix :: Vector a -> Vector a -> (Vector a, Vector a, Vector a)

(StableFactorialMonoid m, TextualMonoid m, LeftGCDMonoid m) => LeftGCDMonoid (LinePositioned m)

Methods

commonPrefix :: LinePositioned m -> LinePositioned m -> LinePositioned m

stripCommonPrefix :: LinePositioned m -> LinePositioned m -> (LinePositioned m, LinePositioned m, LinePositioned m)

(StableFactorialMonoid m, LeftGCDMonoid m) => LeftGCDMonoid (OffsetPositioned m)

Methods

commonPrefix :: OffsetPositioned m -> OffsetPositioned m -> OffsetPositioned m

stripCommonPrefix :: OffsetPositioned m -> OffsetPositioned m -> (OffsetPositioned m, OffsetPositioned m, OffsetPositioned m)

(LeftGCDMonoid a, StableFactorialMonoid a) => LeftGCDMonoid (Measured a)

Methods

commonPrefix :: Measured a -> Measured a -> Measured a

stripCommonPrefix :: Measured a -> Measured a -> (Measured a, Measured a, Measured a)

(LeftGCDMonoid a, StableFactorialMonoid a) => LeftGCDMonoid (Concat a)

Methods

commonPrefix :: Concat a -> Concat a -> Concat a

stripCommonPrefix :: Concat a -> Concat a -> (Concat a, Concat a, Concat a)

(LeftGCDMonoid a, LeftGCDMonoid b) => LeftGCDMonoid (a, b)

Methods

commonPrefix :: (a, b) -> (a, b) -> (a, b)

stripCommonPrefix :: (a, b) -> (a, b) -> ((a, b), (a, b), (a, b))

(Ord k, Eq a) => LeftGCDMonoid (Map k a)

Methods

commonPrefix :: Map k a -> Map k a -> Map k a

stripCommonPrefix :: Map k a -> Map k a -> (Map k a, Map k a, Map k a)

(LeftGCDMonoid a, LeftGCDMonoid b) => LeftGCDMonoid (Stateful a b)

Methods

commonPrefix :: Stateful a b -> Stateful a b -> Stateful a b

stripCommonPrefix :: Stateful a b -> Stateful a b -> (Stateful a b, Stateful a b, Stateful a b)

(LeftGCDMonoid a, LeftGCDMonoid b, LeftGCDMonoid c) => LeftGCDMonoid (a, b, c)

Methods

commonPrefix :: (a, b, c) -> (a, b, c) -> (a, b, c)

stripCommonPrefix :: (a, b, c) -> (a, b, c) -> ((a, b, c), (a, b, c), (a, b, c))

(LeftGCDMonoid a, LeftGCDMonoid b, LeftGCDMonoid c, LeftGCDMonoid d) => LeftGCDMonoid (a, b, c, d)

Methods

commonPrefix :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d)

stripCommonPrefix :: (a, b, c, d) -> (a, b, c, d) -> ((a, b, c, d), (a, b, c, d), (a, b, c, d))

class RightReductiveMonoid m => RightGCDMonoid m where

Class of monoids capable of finding the equivalent of greatest common divisor on the right side of two monoidal values. The methods' complexity must be no worse than linear in the length of the common suffix. The following laws must be respected:

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 b

Minimal complete definition

commonSuffix | stripCommonSuffix

Methods

commonSuffix :: m -> m -> m

stripCommonSuffix :: m -> m -> (m, m, m)

Instances

RightGCDMonoid ()

Methods

commonSuffix :: () -> () -> ()

stripCommonSuffix :: () -> () -> ((), (), ())

RightGCDMonoid ByteString

Methods

commonSuffix :: ByteString -> ByteString -> ByteString

stripCommonSuffix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)

RightGCDMonoid ByteString

Methods

commonSuffix :: ByteString -> ByteString -> ByteString

stripCommonSuffix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)

RightGCDMonoid IntSet

Methods

commonSuffix :: IntSet -> IntSet -> IntSet

stripCommonSuffix :: IntSet -> IntSet -> (IntSet, IntSet, IntSet)

RightGCDMonoid x => RightGCDMonoid (Maybe x)

Methods

commonSuffix :: Maybe x -> Maybe x -> Maybe x

stripCommonSuffix :: Maybe x -> Maybe x -> (Maybe x, Maybe x, Maybe x)

LeftGCDMonoid a => RightGCDMonoid (Dual a)

Methods

commonSuffix :: Dual a -> Dual a -> Dual a

stripCommonSuffix :: Dual a -> Dual a -> (Dual a, Dual a, Dual a)

(Integral a, Ord a) => RightGCDMonoid (Sum a)

Methods

commonSuffix :: Sum a -> Sum a -> Sum a

stripCommonSuffix :: Sum a -> Sum a -> (Sum a, Sum a, Sum a)

Integral a => RightGCDMonoid (Product a)

Methods

commonSuffix :: Product a -> Product a -> Product a

stripCommonSuffix :: Product a -> Product a -> (Product a, Product a, Product a)

Eq a => RightGCDMonoid (Seq a)

Methods

commonSuffix :: Seq a -> Seq a -> Seq a

stripCommonSuffix :: Seq a -> Seq a -> (Seq a, Seq a, Seq a)

Ord a => RightGCDMonoid (Set a)

Methods

commonSuffix :: Set a -> Set a -> Set a

stripCommonSuffix :: Set a -> Set a -> (Set a, Set a, Set a)

Eq a => RightGCDMonoid (Vector a)

Methods

commonSuffix :: Vector a -> Vector a -> Vector a

stripCommonSuffix :: Vector a -> Vector a -> (Vector a, Vector a, Vector a)

(StableFactorialMonoid m, TextualMonoid m, RightGCDMonoid m) => RightGCDMonoid (LinePositioned m)

Methods

commonSuffix :: LinePositioned m -> LinePositioned m -> LinePositioned m

stripCommonSuffix :: LinePositioned m -> LinePositioned m -> (LinePositioned m, LinePositioned m, LinePositioned m)

(StableFactorialMonoid m, RightGCDMonoid m) => RightGCDMonoid (OffsetPositioned m)

Methods

commonSuffix :: OffsetPositioned m -> OffsetPositioned m -> OffsetPositioned m

stripCommonSuffix :: OffsetPositioned m -> OffsetPositioned m -> (OffsetPositioned m, OffsetPositioned m, OffsetPositioned m)

(RightGCDMonoid a, StableFactorialMonoid a) => RightGCDMonoid (Measured a)

Methods

commonSuffix :: Measured a -> Measured a -> Measured a

stripCommonSuffix :: Measured a -> Measured a -> (Measured a, Measured a, Measured a)

(RightGCDMonoid a, StableFactorialMonoid a) => RightGCDMonoid (Concat a)

Methods

commonSuffix :: Concat a -> Concat a -> Concat a

stripCommonSuffix :: Concat a -> Concat a -> (Concat a, Concat a, Concat a)

(RightGCDMonoid a, RightGCDMonoid b) => RightGCDMonoid (a, b)

Methods

commonSuffix :: (a, b) -> (a, b) -> (a, b)

stripCommonSuffix :: (a, b) -> (a, b) -> ((a, b), (a, b), (a, b))

(RightGCDMonoid a, RightGCDMonoid b) => RightGCDMonoid (Stateful a b)

Methods

commonSuffix :: Stateful a b -> Stateful a b -> Stateful a b

stripCommonSuffix :: Stateful a b -> Stateful a b -> (Stateful a b, Stateful a b, Stateful a b)

(RightGCDMonoid a, RightGCDMonoid b, RightGCDMonoid c) => RightGCDMonoid (a, b, c)

Methods

commonSuffix :: (a, b, c) -> (a, b, c) -> (a, b, c)

stripCommonSuffix :: (a, b, c) -> (a, b, c) -> ((a, b, c), (a, b, c), (a, b, c))

(RightGCDMonoid a, RightGCDMonoid b, RightGCDMonoid c, RightGCDMonoid d) => RightGCDMonoid (a, b, c, d)

Methods

commonSuffix :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d)

stripCommonSuffix :: (a, b, c, d) -> (a, b, c, d) -> ((a, b, c, d), (a, b, c, d), (a, b, c, d))