Safe Haskell | Trustworthy |
---|---|
Language | Haskell2010 |
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
Nothing
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.
isPrefixOf :: m -> m -> Bool Source #
stripPrefix :: m -> m -> Maybe m Source #
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.
isSuffixOf :: m -> m -> Bool Source #
stripSuffix :: m -> m -> Maybe m Source #
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