Safe Haskell | Trustworthy |
---|---|
Language | Haskell2010 |
This module defines the Monoid
=> ReductiveMonoid
=> (CancellativeMonoid
, GCDMonoid
) class hierarchy.
The ReductiveMonoid
class introduces operation </>
which is the inverse of <>
. For the Sum
monoid, this
operation is subtraction; for Product
it is division and for Set
it's the set difference. A ReductiveMonoid
is
not a full group because </>
may return Nothing
.
The CancellativeMonoid
subclass does not add any operation but it provides the additional guarantee that <>
can
always be undone with </>
. Thus Sum
is a CancellativeMonoid
but Product
is not because (0*n)/0
is not
defined.
The GCDMonoid
subclass adds the gcd
operation which takes two monoidal arguments and finds their greatest common
divisor, or (more generally) the greatest monoid that can be extracted with the </>
operation from both.
All monoid subclasses listed above are for Abelian, i.e., commutative or symmetric monoids. Since most practical monoids in Haskell are not Abelian, each of the these classes has two symmetric superclasses:
Synopsis
- class Monoid m => CommutativeMonoid m
- class (CommutativeMonoid m, LeftReductiveMonoid m, RightReductiveMonoid m) => ReductiveMonoid m where
- class (LeftCancellativeMonoid m, RightCancellativeMonoid m, ReductiveMonoid m) => CancellativeMonoid m
- class (ReductiveMonoid m, LeftGCDMonoid m, RightGCDMonoid m) => GCDMonoid m where
- class Monoid m => LeftReductiveMonoid m where
- class Monoid m => RightReductiveMonoid m where
- class LeftReductiveMonoid m => LeftCancellativeMonoid m
- class RightReductiveMonoid m => RightCancellativeMonoid m
- class LeftReductiveMonoid m => LeftGCDMonoid m where
- class RightReductiveMonoid m => RightGCDMonoid m where
Symmetric, commutative monoid classes
class Monoid m => CommutativeMonoid m Source #
Class of all Abelian ({i.e.}, commutative) monoids that satisfy the commutativity property:
a <> b == b <> a
Instances
CommutativeMonoid () Source # | |
Defined in Data.Monoid.Cancellative | |
CommutativeMonoid IntSet Source # | |
Defined in Data.Monoid.Cancellative | |
CommutativeMonoid a => CommutativeMonoid (Dual a) Source # | |
Defined in Data.Monoid.Cancellative | |
Num a => CommutativeMonoid (Sum a) Source # | |
Defined in Data.Monoid.Cancellative | |
Num a => CommutativeMonoid (Product a) Source # | |
Defined in Data.Monoid.Cancellative | |
Ord a => CommutativeMonoid (Set a) Source # | |
Defined in Data.Monoid.Cancellative | |
(CommutativeMonoid a, CommutativeMonoid b) => CommutativeMonoid (a, b) Source # | |
Defined in Data.Monoid.Cancellative | |
(CommutativeMonoid a, CommutativeMonoid b, CommutativeMonoid c) => CommutativeMonoid (a, b, c) Source # | |
Defined in Data.Monoid.Cancellative | |
(CommutativeMonoid a, CommutativeMonoid b, CommutativeMonoid c, CommutativeMonoid d) => CommutativeMonoid (a, b, c, d) Source # | |
Defined in Data.Monoid.Cancellative |
class (CommutativeMonoid m, LeftReductiveMonoid m, RightReductiveMonoid m) => ReductiveMonoid m where Source #
Class of Abelian monoids with a partial inverse for the Monoid <>
operation. The inverse operation </>
must
satisfy the following laws:
maybe a (b <>) (a </> b) == a maybe a (<> b) (a </> b) == a
Instances
ReductiveMonoid () Source # | |
Defined in Data.Monoid.Cancellative | |
ReductiveMonoid IntSet Source # | |
ReductiveMonoid a => ReductiveMonoid (Dual a) Source # | |
Integral a => ReductiveMonoid (Sum a) Source # | |
Integral a => ReductiveMonoid (Product a) Source # | |
Ord a => ReductiveMonoid (Set a) Source # | |
(ReductiveMonoid a, ReductiveMonoid b) => ReductiveMonoid (a, b) Source # | |
Defined in Data.Monoid.Cancellative | |
(ReductiveMonoid a, ReductiveMonoid b, ReductiveMonoid c) => ReductiveMonoid (a, b, c) Source # | |
Defined in Data.Monoid.Cancellative | |
(ReductiveMonoid a, ReductiveMonoid b, ReductiveMonoid c, ReductiveMonoid d) => ReductiveMonoid (a, b, c, d) Source # | |
Defined in Data.Monoid.Cancellative |
class (LeftCancellativeMonoid m, RightCancellativeMonoid m, ReductiveMonoid m) => CancellativeMonoid m Source #
Subclass of ReductiveMonoid
where </>
is a complete inverse of the Monoid <>
operation. The class instances
must satisfy the following additional laws:
(a <> b) </> a == Just b (a <> b) </> b == Just a
Instances
CancellativeMonoid () Source # | |
Defined in Data.Monoid.Cancellative | |
CancellativeMonoid a => CancellativeMonoid (Dual a) Source # | |
Defined in Data.Monoid.Cancellative | |
Integral a => CancellativeMonoid (Sum a) Source # | |
Defined in Data.Monoid.Cancellative | |
(CancellativeMonoid a, CancellativeMonoid b) => CancellativeMonoid (a, b) Source # | |
Defined in Data.Monoid.Cancellative | |
(CancellativeMonoid a, CancellativeMonoid b, CancellativeMonoid c) => CancellativeMonoid (a, b, c) Source # | |
Defined in Data.Monoid.Cancellative | |
(CancellativeMonoid a, CancellativeMonoid b, CancellativeMonoid c, CancellativeMonoid d) => CancellativeMonoid (a, b, c, d) Source # | |
Defined in Data.Monoid.Cancellative |
class (ReductiveMonoid m, LeftGCDMonoid m, RightGCDMonoid m) => GCDMonoid m where Source #
Class of Abelian monoids that allow the greatest common denominator to be found for any two given values. The operations must satisfy the following laws:
gcd a b == commonPrefix a b == commonSuffix a b Just a' = a </> p && Just b' = b </> p where p = gcd a b
If a GCDMonoid
happens to also be a CancellativeMonoid
, it should additionally satisfy the following laws:
gcd (a <> b) (a <> c) == a <> gcd b c gcd (a <> c) (b <> c) == gcd a b <> c
Instances
GCDMonoid () Source # | |
Defined in Data.Monoid.Cancellative | |
GCDMonoid IntSet Source # | |
GCDMonoid a => GCDMonoid (Dual a) Source # | |
(Integral a, Ord a) => GCDMonoid (Sum a) Source # | |
Integral a => GCDMonoid (Product a) Source # | |
Ord a => GCDMonoid (Set a) Source # | |
(GCDMonoid a, GCDMonoid b) => GCDMonoid (a, b) Source # | |
Defined in Data.Monoid.Cancellative | |
(GCDMonoid a, GCDMonoid b, GCDMonoid c) => GCDMonoid (a, b, c) Source # | |
Defined in Data.Monoid.Cancellative | |
(GCDMonoid a, GCDMonoid b, GCDMonoid c, GCDMonoid d) => GCDMonoid (a, b, c, d) Source # | |
Defined in Data.Monoid.Cancellative |
Asymmetric monoid classes
class Monoid m => LeftReductiveMonoid m where Source #
Class of monoids with a left inverse of mappend
, satisfying the following law:
isPrefixOf a b == isJust (stripPrefix a b) maybe b (a <>) (stripPrefix a b) == b a `isPrefixOf` (a <> b)
| Every instance definition has to implement at least the stripPrefix
method. Its complexity should be no worse
than linear in the length of the prefix argument.
isPrefixOf :: m -> m -> Bool Source #
stripPrefix :: m -> m -> Maybe m Source #
Instances
class Monoid m => RightReductiveMonoid m where Source #
Class of monoids with a right inverse of mappend
, satisfying the following law:
isSuffixOf a b == isJust (stripSuffix a b) maybe b (<> a) (stripSuffix a b) == b b `isSuffixOf` (a <> b)
| Every instance definition has to implement at least the stripSuffix
method. Its complexity should be no worse
than linear in the length of the suffix argument.
isSuffixOf :: m -> m -> Bool Source #
stripSuffix :: m -> m -> Maybe m Source #
Instances
class LeftReductiveMonoid m => LeftCancellativeMonoid m Source #
Subclass of LeftReductiveMonoid
where stripPrefix
is a complete inverse of <>
, satisfying the following
additional law:
stripPrefix a (a <> b) == Just b
Instances
class RightReductiveMonoid m => RightCancellativeMonoid m Source #
Subclass of LeftReductiveMonoid
where stripPrefix
is a complete inverse of <>
, satisfying the following
additional law:
stripSuffix b (a <> b) == Just a
Instances
class LeftReductiveMonoid 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 methods' complexity should be no worse than linear in the length of the common prefix. The following laws must be respected:
stripCommonPrefix a b == (p, a', b') where p = commonPrefix a b Just a' = stripPrefix p a Just b' = stripPrefix p b p == commonPrefix a b && p <> a' == a && p <> b' == b where (p, a', b') = stripCommonPrefix a b
commonPrefix :: m -> m -> m Source #
stripCommonPrefix :: m -> m -> (m, m, m) Source #
Instances
class RightReductiveMonoid 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 methods' complexity must be no worse than linear in the length of the common suffix. The following laws must be respected:
stripCommonSuffix a b == (a', b', s) where s = commonSuffix a b Just a' = stripSuffix p a Just b' = stripSuffix p b s == commonSuffix a b && a' <> s == a && b' <> s == b where (a', b', s) = stripCommonSuffix a b
commonSuffix :: m -> m -> m Source #
stripCommonSuffix :: m -> m -> (m, m, m) Source #