monoid-subclasses-1.2.1: Subclasses of Monoid

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:

• LeftReductive
• LeftCancellative
• RightReductive
• RightCancellative

Since: 1.0

Synopsis

# Symmetric, commutative semigroup classes

class Semigroup g => Commutative g #

An Commutative semigroup is a Semigroup that follows the rule:

a <> b == b <> a

#### Instances

Instances details
 Since: commutative-semigroups-0.0.2.0 Instance detailsDefined in Data.Semigroup.Commutative Trivial commutative semigroup. Instance detailsDefined in Data.Semigroup.Commutative Identity lifts commutative semigroups pointwise (at only one point). Instance detailsDefined in Data.Semigroup.Commutative Commutative a => Commutative (Down a) Instance detailsDefined in Data.Semigroup.Commutative Commutative a => Commutative (Dual a) Instance detailsDefined in Data.Semigroup.Commutative Instance detailsDefined in Data.Semigroup.Commutative Num a => Commutative (Sum a) Instance detailsDefined in Data.Semigroup.Commutative Ord a => Commutative (Set a) Since: commutative-semigroups-0.0.2.0 Instance detailsDefined in Data.Semigroup.Commutative Commutative a => Commutative (Maybe a) Since: commutative-semigroups-0.0.1.0 Instance detailsDefined in Data.Semigroup.Commutative Commutative a => Commutative (Op a b) Instance detailsDefined in Data.Semigroup.Commutative Trivial commutative semigroup, Functor style. Instance detailsDefined in Data.Semigroup.Commutative Commutative b => Commutative (a -> b) Functions lift commutative semigroups pointwise. Instance detailsDefined in Data.Semigroup.Commutative (Commutative a, Commutative b) => Commutative (a, b) Product commutative semigroup. A Pair of commutative semigroups gives rise to a commutative semigroup Instance detailsDefined in Data.Semigroup.Commutative Commutative a => Commutative (Const a x) Const lifts commutative semigroups into a functor. Instance detailsDefined in Data.Semigroup.Commutative (Commutative a, Commutative b, Commutative c) => Commutative (a, b, c) Instance detailsDefined in Data.Semigroup.Commutative (Commutative (f a), Commutative (g a)) => Commutative ((f :*: g) a) Product of commutative semigroups, Functor style. Instance detailsDefined in Data.Semigroup.Commutative (Commutative a, Commutative b, Commutative c, Commutative d) => Commutative (a, b, c, d) Instance detailsDefined in Data.Semigroup.Commutative Commutative (f (g a)) => Commutative ((f :.: g) a) Instance detailsDefined in Data.Semigroup.Commutative (Commutative a, Commutative b, Commutative c, Commutative d, Commutative e) => Commutative (a, b, c, d, e) Instance detailsDefined in Data.Semigroup.Commutative

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

Methods

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

#### Instances

Instances details
 Source # O(m+n) Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods() :: () -> () -> Maybe () Source # Reductive a => Reductive (Dual a) Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods() :: Dual a -> Dual a -> Maybe (Dual a) Source # (CommutativeProduct a, Integral a) => Reductive (Product a) Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods() :: Product a -> Product a -> Maybe (Product a) Source # SumCancellative a => Reductive (Sum a) Source # O(1) Instance detailsDefined in Data.Semigroup.Cancellative Methods() :: Sum a -> Sum a -> Maybe (Sum a) Source # Ord a => Reductive (Set a) Source # O(m*log(nm + 1)), m <= n/ Instance detailsDefined in Data.Semigroup.Cancellative Methods() :: Set a -> Set a -> Maybe (Set a) Source # Reductive x => Reductive (Maybe x) Source # Since: 1.0 Instance detailsDefined in Data.Semigroup.Cancellative Methods() :: Maybe x -> Maybe x -> Maybe (Maybe x) Source # (Reductive a, Reductive b) => Reductive (a, b) Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods() :: (a, b) -> (a, b) -> Maybe (a, b) Source # (Reductive a, Reductive b, Reductive c) => Reductive (a, b, c) Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods() :: (a, b, c) -> (a, b, c) -> Maybe (a, b, c) Source # (Reductive a, Reductive b, Reductive c, Reductive d) => Reductive (a, b, c, d) Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods() :: (a, b, c, d) -> (a, b, c, d) -> Maybe (a, b, c, d) Source #

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

Instances details
 Source # Instance detailsDefined in Data.Semigroup.Cancellative Cancellative a => Cancellative (Dual a) Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative (Cancellative a, Cancellative b) => Cancellative (a, b) Source # Instance detailsDefined in Data.Semigroup.Cancellative (Cancellative a, Cancellative b, Cancellative c) => Cancellative (a, b, c) Source # Instance detailsDefined in Data.Semigroup.Cancellative (Cancellative a, Cancellative b, Cancellative c, Cancellative d) => Cancellative (a, b, c, d) Source # Instance detailsDefined 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

Instances details
 Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods

# 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

stripPrefix

Methods

isPrefixOf :: m -> m -> Bool Source #

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

#### Instances

Instances details
 Source # O(n) Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # O(n) Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # O(m+n) Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # O(n) Instance detailsDefined in Data.Monoid.Instances.ByteString.UTF8 Methods Source # O(n) Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # O(n) Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # O(1) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: () -> () -> Bool Source #stripPrefix :: () -> () -> Maybe () Source # Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: Dual a -> Dual a -> Bool Source #stripPrefix :: Dual a -> Dual a -> Maybe (Dual a) Source # Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: Product a -> Product a -> Bool Source #stripPrefix :: Product a -> Product a -> Maybe (Product a) Source # Source # O(1) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: Sum a -> Sum a -> Bool Source #stripPrefix :: Sum a -> Sum a -> Maybe (Sum a) Source # Eq a => LeftReductive (IntMap a) Source # O(m+n) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: IntMap a -> IntMap a -> Bool Source #stripPrefix :: IntMap a -> IntMap a -> Maybe (IntMap a) Source # Eq a => LeftReductive (Seq a) Source # O(log(min(m,n−m)) + prefixLength) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: Seq a -> Seq a -> Bool Source #stripPrefix :: Seq a -> Seq a -> Maybe (Seq a) Source # Ord a => LeftReductive (Set a) Source # O(m*log(nm + 1)), m <= n/ Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: Set a -> Set a -> Bool Source #stripPrefix :: Set a -> Set a -> Maybe (Set a) Source # Source # Instance detailsDefined in Data.Monoid.Instances.Concat MethodsisPrefixOf :: Concat a -> Concat a -> Bool Source #stripPrefix :: Concat a -> Concat a -> Maybe (Concat a) Source # Source # Instance detailsDefined in Data.Monoid.Instances.Measured MethodsisPrefixOf :: Measured a -> Measured a -> Bool Source #stripPrefix :: Measured a -> Measured a -> Maybe (Measured a) Source # Source # Instance detailsDefined in Data.Monoid.Instances.Positioned Methods Source # Instance detailsDefined in Data.Monoid.Instances.Positioned Methods Eq a => LeftReductive (Vector a) Source # O(n) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: Vector a -> Vector a -> Bool Source #stripPrefix :: Vector a -> Vector a -> Maybe (Vector a) Source # Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: Maybe x -> Maybe x -> Bool Source #stripPrefix :: Maybe x -> Maybe x -> Maybe (Maybe x) Source # Eq x => LeftReductive [x] Source # O(prefixLength) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: [x] -> [x] -> Bool Source #stripPrefix :: [x] -> [x] -> Maybe [x] Source # (Ord k, Eq a) => LeftReductive (Map k a) Source # O(m+n) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: Map k a -> Map k a -> Bool Source #stripPrefix :: Map k a -> Map k a -> Maybe (Map k a) Source # (LeftReductive a, LeftReductive b) => LeftReductive (Stateful a b) Source # Instance detailsDefined in Data.Monoid.Instances.Stateful MethodsisPrefixOf :: Stateful a b -> Stateful a b -> Bool Source #stripPrefix :: Stateful a b -> Stateful a b -> Maybe (Stateful a b) Source # (LeftReductive a, LeftReductive b) => LeftReductive (a, b) Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: (a, b) -> (a, b) -> Bool Source #stripPrefix :: (a, b) -> (a, b) -> Maybe (a, b) Source # (LeftReductive a, LeftReductive b, LeftReductive c) => LeftReductive (a, b, c) Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: (a, b, c) -> (a, b, c) -> Bool Source #stripPrefix :: (a, b, c) -> (a, b, c) -> Maybe (a, b, c) Source # (LeftReductive a, LeftReductive b, LeftReductive c, LeftReductive d) => LeftReductive (a, b, c, d) Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: (a, b, c, d) -> (a, b, c, d) -> Bool Source #stripPrefix :: (a, b, c, d) -> (a, b, c, d) -> Maybe (a, b, c, d) Source #

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

stripSuffix

Methods

isSuffixOf :: m -> m -> Bool Source #

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

#### Instances

Instances details
 Source # O(n) Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # O(n) Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # O(m+n) Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # O(n) Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # O(n) Instance detailsDefined in Data.Semigroup.Cancellative Methods Source # O(1) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: () -> () -> Bool Source #stripSuffix :: () -> () -> Maybe () Source # Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: Dual a -> Dual a -> Bool Source #stripSuffix :: Dual a -> Dual a -> Maybe (Dual a) Source # Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: Product a -> Product a -> Bool Source #stripSuffix :: Product a -> Product a -> Maybe (Product a) Source # Source # O(1) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: Sum a -> Sum a -> Bool Source #stripSuffix :: Sum a -> Sum a -> Maybe (Sum a) Source # Eq a => RightReductive (IntMap a) Source # O(m+n) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: IntMap a -> IntMap a -> Bool Source #stripSuffix :: IntMap a -> IntMap a -> Maybe (IntMap a) Source # Eq a => RightReductive (Seq a) Source # O(log(min(m,n−m)) + suffixLength) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: Seq a -> Seq a -> Bool Source #stripSuffix :: Seq a -> Seq a -> Maybe (Seq a) Source # Ord a => RightReductive (Set a) Source # O(m*log(nm + 1)), m <= n/ Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: Set a -> Set a -> Bool Source #stripSuffix :: Set a -> Set a -> Maybe (Set a) Source # Source # Instance detailsDefined in Data.Monoid.Instances.Concat MethodsisSuffixOf :: Concat a -> Concat a -> Bool Source #stripSuffix :: Concat a -> Concat a -> Maybe (Concat a) Source # Source # Instance detailsDefined in Data.Monoid.Instances.Measured MethodsisSuffixOf :: Measured a -> Measured a -> Bool Source #stripSuffix :: Measured a -> Measured a -> Maybe (Measured a) Source # Source # Instance detailsDefined in Data.Monoid.Instances.Positioned Methods Source # Instance detailsDefined in Data.Monoid.Instances.Positioned Methods Eq a => RightReductive (Vector a) Source # O(n) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: Vector a -> Vector a -> Bool Source #stripSuffix :: Vector a -> Vector a -> Maybe (Vector a) Source # Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: Maybe x -> Maybe x -> Bool Source #stripSuffix :: Maybe x -> Maybe x -> Maybe (Maybe x) Source # Eq x => RightReductive [x] Source # O(m+n)Since: 1.0 Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: [x] -> [x] -> Bool Source #stripSuffix :: [x] -> [x] -> Maybe [x] Source # (Ord k, Eq a) => RightReductive (Map k a) Source # O(m+n) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: Map k a -> Map k a -> Bool Source #stripSuffix :: Map k a -> Map k a -> Maybe (Map k a) Source # (RightReductive a, RightReductive b) => RightReductive (Stateful a b) Source # Instance detailsDefined in Data.Monoid.Instances.Stateful MethodsisSuffixOf :: Stateful a b -> Stateful a b -> Bool Source #stripSuffix :: Stateful a b -> Stateful a b -> Maybe (Stateful a b) Source # (RightReductive a, RightReductive b) => RightReductive (a, b) Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: (a, b) -> (a, b) -> Bool Source #stripSuffix :: (a, b) -> (a, b) -> Maybe (a, b) Source # (RightReductive a, RightReductive b, RightReductive c) => RightReductive (a, b, c) Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: (a, b, c) -> (a, b, c) -> Bool Source #stripSuffix :: (a, b, c) -> (a, b, c) -> Maybe (a, b, c) Source # (RightReductive a, RightReductive b, RightReductive c, RightReductive d) => RightReductive (a, b, c, d) Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: (a, b, c, d) -> (a, b, c, d) -> Bool Source #stripSuffix :: (a, b, c, d) -> (a, b, c, d) -> Maybe (a, b, c, d) Source #

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

Instances details
 Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Monoid.Instances.ByteString.UTF8 Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative Eq a => LeftCancellative (Seq a) Source # Instance detailsDefined in Data.Semigroup.Cancellative Eq a => LeftCancellative (Vector a) Source # Instance detailsDefined in Data.Semigroup.Cancellative Eq x => LeftCancellative [x] Source # Instance detailsDefined in Data.Semigroup.Cancellative (LeftCancellative a, LeftCancellative b) => LeftCancellative (a, b) Source # Instance detailsDefined in Data.Semigroup.Cancellative (LeftCancellative a, LeftCancellative b, LeftCancellative c) => LeftCancellative (a, b, c) Source # Instance detailsDefined in Data.Semigroup.Cancellative (LeftCancellative a, LeftCancellative b, LeftCancellative c, LeftCancellative d) => LeftCancellative (a, b, c, d) Source # Instance detailsDefined in Data.Semigroup.Cancellative

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

#### Instances

Instances details
 Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative Eq a => RightCancellative (Seq a) Source # Instance detailsDefined in Data.Semigroup.Cancellative Eq a => RightCancellative (Vector a) Source # Instance detailsDefined in Data.Semigroup.Cancellative Eq x => RightCancellative [x] Source # Since: 1.0 Instance detailsDefined in Data.Semigroup.Cancellative (RightCancellative a, RightCancellative b) => RightCancellative (a, b) Source # Instance detailsDefined in Data.Semigroup.Cancellative (RightCancellative a, RightCancellative b, RightCancellative c) => RightCancellative (a, b, c) Source # Instance detailsDefined in Data.Semigroup.Cancellative (RightCancellative a, RightCancellative b, RightCancellative c, RightCancellative d) => RightCancellative (a, b, c, d) Source # Instance detailsDefined in Data.Semigroup.Cancellative