Data.Monoid.GCD

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.

Documentation

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

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

Instances

GCDMonoid IntSet

O(m+n)

Defined in Data.Monoid.GCD

Methods

gcd :: IntSet -> IntSet -> IntSet

GCDMonoid ()

O(1)

Defined in Data.Monoid.GCD

Methods

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

GCDMonoid a => GCDMonoid (Dual a)

Defined in Data.Monoid.GCD

Methods

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

GCDMonoid (Product Natural)

O(1)

Defined in Data.Monoid.GCD

Methods

gcd :: Product Natural -> Product Natural -> Product Natural

GCDMonoid (Sum Natural)

O(1)

Defined in Data.Monoid.GCD

Methods

gcd :: Sum Natural -> Sum Natural -> Sum Natural

Ord a => GCDMonoid (Set a)

O(m*log(n/m + 1)), m <= n

Defined in Data.Monoid.GCD

Methods

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

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

Defined in Data.Monoid.GCD

Methods

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

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

Defined in Data.Monoid.GCD

Methods

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

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

Defined in Data.Monoid.GCD

Methods

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

class (Monoid m, LeftReductive 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 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

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

Instances

LeftGCDMonoid ByteString

O(prefixLength)

Defined in Data.Monoid.GCD

Methods

commonPrefix :: ByteString -> ByteString -> ByteString

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

LeftGCDMonoid ByteString

O(prefixLength)

Defined in Data.Monoid.GCD

Methods

commonPrefix :: ByteString -> ByteString -> ByteString

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

LeftGCDMonoid IntSet

O(m+n)

Defined in Data.Monoid.GCD

Methods

commonPrefix :: IntSet -> IntSet -> IntSet

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

LeftGCDMonoid ByteStringUTF8

O(prefixLength)

Defined in Data.Monoid.Instances.ByteString.UTF8

Methods

commonPrefix :: ByteStringUTF8 -> ByteStringUTF8 -> ByteStringUTF8

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

LeftGCDMonoid Text

O(prefixLength)

Defined in Data.Monoid.GCD

Methods

commonPrefix :: Text -> Text -> Text

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

LeftGCDMonoid Text

O(prefixLength)

Defined in Data.Monoid.GCD

Methods

commonPrefix :: Text -> Text -> Text

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

LeftGCDMonoid ()

O(1)

Defined in Data.Monoid.GCD

Methods

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

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

RightGCDMonoid a => LeftGCDMonoid (Dual a)

Defined in Data.Monoid.GCD

Methods

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

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

LeftGCDMonoid (Product Natural)

O(1)

Defined in Data.Monoid.GCD

Methods

commonPrefix :: Product Natural -> Product Natural -> Product Natural

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

LeftGCDMonoid (Sum Natural)

O(1)

Defined in Data.Monoid.GCD

Methods

commonPrefix :: Sum Natural -> Sum Natural -> Sum Natural

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

Eq a => LeftGCDMonoid (IntMap a)

O(m+n)

Defined in Data.Monoid.GCD

Methods

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

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

Eq a => LeftGCDMonoid (Seq a)

O(prefixLength)

Defined in Data.Monoid.GCD

Methods

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

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

Ord a => LeftGCDMonoid (Set a)

O(m*log(n/m + 1)), m <= n

Defined in Data.Monoid.GCD

Methods

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

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

(LeftGCDMonoid a, StableFactorial a, PositiveMonoid a) => LeftGCDMonoid (Concat a)

Defined in Data.Monoid.Instances.Concat

Methods

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

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

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

Defined in Data.Monoid.Instances.Measured

Methods

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

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

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

Defined in Data.Monoid.Instances.Positioned

Methods

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

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

(StableFactorial m, FactorialMonoid m, LeftGCDMonoid m) => LeftGCDMonoid (OffsetPositioned m)

Defined in Data.Monoid.Instances.Positioned

Methods

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

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

(Eq m, StableFactorial m, FactorialMonoid m, LeftGCDMonoid m) => LeftGCDMonoid (Shadowed m)

Defined in Data.Monoid.Instances.PrefixMemory

Methods

commonPrefix :: Shadowed m -> Shadowed m -> Shadowed m

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

Eq a => LeftGCDMonoid (Vector a)

O(prefixLength)

Defined in Data.Monoid.GCD

Methods

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

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

LeftGCDMonoid x => LeftGCDMonoid (Maybe x)

Defined in Data.Monoid.GCD

Methods

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

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

Eq x => LeftGCDMonoid [x]

O(prefixLength)

Defined in Data.Monoid.GCD

Methods

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

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

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

O(m+n)

Defined in Data.Monoid.GCD

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)

Defined in Data.Monoid.Instances.Stateful

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 (a, b)

Defined in Data.Monoid.GCD

Methods

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

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

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

Defined in Data.Monoid.GCD

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)

Defined in Data.Monoid.GCD

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 (Monoid m, RightReductive 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 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

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

Instances

RightGCDMonoid ByteString

O(suffixLength)

Defined in Data.Monoid.GCD

Methods

commonSuffix :: ByteString -> ByteString -> ByteString

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

RightGCDMonoid ByteString

O(suffixLength)

Defined in Data.Monoid.GCD

Methods

commonSuffix :: ByteString -> ByteString -> ByteString

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

RightGCDMonoid IntSet

O(m+n)

Defined in Data.Monoid.GCD

Methods

commonSuffix :: IntSet -> IntSet -> IntSet

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

RightGCDMonoid Text

O(suffixLength), except on GHCjs where it is O(m+n)

Since: 1.0

Defined in Data.Monoid.GCD

Methods

commonSuffix :: Text -> Text -> Text

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

RightGCDMonoid Text

O(m+n)

Since: 1.0

Defined in Data.Monoid.GCD

Methods

commonSuffix :: Text -> Text -> Text

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

RightGCDMonoid ()

O(1)

Defined in Data.Monoid.GCD

Methods

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

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

LeftGCDMonoid a => RightGCDMonoid (Dual a)

Defined in Data.Monoid.GCD

Methods

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

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

RightGCDMonoid (Product Natural)

O(1)

Defined in Data.Monoid.GCD

Methods

commonSuffix :: Product Natural -> Product Natural -> Product Natural

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

RightGCDMonoid (Sum Natural)

O(1)

Defined in Data.Monoid.GCD

Methods

commonSuffix :: Sum Natural -> Sum Natural -> Sum Natural

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

Eq a => RightGCDMonoid (Seq a)

O(suffixLength)

Defined in Data.Monoid.GCD

Methods

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

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

Ord a => RightGCDMonoid (Set a)

O(m*log(n/m + 1)), m <= n

Defined in Data.Monoid.GCD

Methods

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

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

(RightGCDMonoid a, StableFactorial a, PositiveMonoid a) => RightGCDMonoid (Concat a)

Defined in Data.Monoid.Instances.Concat

Methods

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

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

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

Defined in Data.Monoid.Instances.Measured

Methods

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

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

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

Defined in Data.Monoid.Instances.Positioned

Methods

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

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

(StableFactorial m, FactorialMonoid m, RightGCDMonoid m) => RightGCDMonoid (OffsetPositioned m)

Defined in Data.Monoid.Instances.Positioned

Methods

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

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

(StableFactorial m, FactorialMonoid m, RightGCDMonoid m) => RightGCDMonoid (Shadowed m)

Defined in Data.Monoid.Instances.PrefixMemory

Methods

commonSuffix :: Shadowed m -> Shadowed m -> Shadowed m

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

Eq a => RightGCDMonoid (Vector a)

O(suffixLength)

Defined in Data.Monoid.GCD

Methods

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

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

RightGCDMonoid x => RightGCDMonoid (Maybe x)

Defined in Data.Monoid.GCD

Methods

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

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

Eq x => RightGCDMonoid [x]

O(m+n)

Since: 1.0

Defined in Data.Monoid.GCD

Methods

commonSuffix :: [x] -> [x] -> [x]

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

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

Defined in Data.Monoid.Instances.Stateful

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 (a, b)

Defined in Data.Monoid.GCD

Methods

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

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

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

Defined in Data.Monoid.GCD

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)

Defined in Data.Monoid.GCD

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))

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

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

stripSuffixOverlap :: m -> m -> m

overlap :: m -> m -> m

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

Instances

OverlappingGCDMonoid ByteString

O(min(m,n)^2)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: ByteString -> ByteString -> ByteString

stripSuffixOverlap :: ByteString -> ByteString -> ByteString

overlap :: ByteString -> ByteString -> ByteString

stripOverlap :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)

OverlappingGCDMonoid ByteString

O(m*n)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: ByteString -> ByteString -> ByteString

stripSuffixOverlap :: ByteString -> ByteString -> ByteString

overlap :: ByteString -> ByteString -> ByteString

stripOverlap :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)

OverlappingGCDMonoid IntSet

O(m+n)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: IntSet -> IntSet -> IntSet

stripSuffixOverlap :: IntSet -> IntSet -> IntSet

overlap :: IntSet -> IntSet -> IntSet

stripOverlap :: IntSet -> IntSet -> (IntSet, IntSet, IntSet)

OverlappingGCDMonoid Text

O(min(m,n)^2)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Text -> Text -> Text

stripSuffixOverlap :: Text -> Text -> Text

overlap :: Text -> Text -> Text

stripOverlap :: Text -> Text -> (Text, Text, Text)

OverlappingGCDMonoid Text

O(m*n)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Text -> Text -> Text

stripSuffixOverlap :: Text -> Text -> Text

overlap :: Text -> Text -> Text

stripOverlap :: Text -> Text -> (Text, Text, Text)

OverlappingGCDMonoid ()

O(1)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: () -> () -> ()

stripSuffixOverlap :: () -> () -> ()

overlap :: () -> () -> ()

stripOverlap :: () -> () -> ((), (), ())

OverlappingGCDMonoid a => OverlappingGCDMonoid (Dual a)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Dual a -> Dual a -> Dual a

stripSuffixOverlap :: Dual a -> Dual a -> Dual a

overlap :: Dual a -> Dual a -> Dual a

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

OverlappingGCDMonoid (Product Natural)

O(1)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Product Natural -> Product Natural -> Product Natural

stripSuffixOverlap :: Product Natural -> Product Natural -> Product Natural

overlap :: Product Natural -> Product Natural -> Product Natural

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

OverlappingGCDMonoid (Sum Natural)

O(1)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Sum Natural -> Sum Natural -> Sum Natural

stripSuffixOverlap :: Sum Natural -> Sum Natural -> Sum Natural

overlap :: Sum Natural -> Sum Natural -> Sum Natural

stripOverlap :: Sum Natural -> Sum Natural -> (Sum Natural, Sum Natural, Sum Natural)

Eq a => OverlappingGCDMonoid (IntMap a)

O(m+n)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: IntMap a -> IntMap a -> IntMap a

stripSuffixOverlap :: IntMap a -> IntMap a -> IntMap a

overlap :: IntMap a -> IntMap a -> IntMap a

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

Eq a => OverlappingGCDMonoid (Seq a)

O(min(m,n)^2)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Seq a -> Seq a -> Seq a

stripSuffixOverlap :: Seq a -> Seq a -> Seq a

overlap :: Seq a -> Seq a -> Seq a

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

Ord a => OverlappingGCDMonoid (Set a)

O(m*log(nm + 1)), m <= n/

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Set a -> Set a -> Set a

stripSuffixOverlap :: Set a -> Set a -> Set a

overlap :: Set a -> Set a -> Set a

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

Eq a => OverlappingGCDMonoid (Vector a)

O(min(m,n)^2)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Vector a -> Vector a -> Vector a

stripSuffixOverlap :: Vector a -> Vector a -> Vector a

overlap :: Vector a -> Vector a -> Vector a

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

(OverlappingGCDMonoid a, MonoidNull a) => OverlappingGCDMonoid (Maybe a)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Maybe a -> Maybe a -> Maybe a

stripSuffixOverlap :: Maybe a -> Maybe a -> Maybe a

overlap :: Maybe a -> Maybe a -> Maybe a

stripOverlap :: Maybe a -> Maybe a -> (Maybe a, Maybe a, Maybe a)

Eq a => OverlappingGCDMonoid [a]

O(m*n)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: [a] -> [a] -> [a]

stripSuffixOverlap :: [a] -> [a] -> [a]

overlap :: [a] -> [a] -> [a]

stripOverlap :: [a] -> [a] -> ([a], [a], [a])

(Ord k, Eq v) => OverlappingGCDMonoid (Map k v)

O(m+n)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Map k v -> Map k v -> Map k v

stripSuffixOverlap :: Map k v -> Map k v -> Map k v

overlap :: Map k v -> Map k v -> Map k v

stripOverlap :: Map k v -> Map k v -> (Map k v, Map k v, Map k v)

(OverlappingGCDMonoid a, OverlappingGCDMonoid b) => OverlappingGCDMonoid (a, b)

Defined in Data.Monoid.Monus

Methods

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

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

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

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

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

Defined in Data.Monoid.Monus

Methods

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

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

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

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

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

Defined in Data.Monoid.Monus

Methods

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

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

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

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

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

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

DistributiveGCDMonoid IntSet

Defined in Data.Monoid.GCD

DistributiveGCDMonoid ()

Defined in Data.Monoid.GCD

DistributiveGCDMonoid a => DistributiveGCDMonoid (Dual a)

Defined in Data.Monoid.GCD

DistributiveGCDMonoid (Product Natural)

Defined in Data.Monoid.GCD

DistributiveGCDMonoid (Sum Natural)

Defined in Data.Monoid.GCD

Ord a => DistributiveGCDMonoid (Set a)

Defined in Data.Monoid.GCD

class LeftGCDMonoid m => LeftDistributiveGCDMonoid m

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

LeftDistributiveGCDMonoid ByteString

Defined in Data.Monoid.GCD

LeftDistributiveGCDMonoid ByteString

Defined in Data.Monoid.GCD

LeftDistributiveGCDMonoid IntSet

Defined in Data.Monoid.GCD

LeftDistributiveGCDMonoid Text

Defined in Data.Monoid.GCD

LeftDistributiveGCDMonoid Text

Defined in Data.Monoid.GCD

LeftDistributiveGCDMonoid ()

Defined in Data.Monoid.GCD

RightDistributiveGCDMonoid a => LeftDistributiveGCDMonoid (Dual a)

Defined in Data.Monoid.GCD

LeftDistributiveGCDMonoid (Product Natural)

Defined in Data.Monoid.GCD

LeftDistributiveGCDMonoid (Sum Natural)

Defined in Data.Monoid.GCD

Eq a => LeftDistributiveGCDMonoid (Seq a)

Defined in Data.Monoid.GCD

Ord a => LeftDistributiveGCDMonoid (Set a)

Defined in Data.Monoid.GCD

Eq a => LeftDistributiveGCDMonoid (Vector a)

Defined in Data.Monoid.GCD

Eq a => LeftDistributiveGCDMonoid [a]

Defined in Data.Monoid.GCD

class RightGCDMonoid m => RightDistributiveGCDMonoid m

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

RightDistributiveGCDMonoid ByteString

Defined in Data.Monoid.GCD

RightDistributiveGCDMonoid ByteString

Defined in Data.Monoid.GCD

RightDistributiveGCDMonoid IntSet

Defined in Data.Monoid.GCD

RightDistributiveGCDMonoid Text

Defined in Data.Monoid.GCD

RightDistributiveGCDMonoid Text

Defined in Data.Monoid.GCD

RightDistributiveGCDMonoid ()

Defined in Data.Monoid.GCD

LeftDistributiveGCDMonoid a => RightDistributiveGCDMonoid (Dual a)

Defined in Data.Monoid.GCD

RightDistributiveGCDMonoid (Product Natural)

Defined in Data.Monoid.GCD

RightDistributiveGCDMonoid (Sum Natural)

Defined in Data.Monoid.GCD

Eq a => RightDistributiveGCDMonoid (Seq a)

Defined in Data.Monoid.GCD

Ord a => RightDistributiveGCDMonoid (Set a)

Defined in Data.Monoid.GCD

Eq a => RightDistributiveGCDMonoid (Vector a)

Defined in Data.Monoid.GCD

Eq a => RightDistributiveGCDMonoid [a]

Defined in Data.Monoid.GCD