monoid-subclasses-0.1: Subclasses of Monoid

Safe HaskellNone

Data.Monoid.Cancellative

Contents

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:

Synopsis

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

Methods

(</>) :: m -> m -> Maybe mSource

Instances

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

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

Methods

gcd :: m -> m -> mSource

Instances

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.

Methods

isPrefixOf :: m -> m -> BoolSource

stripPrefix :: m -> m -> Maybe mSource

Instances

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.

Methods

isSuffixOf :: m -> m -> BoolSource

stripSuffix :: m -> m -> Maybe mSource

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

Methods

commonPrefix :: m -> m -> mSource

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

Instances

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

Methods

commonSuffix :: m -> m -> mSource

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

Instances