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:
Class of monoids for which it is possible to find the greatest common prefix of two monoidal values.
Class of monoids for which it is possible to find the greatest common suffix of two monoidal values.
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:
Subclass of
GCDMonoid
with symmetric distributivity.Subclass of
LeftGCDMonoid
with left-distributivity.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
amempty
==
mempty
Commutativity
gcd
a b==
gcd
b a
Associativity
gcd
(gcd
a b) c==
gcd
a (gcd
b c)
Instances
GCDMonoid IntSet Source # | O(m+n) |
Defined in Data.Monoid.GCD | |
GCDMonoid () Source # | O(1) |
Defined in Data.Monoid.GCD | |
Ord a => GCDMonoid (Set a) Source # | O(m*log(n/m + 1)), m <= n |
Defined in Data.Monoid.GCD | |
GCDMonoid a => GCDMonoid (Identity a) Source # | |
Defined in Data.Monoid.GCD | |
GCDMonoid a => GCDMonoid (Dual a) Source # | |
Defined in Data.Monoid.GCD | |
GCDMonoid (Product Natural) Source # | O(1) |
Defined in Data.Monoid.GCD | |
GCDMonoid (Sum Natural) Source # | O(1) |
Defined in Data.Monoid.GCD | |
(GCDMonoid a, GCDMonoid b) => GCDMonoid (a, b) Source # | |
Defined in Data.Monoid.GCD | |
GCDMonoid a => GCDMonoid (Const a b) Source # | |
Defined in Data.Monoid.GCD | |
(GCDMonoid a, GCDMonoid b, GCDMonoid c) => GCDMonoid (a, b, c) Source # | |
Defined in Data.Monoid.GCD | |
(GCDMonoid a, GCDMonoid b, GCDMonoid c, GCDMonoid d) => GCDMonoid (a, b, c, d) Source # | |
Defined in Data.Monoid.GCD |
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
amempty
==
mempty
Commutativity
commonPrefix
a b==
commonPrefix
b a
Associativity
commonPrefix
(commonPrefix
a b) c==
commonPrefix
a (commonPrefix
b c)
Minimal complete definition
Instances
LeftGCDMonoid ByteString Source # | O(prefixLength) |
Defined in Data.Monoid.GCD Methods commonPrefix :: ByteString -> ByteString -> ByteString Source # stripCommonPrefix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString) Source # | |
LeftGCDMonoid ByteString Source # | O(prefixLength) |
Defined in Data.Monoid.GCD Methods commonPrefix :: ByteString -> ByteString -> ByteString Source # stripCommonPrefix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString) Source # | |
LeftGCDMonoid IntSet Source # | O(m+n) |
Defined in Data.Monoid.GCD Methods commonPrefix :: IntSet -> IntSet -> IntSet Source # stripCommonPrefix :: IntSet -> IntSet -> (IntSet, IntSet, IntSet) Source # | |
LeftGCDMonoid ByteStringUTF8 Source # | O(prefixLength) |
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) |
Defined in Data.Monoid.GCD Methods commonPrefix :: Text -> Text -> Text Source # stripCommonPrefix :: Text -> Text -> (Text, Text, Text) Source # | |
LeftGCDMonoid Text Source # | O(prefixLength) |
Defined in Data.Monoid.GCD Methods commonPrefix :: Text -> Text -> Text Source # stripCommonPrefix :: Text -> Text -> (Text, Text, Text) Source # | |
LeftGCDMonoid () Source # | O(1) |
Defined in Data.Monoid.GCD Methods commonPrefix :: () -> () -> () Source # stripCommonPrefix :: () -> () -> ((), (), ()) Source # | |
Eq a => LeftGCDMonoid (IntMap a) Source # | O(m+n) |
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) |
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 |
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 # | |
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 # | |
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) |
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) |
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 # | |
Defined in Data.Monoid.Instances.Concat | |
(LeftGCDMonoid a, StableFactorial a) => LeftGCDMonoid (Measured a) Source # | |
Defined in Data.Monoid.Instances.Measured | |
(StableFactorial m, TextualMonoid m, LeftGCDMonoid m) => LeftGCDMonoid (LinePositioned m) Source # | |
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 # | |
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 # | |
Defined in Data.Monoid.Instances.PrefixMemory | |
Eq a => LeftGCDMonoid (Vector a) Source # | O(prefixLength) |
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 # | |
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) |
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) |
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 # | |
Defined in Data.Monoid.Instances.Stateful | |
(LeftGCDMonoid a, LeftGCDMonoid b) => LeftGCDMonoid (a, b) Source # | |
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 # | |
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 # | |
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 # | |
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
amempty
==
mempty
Commutativity
commonSuffix
a b==
commonSuffix
b a
Associativity
commonSuffix
(commonSuffix
a b) c==
commonSuffix
a (commonSuffix
b c)
Minimal complete definition
Instances
RightGCDMonoid ByteString Source # | O(suffixLength) |
Defined in Data.Monoid.GCD Methods commonSuffix :: ByteString -> ByteString -> ByteString Source # stripCommonSuffix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString) Source # | |
RightGCDMonoid ByteString Source # | O(suffixLength) |
Defined in Data.Monoid.GCD Methods commonSuffix :: ByteString -> ByteString -> ByteString Source # stripCommonSuffix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString) Source # | |
RightGCDMonoid IntSet Source # | O(m+n) |
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 |
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 |
Defined in Data.Monoid.GCD Methods commonSuffix :: Text -> Text -> Text Source # stripCommonSuffix :: Text -> Text -> (Text, Text, Text) Source # | |
RightGCDMonoid () Source # | O(1) |
Defined in Data.Monoid.GCD Methods commonSuffix :: () -> () -> () Source # stripCommonSuffix :: () -> () -> ((), (), ()) Source # | |
Eq a => RightGCDMonoid (Seq a) Source # | O(suffixLength) |
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 |
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 # | |
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 # | |
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) |
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) |
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 # | |
Defined in Data.Monoid.Instances.Concat | |
(RightGCDMonoid a, StableFactorial a) => RightGCDMonoid (Measured a) Source # | |
Defined in Data.Monoid.Instances.Measured | |
(StableFactorial m, TextualMonoid m, RightGCDMonoid m) => RightGCDMonoid (LinePositioned m) Source # | |
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 # | |
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 # | |
Defined in Data.Monoid.Instances.PrefixMemory | |
Eq a => RightGCDMonoid (Vector a) Source # | O(suffixLength) |
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 # | |
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 |
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 # | |
Defined in Data.Monoid.Instances.Stateful | |
(RightGCDMonoid a, RightGCDMonoid b) => RightGCDMonoid (a, b) Source # | |
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 # | |
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 # | |
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 # | |
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
amempty
==
mempty
Since: 1.0
Minimal complete definition
Methods
stripPrefixOverlap :: m -> m -> m Source #
stripSuffixOverlap :: m -> m -> m Source #
overlap :: m -> m -> m Source #
stripOverlap :: m -> m -> (m, m, m) Source #
Instances
OverlappingGCDMonoid ByteString Source # | O(min(m,n)^2) |
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) |
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) |
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) |
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) |
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) |
Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: () -> () -> () Source # stripSuffixOverlap :: () -> () -> () Source # overlap :: () -> () -> () Source # stripOverlap :: () -> () -> ((), (), ()) Source # | |
Eq a => OverlappingGCDMonoid (IntMap a) Source # | O(m+n) |
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) |
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/ |
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 # | |
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 # | |
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) |
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) |
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) |
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 # | |
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) |
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) |
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 # | |
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 # | |
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 # | |
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 # | |
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
DistributiveGCDMonoid IntSet Source # | |
Defined in Data.Monoid.GCD | |
DistributiveGCDMonoid () Source # | |
Defined in Data.Monoid.GCD | |
Ord a => DistributiveGCDMonoid (Set a) Source # | |
Defined in Data.Monoid.GCD | |
DistributiveGCDMonoid a => DistributiveGCDMonoid (Identity a) Source # | |
Defined in Data.Monoid.GCD | |
DistributiveGCDMonoid a => DistributiveGCDMonoid (Dual a) Source # | |
Defined in Data.Monoid.GCD | |
DistributiveGCDMonoid (Product Natural) Source # | |
Defined in Data.Monoid.GCD | |
DistributiveGCDMonoid (Sum Natural) Source # | |
Defined in Data.Monoid.GCD | |
DistributiveGCDMonoid a => DistributiveGCDMonoid (Const a b) Source # | |
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
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