Safe Haskell | None |
---|

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:

- class (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
- gcd :: m -> m -> m

- class Monoid m => LeftReductiveMonoid m where
- isPrefixOf :: m -> m -> Bool
- stripPrefix :: m -> m -> Maybe m

- class Monoid m => RightReductiveMonoid m where
- isSuffixOf :: m -> m -> Bool
- stripSuffix :: m -> m -> Maybe m

- class LeftReductiveMonoid m => LeftCancellativeMonoid m
- class RightReductiveMonoid m => RightCancellativeMonoid m
- class LeftReductiveMonoid m => LeftGCDMonoid m where
- commonPrefix :: m -> m -> m
- stripCommonPrefix :: m -> m -> (m, m, m)

- class RightReductiveMonoid m => RightGCDMonoid m where
- commonSuffix :: m -> m -> m
- stripCommonSuffix :: m -> m -> (m, m, m)

# Symmetric monoid classes

class (LeftReductiveMonoid m, RightReductiveMonoid m) => ReductiveMonoid m whereSource

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

ReductiveMonoid IntSet | |

ReductiveMonoid a => ReductiveMonoid (Dual a) | |

Integral a => ReductiveMonoid (Sum a) | |

Integral a => ReductiveMonoid (Product a) | |

Ord a => ReductiveMonoid (Set a) | |

(ReductiveMonoid a, ReductiveMonoid b) => ReductiveMonoid (a, b) |

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

CancellativeMonoid a => CancellativeMonoid (Dual a) | |

Integral a => CancellativeMonoid (Sum a) | |

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

class (ReductiveMonoid m, LeftGCDMonoid m, RightGCDMonoid m) => GCDMonoid m whereSource

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

# Asymmetric monoid classes

class Monoid m => LeftReductiveMonoid m whereSource

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

stripPrefix :: m -> m -> Maybe mSource

LeftReductiveMonoid ByteString | |

LeftReductiveMonoid ByteString | |

LeftReductiveMonoid IntSet | |

LeftReductiveMonoid Text | |

LeftReductiveMonoid Text | |

LeftReductiveMonoid ByteStringUTF8 | |

Eq x => LeftReductiveMonoid [x] | |

RightReductiveMonoid a => LeftReductiveMonoid (Dual a) | |

Integral a => LeftReductiveMonoid (Sum a) | |

Integral a => LeftReductiveMonoid (Product a) | |

Eq a => LeftReductiveMonoid (Seq a) | |

LeftReductiveMonoid (IntMap a) | |

Ord a => LeftReductiveMonoid (Set a) | |

Eq a => LeftReductiveMonoid (Vector a) | |

(LeftReductiveMonoid a, LeftReductiveMonoid b) => LeftReductiveMonoid (a, b) | |

Ord k => LeftReductiveMonoid (Map k a) |

class Monoid m => RightReductiveMonoid m whereSource

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

stripSuffix :: m -> m -> Maybe mSource

RightReductiveMonoid ByteString | |

RightReductiveMonoid ByteString | |

RightReductiveMonoid IntSet | |

RightReductiveMonoid Text | |

RightReductiveMonoid Text | |

LeftReductiveMonoid a => RightReductiveMonoid (Dual a) | |

Integral a => RightReductiveMonoid (Sum a) | |

Integral a => RightReductiveMonoid (Product a) | |

Eq a => RightReductiveMonoid (Seq a) | |

Ord a => RightReductiveMonoid (Set a) | |

Eq a => RightReductiveMonoid (Vector a) | |

(RightReductiveMonoid a, RightReductiveMonoid b) => RightReductiveMonoid (a, b) |

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

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

class LeftReductiveMonoid m => LeftGCDMonoid m whereSource

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

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

LeftGCDMonoid ByteString | |

LeftGCDMonoid ByteString | |

LeftGCDMonoid IntSet | |

LeftGCDMonoid Text | |

LeftGCDMonoid Text | |

LeftGCDMonoid ByteStringUTF8 | |

Eq x => LeftGCDMonoid [x] | |

RightGCDMonoid a => LeftGCDMonoid (Dual a) | |

(Integral a, Ord a) => LeftGCDMonoid (Sum a) | |

Integral a => LeftGCDMonoid (Product a) | |

Eq a => LeftGCDMonoid (Seq a) | |

Eq a => LeftGCDMonoid (IntMap a) | |

Ord a => LeftGCDMonoid (Set a) | |

Eq a => LeftGCDMonoid (Vector a) | |

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

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

class RightReductiveMonoid m => RightGCDMonoid m whereSource

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

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

RightGCDMonoid ByteString | |

RightGCDMonoid ByteString | |

RightGCDMonoid IntSet | |

LeftGCDMonoid a => RightGCDMonoid (Dual a) | |

(Integral a, Ord a) => RightGCDMonoid (Sum a) | |

Integral a => RightGCDMonoid (Product a) | |

Eq a => RightGCDMonoid (Seq a) | |

Ord a => RightGCDMonoid (Set a) | |

Eq a => RightGCDMonoid (Vector a) | |

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