monoid-subclasses-1.0: 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 m => Commutative m Source #

Class of all Abelian (i.e., commutative) semigroups that satisfy the commutativity property:

a <> b == b <> a
Instances
 Source # Instance detailsDefined in Data.Semigroup.Cancellative Source # Instance detailsDefined in Data.Semigroup.Cancellative Commutative x => Commutative (Maybe x) Source # Since: 1.0 Instance detailsDefined in Data.Semigroup.Cancellative Commutative a => Commutative (Dual a) Source # Instance detailsDefined in Data.Semigroup.Cancellative Num a => Commutative (Sum a) Source # Instance detailsDefined in Data.Semigroup.Cancellative Num a => Commutative (Product a) Source # Instance detailsDefined in Data.Semigroup.Cancellative Ord a => Commutative (Set a) Source # Instance detailsDefined in Data.Semigroup.Cancellative (Commutative a, Commutative b) => Commutative (a, b) Source # Instance detailsDefined in Data.Semigroup.Cancellative (Commutative a, Commutative b, Commutative c) => Commutative (a, b, c) Source # Instance detailsDefined in Data.Semigroup.Cancellative (Commutative a, Commutative b, Commutative c, Commutative d) => Commutative (a, b, c, d) Source # Instance detailsDefined 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

Methods

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

Instances
 Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods() :: () -> () -> Maybe () Source # Source # O(m+n) Instance detailsDefined in Data.Semigroup.Cancellative Methods 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 (Dual a) Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods() :: Dual a -> Dual a -> Maybe (Dual 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 # Integral a => Reductive (Product a) Source # Instance detailsDefined in Data.Semigroup.Cancellative Methods() :: Product a -> Product a -> Maybe (Product 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 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
 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
 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
 Source # O(1) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: () -> () -> Bool Source #stripPrefix :: () -> () -> Maybe () Source # 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(n) Instance detailsDefined in Data.Monoid.Instances.ByteString.UTF8 Methods Eq x => LeftReductive [x] Source # O(prefixLength) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: [x] -> [x] -> Bool Source #stripPrefix :: [x] -> [x] -> Maybe [x] Source # Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: Maybe x -> Maybe x -> Bool Source #stripPrefix :: Maybe x -> Maybe x -> Maybe (Maybe x) 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 # O(1) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: Sum a -> Sum a -> Bool Source #stripPrefix :: Sum a -> Sum a -> Maybe (Sum a) Source # Integral a => LeftReductive (Product a) Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisPrefixOf :: Product a -> Product a -> Bool Source #stripPrefix :: Product a -> Product a -> Maybe (Product 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 # 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.Monoid.Instances.Positioned Methods Source # Instance detailsDefined in Data.Monoid.Instances.Positioned Methods 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.Concat MethodsisPrefixOf :: Concat a -> Concat a -> Bool Source #stripPrefix :: Concat a -> Concat a -> Maybe (Concat a) 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 # (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 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
 Source # O(1) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: () -> () -> Bool Source #stripSuffix :: () -> () -> Maybe () Source # 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 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 # Source # Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: Maybe x -> Maybe x -> Bool Source #stripSuffix :: Maybe x -> Maybe x -> Maybe (Maybe x) 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 # O(1) Instance detailsDefined in Data.Semigroup.Cancellative MethodsisSuffixOf :: Sum a -> Sum a -> Bool Source #stripSuffix :: Sum a -> Sum a -> Maybe (Sum 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 # 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 # 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.Monoid.Instances.Positioned Methods Source # Instance detailsDefined in Data.Monoid.Instances.Positioned Methods 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.Concat MethodsisSuffixOf :: Concat a -> Concat a -> Bool Source #stripSuffix :: Concat a -> Concat a -> Maybe (Concat a) 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 # (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 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
 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.Monoid.Instances.ByteString.UTF8 Eq x => LeftCancellative [x] 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 (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
 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 x => RightCancellative [x] Source # Since: 1.0 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 (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