monoid-subclasses-1.2.6: Subclasses of Monoid

Safe Haskell | Trustworthy
Language | Haskell2010

Data.Monoid.GCD

Description

This module defines the `GCDMonoid` subclass of the `Monoid` class.

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.

The `GCDMonoid` class is for Abelian, i.e., `Commutative` monoids.

## Non-commutative GCD monoids

Since most practical monoids in Haskell are not Abelian, the `GCDMonoid` class has three symmetric superclasses:

- `LeftGCDMonoid`

  Class of monoids for which it is possible to find the greatest common prefix of two monoidal values.

- `RightGCDMonoid`

  Class of monoids for which it is possible to find the greatest common suffix of two monoidal values.

- `OverlappingGCDMonoid`

  Class of monoids for which it is possible to find the greatest common overlap of two monoidal values.

## Distributive GCD monoids

Since some (but not all) GCD monoids are also distributive, there are three subclasses that add distributivity:

- `DistributiveGCDMonoid`

  Subclass of `GCDMonoid` with symmetric distributivity.

- `LeftDistributiveGCDMonoid`

  Subclass of `LeftGCDMonoid` with left-distributivity.

- `RightDistributiveGCDMonoid`

  Subclass of `RightGCDMonoid` with right-distributivity.

Synopsis

- class (Monoid m, Commutative m, Reductive m, LeftGCDMonoid m, RightGCDMonoid m, OverlappingGCDMonoid m) => GCDMonoid m where
  - gcd :: m -> m -> m
- class (Monoid m, LeftReductive m) => LeftGCDMonoid m where
  - commonPrefix :: m -> m -> m
  - stripCommonPrefix :: m -> m -> (m, m, m)
- class (Monoid m, RightReductive m) => RightGCDMonoid m where
  - commonSuffix :: m -> m -> m
  - stripCommonSuffix :: m -> m -> (m, m, m)
- class (Monoid m, LeftReductive m, RightReductive m) => OverlappingGCDMonoid m where
  - stripPrefixOverlap :: m -> m -> m
  - stripSuffixOverlap :: m -> m -> m
  - overlap :: m -> m -> m
  - stripOverlap :: m -> m -> (m, m, m)
- class (LeftDistributiveGCDMonoid m, RightDistributiveGCDMonoid m, GCDMonoid m) => DistributiveGCDMonoid m
- class LeftGCDMonoid m => LeftDistributiveGCDMonoid m
- class RightGCDMonoid m => RightDistributiveGCDMonoid m

# Documentation

class (Monoid m, Commutative m, Reductive m, LeftGCDMonoid m, RightGCDMonoid m, OverlappingGCDMonoid m) => GCDMonoid m where Source #

Class of Abelian monoids that allow the greatest common divisor 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

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

Identity

    gcd mempty a == mempty

    gcd a mempty == mempty

Commutativity

    gcd a b == gcd b a

Associativity

    gcd (gcd a b) c == gcd a (gcd b c)

Methods

gcd :: m -> m -> m Source #

#### Instances

Instances details

GCDMonoid IntSet Source # | O(m+n)
Instance details Defined in Data.Monoid.GCD Methods gcd :: IntSet -> IntSet -> IntSet Source #
GCDMonoid () Source # | O(1)
Instance details Defined in Data.Monoid.GCD Methods gcd :: () -> () -> () Source #
Ord a => GCDMonoid (Set a) Source # | O(m*log(n/m + 1)), m <= n
Instance details Defined in Data.Monoid.GCD Methods gcd :: Set a -> Set a -> Set a Source #
GCDMonoid a => GCDMonoid (Identity a) Source # |
Instance details Defined in Data.Monoid.GCD Methods gcd :: Identity a -> Identity a -> Identity a Source #
GCDMonoid a => GCDMonoid (Dual a) Source # |
Instance details Defined in Data.Monoid.GCD Methods gcd :: Dual a -> Dual a -> Dual a Source #
GCDMonoid (Product Natural) Source # | O(1)
Instance details Defined in Data.Monoid.GCD Methods gcd :: Product Natural -> Product Natural -> Product Natural Source #
GCDMonoid (Sum Natural) Source # | O(1)
Instance details Defined in Data.Monoid.GCD Methods gcd :: Sum Natural -> Sum Natural -> Sum Natural Source #
(GCDMonoid a, GCDMonoid b) => GCDMonoid (a, b) Source # |
Instance details Defined in Data.Monoid.GCD Methods gcd :: (a, b) -> (a, b) -> (a, b) Source #
GCDMonoid a => GCDMonoid (Const a b) Source # |
Instance details Defined in Data.Monoid.GCD Methods gcd :: Const a b -> Const a b -> Const a b Source #
(GCDMonoid a, GCDMonoid b, GCDMonoid c) => GCDMonoid (a, b, c) Source # |
Instance details Defined in Data.Monoid.GCD Methods gcd :: (a, b, c) -> (a, b, c) -> (a, b, c) Source #
(GCDMonoid a, GCDMonoid b, GCDMonoid c, GCDMonoid d) => GCDMonoid (a, b, c, d) Source # |
Instance details Defined in Data.Monoid.GCD Methods gcd :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d) Source #

class (Monoid m, LeftReductive m) => LeftGCDMonoid m where Source #

Class of monoids capable of finding the equivalent of greatest common divisor on the left side of two monoidal values. 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

Furthermore, `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 b

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

Identity

    commonPrefix mempty a == mempty

    commonPrefix a mempty == mempty

Commutativity

    commonPrefix a b == commonPrefix b a

Associativity

    commonPrefix (commonPrefix a b) c
    ==
    commonPrefix a (commonPrefix b c)

Minimal complete definition

commonPrefix | stripCommonPrefix

Methods

commonPrefix :: m -> m -> m Source #

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

#### Instances

Instances details

LeftGCDMonoid ByteString Source # | O(prefixLength)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: ByteString -> ByteString -> ByteString Source # stripCommonPrefix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString) Source #
LeftGCDMonoid ByteString Source # | O(prefixLength)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: ByteString -> ByteString -> ByteString Source # stripCommonPrefix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString) Source #
LeftGCDMonoid IntSet Source # | O(m+n)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: IntSet -> IntSet -> IntSet Source # stripCommonPrefix :: IntSet -> IntSet -> (IntSet, IntSet, IntSet) Source #
LeftGCDMonoid ByteStringUTF8 Source # | O(prefixLength)
Instance details Defined in Data.Monoid.Instances.ByteString.UTF8 Methods commonPrefix :: ByteStringUTF8 -> ByteStringUTF8 -> ByteStringUTF8 Source # stripCommonPrefix :: ByteStringUTF8 -> ByteStringUTF8 -> (ByteStringUTF8, ByteStringUTF8, ByteStringUTF8) Source #
LeftGCDMonoid Text Source # | O(prefixLength)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: Text -> Text -> Text Source # stripCommonPrefix :: Text -> Text -> (Text, Text, Text) Source #
LeftGCDMonoid Text Source # | O(prefixLength)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: Text -> Text -> Text Source # stripCommonPrefix :: Text -> Text -> (Text, Text, Text) Source #
LeftGCDMonoid () Source # | O(1)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: () -> () -> () Source # stripCommonPrefix :: () -> () -> ((), (), ()) Source #
Eq a => LeftGCDMonoid (IntMap a) Source # | O(m+n)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: IntMap a -> IntMap a -> IntMap a Source # stripCommonPrefix :: IntMap a -> IntMap a -> (IntMap a, IntMap a, IntMap a) Source #
Eq a => LeftGCDMonoid (Seq a) Source # | O(prefixLength)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: Seq a -> Seq a -> Seq a Source # stripCommonPrefix :: Seq a -> Seq a -> (Seq a, Seq a, Seq a) Source #
Ord a => LeftGCDMonoid (Set a) Source # | O(m*log(n/m + 1)), m <= n
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: Set a -> Set a -> Set a Source # stripCommonPrefix :: Set a -> Set a -> (Set a, Set a, Set a) Source #
LeftGCDMonoid a => LeftGCDMonoid (Identity a) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: Identity a -> Identity a -> Identity a Source # stripCommonPrefix :: Identity a -> Identity a -> (Identity a, Identity a, Identity a) Source #
RightGCDMonoid a => LeftGCDMonoid (Dual a) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: Dual a -> Dual a -> Dual a Source # stripCommonPrefix :: Dual a -> Dual a -> (Dual a, Dual a, Dual a) Source #
LeftGCDMonoid (Product Natural) Source # | O(1)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: Product Natural -> Product Natural -> Product Natural Source # stripCommonPrefix :: Product Natural -> Product Natural -> (Product Natural, Product Natural, Product Natural) Source #
LeftGCDMonoid (Sum Natural) Source # | O(1)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: Sum Natural -> Sum Natural -> Sum Natural Source # stripCommonPrefix :: Sum Natural -> Sum Natural -> (Sum Natural, Sum Natural, Sum Natural) Source #
(LeftGCDMonoid a, StableFactorial a, PositiveMonoid a) => LeftGCDMonoid (Concat a) Source # |
Instance details Defined in Data.Monoid.Instances.Concat Methods commonPrefix :: Concat a -> Concat a -> Concat a Source # stripCommonPrefix :: Concat a -> Concat a -> (Concat a, Concat a, Concat a) Source #
(LeftGCDMonoid a, StableFactorial a) => LeftGCDMonoid (Measured a) Source # |
Instance details Defined in Data.Monoid.Instances.Measured Methods commonPrefix :: Measured a -> Measured a -> Measured a Source # stripCommonPrefix :: Measured a -> Measured a -> (Measured a, Measured a, Measured a) Source #
(StableFactorial m, TextualMonoid m, LeftGCDMonoid m) => LeftGCDMonoid (LinePositioned m) Source # |
Instance details Defined in Data.Monoid.Instances.Positioned Methods commonPrefix :: LinePositioned m -> LinePositioned m -> LinePositioned m Source # stripCommonPrefix :: LinePositioned m -> LinePositioned m -> (LinePositioned m, LinePositioned m, LinePositioned m) Source #
(StableFactorial m, FactorialMonoid m, LeftGCDMonoid m) => LeftGCDMonoid (OffsetPositioned m) Source # |
Instance details Defined in Data.Monoid.Instances.Positioned Methods commonPrefix :: OffsetPositioned m -> OffsetPositioned m -> OffsetPositioned m Source # stripCommonPrefix :: OffsetPositioned m -> OffsetPositioned m -> (OffsetPositioned m, OffsetPositioned m, OffsetPositioned m) Source #
(Eq m, StableFactorial m, FactorialMonoid m, LeftGCDMonoid m) => LeftGCDMonoid (Shadowed m) Source # |
Instance details Defined in Data.Monoid.Instances.PrefixMemory Methods commonPrefix :: Shadowed m -> Shadowed m -> Shadowed m Source # stripCommonPrefix :: Shadowed m -> Shadowed m -> (Shadowed m, Shadowed m, Shadowed m) Source #
Eq a => LeftGCDMonoid (Vector a) Source # | O(prefixLength)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: Vector a -> Vector a -> Vector a Source # stripCommonPrefix :: Vector a -> Vector a -> (Vector a, Vector a, Vector a) Source #
LeftGCDMonoid x => LeftGCDMonoid (Maybe x) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: Maybe x -> Maybe x -> Maybe x Source # stripCommonPrefix :: Maybe x -> Maybe x -> (Maybe x, Maybe x, Maybe x) Source #
Eq x => LeftGCDMonoid [x] Source # | O(prefixLength)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: [x] -> [x] -> [x] Source # stripCommonPrefix :: [x] -> [x] -> ([x], [x], [x]) Source #
(Ord k, Eq a) => LeftGCDMonoid (Map k a) Source # | O(m+n)
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: Map k a -> Map k a -> Map k a Source # stripCommonPrefix :: Map k a -> Map k a -> (Map k a, Map k a, Map k a) Source #
(LeftGCDMonoid a, LeftGCDMonoid b) => LeftGCDMonoid (Stateful a b) Source # |
Instance details Defined in Data.Monoid.Instances.Stateful Methods commonPrefix :: Stateful a b -> Stateful a b -> Stateful a b Source # stripCommonPrefix :: Stateful a b -> Stateful a b -> (Stateful a b, Stateful a b, Stateful a b) Source #
(LeftGCDMonoid a, LeftGCDMonoid b) => LeftGCDMonoid (a, b) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: (a, b) -> (a, b) -> (a, b) Source # stripCommonPrefix :: (a, b) -> (a, b) -> ((a, b), (a, b), (a, b)) Source #
LeftGCDMonoid a => LeftGCDMonoid (Const a b) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: Const a b -> Const a b -> Const a b Source # stripCommonPrefix :: Const a b -> Const a b -> (Const a b, Const a b, Const a b) Source #
(LeftGCDMonoid a, LeftGCDMonoid b, LeftGCDMonoid c) => LeftGCDMonoid (a, b, c) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: (a, b, c) -> (a, b, c) -> (a, b, c) Source # stripCommonPrefix :: (a, b, c) -> (a, b, c) -> ((a, b, c), (a, b, c), (a, b, c)) Source #
(LeftGCDMonoid a, LeftGCDMonoid b, LeftGCDMonoid c, LeftGCDMonoid d) => LeftGCDMonoid (a, b, c, d) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonPrefix :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d) Source # stripCommonPrefix :: (a, b, c, d) -> (a, b, c, d) -> ((a, b, c, d), (a, b, c, d), (a, b, c, d)) Source #

class (Monoid m, RightReductive m) => RightGCDMonoid m where Source #

Class of monoids capable of finding the equivalent of greatest common divisor on the right side of two monoidal values. 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

Furthermore, `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 b

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

Identity

    commonSuffix mempty a == mempty

    commonSuffix a mempty == mempty

Commutativity

    commonSuffix a b == commonSuffix b a

Associativity

    commonSuffix (commonSuffix a b) c
    ==
    commonSuffix a (commonSuffix b c)

Minimal complete definition

commonSuffix | stripCommonSuffix

Methods

commonSuffix :: m -> m -> m Source #

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

#### Instances

Instances details

RightGCDMonoid ByteString Source # | O(suffixLength)
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: ByteString -> ByteString -> ByteString Source # stripCommonSuffix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString) Source #
RightGCDMonoid ByteString Source # | O(suffixLength)
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: ByteString -> ByteString -> ByteString Source # stripCommonSuffix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString) Source #
RightGCDMonoid IntSet Source # | O(m+n)
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: IntSet -> IntSet -> IntSet Source # stripCommonSuffix :: IntSet -> IntSet -> (IntSet, IntSet, IntSet) Source #
RightGCDMonoid Text Source # | O(suffixLength), except on GHCjs where it is O(m+n) Since: 1.0
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: Text -> Text -> Text Source # stripCommonSuffix :: Text -> Text -> (Text, Text, Text) Source #
RightGCDMonoid Text Source # | O(m+n) Since: 1.0
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: Text -> Text -> Text Source # stripCommonSuffix :: Text -> Text -> (Text, Text, Text) Source #
RightGCDMonoid () Source # | O(1)
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: () -> () -> () Source # stripCommonSuffix :: () -> () -> ((), (), ()) Source #
Eq a => RightGCDMonoid (Seq a) Source # | O(suffixLength)
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: Seq a -> Seq a -> Seq a Source # stripCommonSuffix :: Seq a -> Seq a -> (Seq a, Seq a, Seq a) Source #
Ord a => RightGCDMonoid (Set a) Source # | O(m*log(n/m + 1)), m <= n
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: Set a -> Set a -> Set a Source # stripCommonSuffix :: Set a -> Set a -> (Set a, Set a, Set a) Source #
RightGCDMonoid a => RightGCDMonoid (Identity a) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: Identity a -> Identity a -> Identity a Source # stripCommonSuffix :: Identity a -> Identity a -> (Identity a, Identity a, Identity a) Source #
LeftGCDMonoid a => RightGCDMonoid (Dual a) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: Dual a -> Dual a -> Dual a Source # stripCommonSuffix :: Dual a -> Dual a -> (Dual a, Dual a, Dual a) Source #
RightGCDMonoid (Product Natural) Source # | O(1)
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: Product Natural -> Product Natural -> Product Natural Source # stripCommonSuffix :: Product Natural -> Product Natural -> (Product Natural, Product Natural, Product Natural) Source #
RightGCDMonoid (Sum Natural) Source # | O(1)
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: Sum Natural -> Sum Natural -> Sum Natural Source # stripCommonSuffix :: Sum Natural -> Sum Natural -> (Sum Natural, Sum Natural, Sum Natural) Source #
(RightGCDMonoid a, StableFactorial a, PositiveMonoid a) => RightGCDMonoid (Concat a) Source # |
Instance details Defined in Data.Monoid.Instances.Concat Methods commonSuffix :: Concat a -> Concat a -> Concat a Source # stripCommonSuffix :: Concat a -> Concat a -> (Concat a, Concat a, Concat a) Source #
(RightGCDMonoid a, StableFactorial a) => RightGCDMonoid (Measured a) Source # |
Instance details Defined in Data.Monoid.Instances.Measured Methods commonSuffix :: Measured a -> Measured a -> Measured a Source # stripCommonSuffix :: Measured a -> Measured a -> (Measured a, Measured a, Measured a) Source #
(StableFactorial m, TextualMonoid m, RightGCDMonoid m) => RightGCDMonoid (LinePositioned m) Source # |
Instance details Defined in Data.Monoid.Instances.Positioned Methods commonSuffix :: LinePositioned m -> LinePositioned m -> LinePositioned m Source # stripCommonSuffix :: LinePositioned m -> LinePositioned m -> (LinePositioned m, LinePositioned m, LinePositioned m) Source #
(StableFactorial m, FactorialMonoid m, RightGCDMonoid m) => RightGCDMonoid (OffsetPositioned m) Source # |
Instance details Defined in Data.Monoid.Instances.Positioned Methods commonSuffix :: OffsetPositioned m -> OffsetPositioned m -> OffsetPositioned m Source # stripCommonSuffix :: OffsetPositioned m -> OffsetPositioned m -> (OffsetPositioned m, OffsetPositioned m, OffsetPositioned m) Source #
(StableFactorial m, FactorialMonoid m, RightGCDMonoid m) => RightGCDMonoid (Shadowed m) Source # |
Instance details Defined in Data.Monoid.Instances.PrefixMemory Methods commonSuffix :: Shadowed m -> Shadowed m -> Shadowed m Source # stripCommonSuffix :: Shadowed m -> Shadowed m -> (Shadowed m, Shadowed m, Shadowed m) Source #
Eq a => RightGCDMonoid (Vector a) Source # | O(suffixLength)
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: Vector a -> Vector a -> Vector a Source # stripCommonSuffix :: Vector a -> Vector a -> (Vector a, Vector a, Vector a) Source #
RightGCDMonoid x => RightGCDMonoid (Maybe x) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: Maybe x -> Maybe x -> Maybe x Source # stripCommonSuffix :: Maybe x -> Maybe x -> (Maybe x, Maybe x, Maybe x) Source #
Eq x => RightGCDMonoid [x] Source # | O(m+n) Since: 1.0
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: [x] -> [x] -> [x] Source # stripCommonSuffix :: [x] -> [x] -> ([x], [x], [x]) Source #
(RightGCDMonoid a, RightGCDMonoid b) => RightGCDMonoid (Stateful a b) Source # |
Instance details Defined in Data.Monoid.Instances.Stateful Methods commonSuffix :: Stateful a b -> Stateful a b -> Stateful a b Source # stripCommonSuffix :: Stateful a b -> Stateful a b -> (Stateful a b, Stateful a b, Stateful a b) Source #
(RightGCDMonoid a, RightGCDMonoid b) => RightGCDMonoid (a, b) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: (a, b) -> (a, b) -> (a, b) Source # stripCommonSuffix :: (a, b) -> (a, b) -> ((a, b), (a, b), (a, b)) Source #
RightGCDMonoid a => RightGCDMonoid (Const a b) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: Const a b -> Const a b -> Const a b Source # stripCommonSuffix :: Const a b -> Const a b -> (Const a b, Const a b, Const a b) Source #
(RightGCDMonoid a, RightGCDMonoid b, RightGCDMonoid c) => RightGCDMonoid (a, b, c) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: (a, b, c) -> (a, b, c) -> (a, b, c) Source # stripCommonSuffix :: (a, b, c) -> (a, b, c) -> ((a, b, c), (a, b, c), (a, b, c)) Source #
(RightGCDMonoid a, RightGCDMonoid b, RightGCDMonoid c, RightGCDMonoid d) => RightGCDMonoid (a, b, c, d) Source # |
Instance details Defined in Data.Monoid.GCD Methods commonSuffix :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d) Source # stripCommonSuffix :: (a, b, c, d) -> (a, b, c, d) -> ((a, b, c, d), (a, b, c, d), (a, b, c, d)) Source #

class (Monoid m, LeftReductive m, RightReductive m) => OverlappingGCDMonoid m where Source #

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

Since: 1.0

Minimal complete definition

stripOverlap

Methods

stripPrefixOverlap :: m -> m -> m Source #

stripSuffixOverlap :: m -> m -> m Source #

overlap :: m -> m -> m Source #

stripOverlap :: m -> m -> (m, m, m) Source #

#### Instances

Instances details

OverlappingGCDMonoid ByteString Source # | O(min(m,n)^2)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: ByteString -> ByteString -> ByteString Source # stripSuffixOverlap :: ByteString -> ByteString -> ByteString Source # overlap :: ByteString -> ByteString -> ByteString Source # stripOverlap :: ByteString -> ByteString -> (ByteString, ByteString, ByteString) Source #
OverlappingGCDMonoid ByteString Source # | O(m*n)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: ByteString -> ByteString -> ByteString Source # stripSuffixOverlap :: ByteString -> ByteString -> ByteString Source # overlap :: ByteString -> ByteString -> ByteString Source # stripOverlap :: ByteString -> ByteString -> (ByteString, ByteString, ByteString) Source #
OverlappingGCDMonoid IntSet Source # | O(m+n)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: IntSet -> IntSet -> IntSet Source # stripSuffixOverlap :: IntSet -> IntSet -> IntSet Source # overlap :: IntSet -> IntSet -> IntSet Source # stripOverlap :: IntSet -> IntSet -> (IntSet, IntSet, IntSet) Source #
OverlappingGCDMonoid Text Source # | O(min(m,n)^2)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Text -> Text -> Text Source # stripSuffixOverlap :: Text -> Text -> Text Source # overlap :: Text -> Text -> Text Source # stripOverlap :: Text -> Text -> (Text, Text, Text) Source #
OverlappingGCDMonoid Text Source # | O(m*n)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Text -> Text -> Text Source # stripSuffixOverlap :: Text -> Text -> Text Source # overlap :: Text -> Text -> Text Source # stripOverlap :: Text -> Text -> (Text, Text, Text) Source #
OverlappingGCDMonoid () Source # | O(1)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: () -> () -> () Source # stripSuffixOverlap :: () -> () -> () Source # overlap :: () -> () -> () Source # stripOverlap :: () -> () -> ((), (), ()) Source #
Eq a => OverlappingGCDMonoid (IntMap a) Source # | O(m+n)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: IntMap a -> IntMap a -> IntMap a Source # stripSuffixOverlap :: IntMap a -> IntMap a -> IntMap a Source # overlap :: IntMap a -> IntMap a -> IntMap a Source # stripOverlap :: IntMap a -> IntMap a -> (IntMap a, IntMap a, IntMap a) Source #
Eq a => OverlappingGCDMonoid (Seq a) Source # | O(min(m,n)^2)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Seq a -> Seq a -> Seq a Source # stripSuffixOverlap :: Seq a -> Seq a -> Seq a Source # overlap :: Seq a -> Seq a -> Seq a Source # stripOverlap :: Seq a -> Seq a -> (Seq a, Seq a, Seq a) Source #
Ord a => OverlappingGCDMonoid (Set a) Source # | O(m*log(nm + 1)), m <= n/
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Set a -> Set a -> Set a Source # stripSuffixOverlap :: Set a -> Set a -> Set a Source # overlap :: Set a -> Set a -> Set a Source # stripOverlap :: Set a -> Set a -> (Set a, Set a, Set a) Source #
OverlappingGCDMonoid a => OverlappingGCDMonoid (Identity a) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Identity a -> Identity a -> Identity a Source # stripSuffixOverlap :: Identity a -> Identity a -> Identity a Source # overlap :: Identity a -> Identity a -> Identity a Source # stripOverlap :: Identity a -> Identity a -> (Identity a, Identity a, Identity a) Source #
OverlappingGCDMonoid a => OverlappingGCDMonoid (Dual a) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Dual a -> Dual a -> Dual a Source # stripSuffixOverlap :: Dual a -> Dual a -> Dual a Source # overlap :: Dual a -> Dual a -> Dual a Source # stripOverlap :: Dual a -> Dual a -> (Dual a, Dual a, Dual a) Source #
OverlappingGCDMonoid (Product Natural) Source # | O(1)

Instance details

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Product Natural -> Product Natural -> Product Natural Source #

stripSuffixOverlap :: Product Natural -> Product Natural -> Product Natural Source #

overlap :: Product Natural -> Product Natural -> Product Natural Source #

stripOverlap :: Product Natural -> Product Natural -> (Product Natural, Product Natural, Product Natural) Source #

OverlappingGCDMonoid (Sum Natural) Source # | O(1)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Sum Natural -> Sum Natural -> Sum Natural Source # stripSuffixOverlap :: Sum Natural -> Sum Natural -> Sum Natural Source # overlap :: Sum Natural -> Sum Natural -> Sum Natural Source # stripOverlap :: Sum Natural -> Sum Natural -> (Sum Natural, Sum Natural, Sum Natural) Source #
Eq a => OverlappingGCDMonoid (Vector a) Source # | O(min(m,n)^2)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Vector a -> Vector a -> Vector a Source # stripSuffixOverlap :: Vector a -> Vector a -> Vector a Source # overlap :: Vector a -> Vector a -> Vector a Source # stripOverlap :: Vector a -> Vector a -> (Vector a, Vector a, Vector a) Source #
(OverlappingGCDMonoid a, MonoidNull a) => OverlappingGCDMonoid (Maybe a) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Maybe a -> Maybe a -> Maybe a Source # stripSuffixOverlap :: Maybe a -> Maybe a -> Maybe a Source # overlap :: Maybe a -> Maybe a -> Maybe a Source # stripOverlap :: Maybe a -> Maybe a -> (Maybe a, Maybe a, Maybe a) Source #
Eq a => OverlappingGCDMonoid [a] Source # | O(m*n)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: [a] -> [a] -> [a] Source # stripSuffixOverlap :: [a] -> [a] -> [a] Source # overlap :: [a] -> [a] -> [a] Source # stripOverlap :: [a] -> [a] -> ([a], [a], [a]) Source #
(Ord k, Eq v) => OverlappingGCDMonoid (Map k v) Source # | O(m+n)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Map k v -> Map k v -> Map k v Source # stripSuffixOverlap :: Map k v -> Map k v -> Map k v Source # overlap :: Map k v -> Map k v -> Map k v Source # stripOverlap :: Map k v -> Map k v -> (Map k v, Map k v, Map k v) Source #
(OverlappingGCDMonoid a, OverlappingGCDMonoid b) => OverlappingGCDMonoid (a, b) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: (a, b) -> (a, b) -> (a, b) Source # stripSuffixOverlap :: (a, b) -> (a, b) -> (a, b) Source # overlap :: (a, b) -> (a, b) -> (a, b) Source # stripOverlap :: (a, b) -> (a, b) -> ((a, b), (a, b), (a, b)) Source #
OverlappingGCDMonoid a => OverlappingGCDMonoid (Const a b) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Const a b -> Const a b -> Const a b Source # stripSuffixOverlap :: Const a b -> Const a b -> Const a b Source # overlap :: Const a b -> Const a b -> Const a b Source # stripOverlap :: Const a b -> Const a b -> (Const a b, Const a b, Const a b) Source #
(OverlappingGCDMonoid a, OverlappingGCDMonoid b, OverlappingGCDMonoid c) => OverlappingGCDMonoid (a, b, c) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: (a, b, c) -> (a, b, c) -> (a, b, c) Source # stripSuffixOverlap :: (a, b, c) -> (a, b, c) -> (a, b, c) Source # overlap :: (a, b, c) -> (a, b, c) -> (a, b, c) Source # stripOverlap :: (a, b, c) -> (a, b, c) -> ((a, b, c), (a, b, c), (a, b, c)) Source #
(OverlappingGCDMonoid a, OverlappingGCDMonoid b, OverlappingGCDMonoid c, OverlappingGCDMonoid d) => OverlappingGCDMonoid (a, b, c, d) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d) Source # stripSuffixOverlap :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d) Source # overlap :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d) Source # stripOverlap :: (a, b, c, d) -> (a, b, c, d) -> ((a, b, c, d), (a, b, c, d), (a, b, c, d)) Source #

class (LeftDistributiveGCDMonoid m, RightDistributiveGCDMonoid m, GCDMonoid m) => DistributiveGCDMonoid m Source #

Class of commutative GCD monoids with symmetric distributivity.

In addition to the general `GCDMonoid` laws, instances of this class must also satisfy the following laws:

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

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

#### Instances

Instances details

DistributiveGCDMonoid IntSet Source # |
Instance details Defined in Data.Monoid.GCD
DistributiveGCDMonoid () Source # |
Instance details Defined in Data.Monoid.GCD
Ord a => DistributiveGCDMonoid (Set a) Source # |
Instance details Defined in Data.Monoid.GCD
DistributiveGCDMonoid a => DistributiveGCDMonoid (Identity a) Source # |
Instance details Defined in Data.Monoid.GCD
DistributiveGCDMonoid a => DistributiveGCDMonoid (Dual a) Source # |
Instance details Defined in Data.Monoid.GCD
DistributiveGCDMonoid (Product Natural) Source # |
Instance details Defined in Data.Monoid.GCD
DistributiveGCDMonoid (Sum Natural) Source # |
Instance details Defined in Data.Monoid.GCD
DistributiveGCDMonoid a => DistributiveGCDMonoid (Const a b) Source # |
Instance details Defined in Data.Monoid.GCD

class LeftGCDMonoid m => LeftDistributiveGCDMonoid m Source #

Class of left GCD monoids with left-distributivity.

In addition to the general `LeftGCDMonoid` laws, instances of this class must also satisfy the following law:

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

#### Instances

Instances details

LeftDistributiveGCDMonoid ByteString Source # |
Instance details Defined in Data.Monoid.GCD
LeftDistributiveGCDMonoid ByteString Source # |
Instance details Defined in Data.Monoid.GCD
LeftDistributiveGCDMonoid IntSet Source # |
Instance details Defined in Data.Monoid.GCD
LeftDistributiveGCDMonoid Text Source # |
Instance details Defined in Data.Monoid.GCD
LeftDistributiveGCDMonoid Text Source # |
Instance details Defined in Data.Monoid.GCD
LeftDistributiveGCDMonoid () Source # |
Instance details Defined in Data.Monoid.GCD
Eq a => LeftDistributiveGCDMonoid (Seq a) Source # |
Instance details Defined in Data.Monoid.GCD
Ord a => LeftDistributiveGCDMonoid (Set a) Source # |
Instance details Defined in Data.Monoid.GCD
LeftDistributiveGCDMonoid a => LeftDistributiveGCDMonoid (Identity a) Source # |
Instance details Defined in Data.Monoid.GCD
RightDistributiveGCDMonoid a => LeftDistributiveGCDMonoid (Dual a) Source # |
Instance details Defined in Data.Monoid.GCD
LeftDistributiveGCDMonoid (Product Natural) Source # |
Instance details Defined in Data.Monoid.GCD
LeftDistributiveGCDMonoid (Sum Natural) Source # |
Instance details Defined in Data.Monoid.GCD
Eq a => LeftDistributiveGCDMonoid (Vector a) Source # |
Instance details Defined in Data.Monoid.GCD
Eq a => LeftDistributiveGCDMonoid [a] Source # |
Instance details Defined in Data.Monoid.GCD
LeftDistributiveGCDMonoid a => LeftDistributiveGCDMonoid (Const a b) Source # |
Instance details Defined in Data.Monoid.GCD

class RightGCDMonoid m => RightDistributiveGCDMonoid m Source #

Class of right GCD monoids with right-distributivity.

In addition to the general `RightGCDMonoid` laws, instances of this class must also satisfy the following law:

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

#### Instances

Instances details

RightDistributiveGCDMonoid ByteString Source # |
Instance details Defined in Data.Monoid.GCD
RightDistributiveGCDMonoid ByteString Source # |
Instance details Defined in Data.Monoid.GCD
RightDistributiveGCDMonoid IntSet Source # |
Instance details Defined in Data.Monoid.GCD
RightDistributiveGCDMonoid Text Source # |
Instance details Defined in Data.Monoid.GCD
RightDistributiveGCDMonoid Text Source # |
Instance details Defined in Data.Monoid.GCD
RightDistributiveGCDMonoid () Source # |
Instance details Defined in Data.Monoid.GCD
Eq a => RightDistributiveGCDMonoid (Seq a) Source # |
Instance details Defined in Data.Monoid.GCD
Ord a => RightDistributiveGCDMonoid (Set a) Source # |
Instance details Defined in Data.Monoid.GCD
RightDistributiveGCDMonoid a => RightDistributiveGCDMonoid (Identity a) Source # |
Instance details Defined in Data.Monoid.GCD
LeftDistributiveGCDMonoid a => RightDistributiveGCDMonoid (Dual a) Source # |
Instance details Defined in Data.Monoid.GCD
RightDistributiveGCDMonoid (Product Natural) Source # |
Instance details Defined in Data.Monoid.GCD
RightDistributiveGCDMonoid (Sum Natural) Source # |
Instance details Defined in Data.Monoid.GCD
Eq a => RightDistributiveGCDMonoid (Vector a) Source # |
Instance details Defined in Data.Monoid.GCD
Eq a => RightDistributiveGCDMonoid [a] Source # |
Instance details Defined in Data.Monoid.GCD
RightDistributiveGCDMonoid a => RightDistributiveGCDMonoid (Const a b) Source # |
Instance details Defined in Data.Monoid.GCD