monoid-subclasses-1.0.1: Subclasses of Monoid

Safe HaskellTrustworthy
LanguageHaskell2010

Data.Semigroup.Cancellative

Contents

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

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 # 
Instance details

Defined in Data.Semigroup.Cancellative

Commutative IntSet Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Commutative x => Commutative (Maybe x) Source #

Since: 1.0

Instance details

Defined in Data.Semigroup.Cancellative

Commutative a => Commutative (Dual a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Num a => Commutative (Sum a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Num a => Commutative (Product a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Ord a => Commutative (Set a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

(Commutative a, Commutative b) => Commutative (a, b) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

(Commutative a, Commutative b, Commutative c) => Commutative (a, b, c) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

(Commutative a, Commutative b, Commutative c, Commutative d) => Commutative (a, b, c, d) Source # 
Instance details

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

Methods

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

Instances
Reductive () Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Methods

(</>) :: () -> () -> Maybe () Source #

Reductive IntSet Source #

O(m+n)

Instance details

Defined in Data.Semigroup.Cancellative

Reductive x => Reductive (Maybe x) Source #

Since: 1.0

Instance details

Defined in Data.Semigroup.Cancellative

Methods

(</>) :: Maybe x -> Maybe x -> Maybe (Maybe x) Source #

Reductive a => Reductive (Dual a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Methods

(</>) :: Dual a -> Dual a -> Maybe (Dual a) Source #

SumCancellative a => Reductive (Sum a) Source #

O(1)

Instance details

Defined in Data.Semigroup.Cancellative

Methods

(</>) :: Sum a -> Sum a -> Maybe (Sum a) Source #

Integral a => Reductive (Product a) Source # 
Instance details

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

Defined in Data.Semigroup.Cancellative

Methods

(</>) :: Set a -> Set a -> Maybe (Set a) Source #

(Reductive a, Reductive b) => Reductive (a, b) Source # 
Instance details

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

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

Defined 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
Cancellative () Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Cancellative a => Cancellative (Dual a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

SumCancellative a => Cancellative (Sum a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

(Cancellative a, Cancellative b) => Cancellative (a, b) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

(Cancellative a, Cancellative b, Cancellative c) => Cancellative (a, b, c) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

(Cancellative a, Cancellative b, Cancellative c, Cancellative d) => Cancellative (a, b, c, d) Source # 
Instance details

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 #

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
LeftReductive () Source #

O(1)

Instance details

Defined in Data.Semigroup.Cancellative

Methods

isPrefixOf :: () -> () -> Bool Source #

stripPrefix :: () -> () -> Maybe () Source #

LeftReductive ByteString Source #

O(n)

Instance details

Defined in Data.Semigroup.Cancellative

LeftReductive ByteString Source #

O(n)

Instance details

Defined in Data.Semigroup.Cancellative

LeftReductive IntSet Source #

O(m+n)

Instance details

Defined in Data.Semigroup.Cancellative

LeftReductive Text Source #

O(n)

Instance details

Defined in Data.Semigroup.Cancellative

LeftReductive Text Source #

O(n)

Instance details

Defined in Data.Semigroup.Cancellative

LeftReductive ByteStringUTF8 Source #

O(n)

Instance details

Defined in Data.Monoid.Instances.ByteString.UTF8

Eq x => LeftReductive [x] Source #

O(prefixLength)

Instance details

Defined in Data.Semigroup.Cancellative

Methods

isPrefixOf :: [x] -> [x] -> Bool Source #

stripPrefix :: [x] -> [x] -> Maybe [x] Source #

LeftReductive x => LeftReductive (Maybe x) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Methods

isPrefixOf :: Maybe x -> Maybe x -> Bool Source #

stripPrefix :: Maybe x -> Maybe x -> Maybe (Maybe x) Source #

RightReductive a => LeftReductive (Dual a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Methods

isPrefixOf :: Dual a -> Dual a -> Bool Source #

stripPrefix :: Dual a -> Dual a -> Maybe (Dual a) Source #

SumCancellative a => LeftReductive (Sum a) Source #

O(1)

Instance details

Defined in Data.Semigroup.Cancellative

Methods

isPrefixOf :: Sum a -> Sum a -> Bool Source #

stripPrefix :: Sum a -> Sum a -> Maybe (Sum a) Source #

Integral a => LeftReductive (Product a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Eq a => LeftReductive (IntMap a) Source #

O(m+n)

Instance details

Defined in Data.Semigroup.Cancellative

Eq a => LeftReductive (Seq a) Source #

O(log(min(m,n−m)) + prefixLength)

Instance details

Defined in Data.Semigroup.Cancellative

Methods

isPrefixOf :: 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 details

Defined in Data.Semigroup.Cancellative

Methods

isPrefixOf :: Set a -> Set a -> Bool Source #

stripPrefix :: Set a -> Set a -> Maybe (Set a) Source #

Eq a => LeftReductive (Vector a) Source #

O(n)

Instance details

Defined in Data.Semigroup.Cancellative

(StableFactorial m, TextualMonoid m) => LeftReductive (LinePositioned m) Source # 
Instance details

Defined in Data.Monoid.Instances.Positioned

(StableFactorial m, LeftReductive m) => LeftReductive (OffsetPositioned m) Source # 
Instance details

Defined in Data.Monoid.Instances.Positioned

(LeftReductive a, StableFactorial a) => LeftReductive (Measured a) Source # 
Instance details

Defined in Data.Monoid.Instances.Measured

(LeftReductive a, StableFactorial a, PositiveMonoid a) => LeftReductive (Concat a) Source # 
Instance details

Defined in Data.Monoid.Instances.Concat

(LeftReductive a, LeftReductive b) => LeftReductive (a, b) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Methods

isPrefixOf :: (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 details

Defined in Data.Semigroup.Cancellative

Methods

isPrefixOf :: 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 details

Defined in Data.Monoid.Instances.Stateful

Methods

isPrefixOf :: 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 details

Defined in Data.Semigroup.Cancellative

Methods

isPrefixOf :: (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 details

Defined in Data.Semigroup.Cancellative

Methods

isPrefixOf :: (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
RightReductive () Source #

O(1)

Instance details

Defined in Data.Semigroup.Cancellative

Methods

isSuffixOf :: () -> () -> Bool Source #

stripSuffix :: () -> () -> Maybe () Source #

RightReductive ByteString Source #

O(n)

Instance details

Defined in Data.Semigroup.Cancellative

RightReductive ByteString Source #

O(n)

Instance details

Defined in Data.Semigroup.Cancellative

RightReductive IntSet Source #

O(m+n)

Instance details

Defined in Data.Semigroup.Cancellative

RightReductive Text Source #

O(n)

Instance details

Defined in Data.Semigroup.Cancellative

RightReductive Text Source #

O(n)

Instance details

Defined in Data.Semigroup.Cancellative

Eq x => RightReductive [x] Source #

O(m+n)

Since: 1.0

Instance details

Defined in Data.Semigroup.Cancellative

Methods

isSuffixOf :: [x] -> [x] -> Bool Source #

stripSuffix :: [x] -> [x] -> Maybe [x] Source #

RightReductive x => RightReductive (Maybe x) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Methods

isSuffixOf :: Maybe x -> Maybe x -> Bool Source #

stripSuffix :: Maybe x -> Maybe x -> Maybe (Maybe x) Source #

LeftReductive a => RightReductive (Dual a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Methods

isSuffixOf :: Dual a -> Dual a -> Bool Source #

stripSuffix :: Dual a -> Dual a -> Maybe (Dual a) Source #

SumCancellative a => RightReductive (Sum a) Source #

O(1)

Instance details

Defined in Data.Semigroup.Cancellative

Methods

isSuffixOf :: Sum a -> Sum a -> Bool Source #

stripSuffix :: Sum a -> Sum a -> Maybe (Sum a) Source #

Integral a => RightReductive (Product a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Eq a => RightReductive (IntMap a) Source #

O(m+n)

Instance details

Defined in Data.Semigroup.Cancellative

Eq a => RightReductive (Seq a) Source #

O(log(min(m,n−m)) + suffixLength)

Instance details

Defined in Data.Semigroup.Cancellative

Methods

isSuffixOf :: 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 details

Defined in Data.Semigroup.Cancellative

Methods

isSuffixOf :: Set a -> Set a -> Bool Source #

stripSuffix :: Set a -> Set a -> Maybe (Set a) Source #

Eq a => RightReductive (Vector a) Source #

O(n)

Instance details

Defined in Data.Semigroup.Cancellative

(StableFactorial m, TextualMonoid m, RightReductive m) => RightReductive (LinePositioned m) Source # 
Instance details

Defined in Data.Monoid.Instances.Positioned

(StableFactorial m, FactorialMonoid m, RightReductive m) => RightReductive (OffsetPositioned m) Source # 
Instance details

Defined in Data.Monoid.Instances.Positioned

(RightReductive a, StableFactorial a) => RightReductive (Measured a) Source # 
Instance details

Defined in Data.Monoid.Instances.Measured

(RightReductive a, StableFactorial a, PositiveMonoid a) => RightReductive (Concat a) Source # 
Instance details

Defined in Data.Monoid.Instances.Concat

(RightReductive a, RightReductive b) => RightReductive (a, b) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Methods

isSuffixOf :: (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 details

Defined in Data.Semigroup.Cancellative

Methods

isSuffixOf :: 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 details

Defined in Data.Monoid.Instances.Stateful

Methods

isSuffixOf :: 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 details

Defined in Data.Semigroup.Cancellative

Methods

isSuffixOf :: (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 details

Defined in Data.Semigroup.Cancellative

Methods

isSuffixOf :: (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
LeftCancellative () Source # 
Instance details

Defined in Data.Semigroup.Cancellative

LeftCancellative ByteString Source # 
Instance details

Defined in Data.Semigroup.Cancellative

LeftCancellative ByteString Source # 
Instance details

Defined in Data.Semigroup.Cancellative

LeftCancellative Text Source # 
Instance details

Defined in Data.Semigroup.Cancellative

LeftCancellative Text Source # 
Instance details

Defined in Data.Semigroup.Cancellative

LeftCancellative ByteStringUTF8 Source # 
Instance details

Defined in Data.Monoid.Instances.ByteString.UTF8

Eq x => LeftCancellative [x] Source # 
Instance details

Defined in Data.Semigroup.Cancellative

RightCancellative a => LeftCancellative (Dual a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

SumCancellative a => LeftCancellative (Sum a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Eq a => LeftCancellative (Seq a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Eq a => LeftCancellative (Vector a) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

(LeftCancellative a, LeftCancellative b) => LeftCancellative (a, b) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

(LeftCancellative a, LeftCancellative b, LeftCancellative c) => LeftCancellative (a, b, c) Source # 
Instance details

Defined in Data.Semigroup.Cancellative

(LeftCancellative a, LeftCancellative b, LeftCancellative c, LeftCancellative d) => LeftCancellative (a, b, c, d) Source # 
Instance details

Defined 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