monoid-subclasses-0.4.2.1: Subclasses of Monoid

Data.Monoid.Cancellative

Description

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

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

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

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

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

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

Synopsis

# 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

 Source Source Source Num a => CommutativeMonoid (Sum a) Source Num a => CommutativeMonoid (Product a) Source Ord a => CommutativeMonoid (Set a) Source (CommutativeMonoid a, CommutativeMonoid b) => CommutativeMonoid (a, b) Source

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

Methods

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

Instances

 Source Source Source Integral a => ReductiveMonoid (Sum a) Source Source Ord a => ReductiveMonoid (Set a) Source (ReductiveMonoid a, ReductiveMonoid b) => ReductiveMonoid (a, b) 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

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

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

Methods

gcd :: m -> m -> m Source

Instances

 Source 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

# 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.

Minimal complete definition

stripPrefix

Methods

isPrefixOf :: m -> m -> Bool Source

stripPrefix :: m -> m -> Maybe m Source

Instances

 Source Source Source Source Source Source Source Eq x => LeftReductiveMonoid [x] Source Source Source Source Source Source Ord a => LeftReductiveMonoid (Set a) Source Eq a => LeftReductiveMonoid (Seq a) Source Eq a => LeftReductiveMonoid (Vector a) Source Source Source Source Source Source Ord k => LeftReductiveMonoid (Map k a) Source Source

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.

Minimal complete definition

stripSuffix

Methods

isSuffixOf :: m -> m -> Bool Source

stripSuffix :: m -> m -> Maybe m Source

Instances

 Source Source Source Source Source Source Source Source Source Source Ord a => RightReductiveMonoid (Set a) Source Eq a => RightReductiveMonoid (Seq a) Source Eq a => RightReductiveMonoid (Vector a) Source Source Source Source Source Source Source

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

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

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

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

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

Minimal complete definition

Methods

commonPrefix :: m -> m -> m Source

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

Instances

 Source Source Source Source Source Source Source Eq x => LeftGCDMonoid [x] Source Source (Integral a, Ord a) => LeftGCDMonoid (Sum a) Source Integral a => LeftGCDMonoid (Product a) Source Source Eq a => LeftGCDMonoid (IntMap a) Source Ord a => LeftGCDMonoid (Set a) Source Eq a => LeftGCDMonoid (Seq a) Source Eq a => LeftGCDMonoid (Vector a) Source Source Source Source Source (LeftGCDMonoid a, LeftGCDMonoid b) => LeftGCDMonoid (a, b) Source (Ord k, Eq a) => LeftGCDMonoid (Map k a) Source (LeftGCDMonoid a, LeftGCDMonoid b) => LeftGCDMonoid (Stateful a b) Source

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

Minimal complete definition

Methods

commonSuffix :: m -> m -> m Source

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

Instances

 Source Source Source Source Source (Integral a, Ord a) => RightGCDMonoid (Sum a) Source Source Source Ord a => RightGCDMonoid (Set a) Source Eq a => RightGCDMonoid (Seq a) Source Eq a => RightGCDMonoid (Vector a) Source Source Source Source Source (RightGCDMonoid a, RightGCDMonoid b) => RightGCDMonoid (a, b) Source (RightGCDMonoid a, RightGCDMonoid b) => RightGCDMonoid (Stateful a b) Source