| Safe Haskell | Trustworthy |
|---|---|
| Language | Haskell2010 |
Data.Semigroup.Cancellative
Description
This module defines the Semigroup => Reductive => Cancellative class hierarchy.
The Reductive class introduces operation </> which is the inverse of <>. For the Sum semigroup, this
operation is subtraction; for Product it is division and for Set it's the set difference. A Reductive
semigroup is not a full group because </> may return Nothing.
The Cancellative subclass does not add any operation but it provides the additional guarantee that <> can
always be undone with </>. Thus Sum is Cancellative but Product is not because (0*n)/0 is not defined.
All semigroup subclasses listed above are for Abelian, i.e., commutative or symmetric semigroups. Since most practical semigroups in Haskell are not Abelian, each of the these classes has two symmetric superclasses:
Since: 1.0
Synopsis
- class Semigroup m => Commutative m
- class (Commutative m, LeftReductive m, RightReductive m) => Reductive m where
- class (LeftCancellative m, RightCancellative m, Reductive m) => Cancellative m
- class Num a => SumCancellative a where
- cancelAddition :: a -> a -> Maybe a
- class Semigroup m => LeftReductive m where
- isPrefixOf :: m -> m -> Bool
- stripPrefix :: m -> m -> Maybe m
- class Semigroup m => RightReductive m where
- isSuffixOf :: m -> m -> Bool
- stripSuffix :: m -> m -> Maybe m
- class LeftReductive m => LeftCancellative m
- class RightReductive m => RightCancellative m
Symmetric, commutative semigroup classes
class Semigroup m => Commutative m Source #
Class of all Abelian (i.e., commutative) semigroups that satisfy the commutativity property:
a <> b == b <> a
Instances
| Commutative () Source # | |
Defined in Data.Semigroup.Cancellative | |
| Commutative IntSet Source # | |
Defined in Data.Semigroup.Cancellative | |
| Commutative x => Commutative (Maybe x) Source # | Since: 1.0 |
Defined in Data.Semigroup.Cancellative | |
| Commutative a => Commutative (Dual a) Source # | |
Defined in Data.Semigroup.Cancellative | |
| Num a => Commutative (Sum a) Source # | |
Defined in Data.Semigroup.Cancellative | |
| Num a => Commutative (Product a) Source # | |
Defined in Data.Semigroup.Cancellative | |
| Ord a => Commutative (Set a) Source # | |
Defined in Data.Semigroup.Cancellative | |
| (Commutative a, Commutative b) => Commutative (a, b) Source # | |
Defined in Data.Semigroup.Cancellative | |
| (Commutative a, Commutative b, Commutative c) => Commutative (a, b, c) Source # | |
Defined in Data.Semigroup.Cancellative | |
| (Commutative a, Commutative b, Commutative c, Commutative d) => Commutative (a, b, c, d) Source # | |
Defined in Data.Semigroup.Cancellative | |
class (Commutative m, LeftReductive m, RightReductive m) => Reductive m where Source #
Class of Abelian semigroups with a partial inverse for the Semigroup <> operation. The inverse operation </> must
satisfy the following laws:
maybe a (b <>) (a </> b) == a maybe a (<> b) (a </> b) == a
The </> operator is a synonym for both stripPrefix and stripSuffix, which must be equivalent as <> is both
associative and commutative.
(</>) = flip stripPrefix (</>) = flip stripSuffix
Instances
| Reductive () Source # | |
Defined in Data.Semigroup.Cancellative | |
| Reductive IntSet Source # | O(m+n) |
| Reductive x => Reductive (Maybe x) Source # | Since: 1.0 |
| Reductive a => Reductive (Dual a) Source # | |
| SumCancellative a => Reductive (Sum a) Source # | O(1) |
| Integral a => Reductive (Product a) Source # | |
| Ord a => Reductive (Set a) Source # | O(m*log(nm + 1)), m <= n/ |
| (Reductive a, Reductive b) => Reductive (a, b) Source # | |
Defined in Data.Semigroup.Cancellative | |
| (Reductive a, Reductive b, Reductive c) => Reductive (a, b, c) Source # | |
Defined in Data.Semigroup.Cancellative | |
| (Reductive a, Reductive b, Reductive c, Reductive d) => Reductive (a, b, c, d) Source # | |
Defined in Data.Semigroup.Cancellative | |
class (LeftCancellative m, RightCancellative m, Reductive m) => Cancellative m Source #
Subclass of Reductive where </> is a complete inverse of the Semigroup <> operation. The class
instances must satisfy the following additional laws:
(a <> b) </> a == Just b (a <> b) </> b == Just a
Instances
| Cancellative () Source # | |
Defined in Data.Semigroup.Cancellative | |
| Cancellative a => Cancellative (Dual a) Source # | |
Defined in Data.Semigroup.Cancellative | |
| SumCancellative a => Cancellative (Sum a) Source # | |
Defined in Data.Semigroup.Cancellative | |
| (Cancellative a, Cancellative b) => Cancellative (a, b) Source # | |
Defined in Data.Semigroup.Cancellative | |
| (Cancellative a, Cancellative b, Cancellative c) => Cancellative (a, b, c) Source # | |
Defined in Data.Semigroup.Cancellative | |
| (Cancellative a, Cancellative b, Cancellative c, Cancellative d) => Cancellative (a, b, c, d) Source # | |
Defined in Data.Semigroup.Cancellative | |
class Num a => SumCancellative a where Source #
Helper class to avoid FlexibleInstances
Minimal complete definition
Nothing
Methods
cancelAddition :: a -> a -> Maybe a Source #
Instances
| SumCancellative Int Source # | |
Defined in Data.Semigroup.Cancellative | |
| SumCancellative Integer Source # | |
Defined in Data.Semigroup.Cancellative | |
| SumCancellative Natural Source # | |
Defined in Data.Semigroup.Cancellative | |
| SumCancellative Rational Source # | |
Defined in Data.Semigroup.Cancellative | |
Asymmetric semigroup classes
class Semigroup m => LeftReductive m where Source #
Class of semigroups with a left inverse of <>, 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.
Minimal complete definition
Instances
class Semigroup m => RightReductive m where Source #
Class of semigroups with a right inverse of <>, 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.
Minimal complete definition
Instances
class LeftReductive m => LeftCancellative m Source #
Subclass of LeftReductive where stripPrefix is a complete inverse of <>, satisfying the following
additional law:
stripPrefix a (a <> b) == Just b
Instances
class RightReductive m => RightCancellative m Source #
Subclass of LeftReductive where stripPrefix is a complete inverse of <>, satisfying the following
additional law:
stripSuffix b (a <> b) == Just a