monoid-subclasses-1.2.4.1: Subclasses of Monoid
Safe HaskellTrustworthy
LanguageHaskell2010

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

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
Commutative IntSet

Since: commutative-semigroups-0.0.2.0

Instance details

Defined in Data.Semigroup.Commutative

Commutative ()

Trivial commutative semigroup.

Instance details

Defined in Data.Semigroup.Commutative

Commutative a => Commutative (Identity a)

Identity lifts commutative semigroups pointwise (at only one point).

Instance details

Defined in Data.Semigroup.Commutative

Commutative a => Commutative (Down a) 
Instance details

Defined in Data.Semigroup.Commutative

Commutative a => Commutative (Dual a) 
Instance details

Defined in Data.Semigroup.Commutative

CommutativeProduct a => Commutative (Product a) 
Instance details

Defined in Data.Semigroup.Commutative

Num a => Commutative (Sum a) 
Instance details

Defined in Data.Semigroup.Commutative

Ord a => Commutative (Set a)

Since: commutative-semigroups-0.0.2.0

Instance details

Defined in Data.Semigroup.Commutative

Commutative a => Commutative (Maybe a)

Since: commutative-semigroups-0.0.1.0

Instance details

Defined in Data.Semigroup.Commutative

Commutative a => Commutative (Op a b) 
Instance details

Defined in Data.Semigroup.Commutative

Commutative (Proxy x)

Trivial commutative semigroup, Functor style.

Instance details

Defined in Data.Semigroup.Commutative

Commutative b => Commutative (a -> b)

Functions lift commutative semigroups pointwise.

Instance details

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

Defined in Data.Semigroup.Commutative

Commutative a => Commutative (Const a x)

Const lifts commutative semigroups into a functor.

Instance details

Defined in Data.Semigroup.Commutative

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

Defined in Data.Semigroup.Commutative

(Commutative (f a), Commutative (g a)) => Commutative ((f :*: g) a)

Product of commutative semigroups, Functor style.

Instance details

Defined in Data.Semigroup.Commutative

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

Defined in Data.Semigroup.Commutative

Commutative (f (g a)) => Commutative ((f :.: g) a) 
Instance details

Defined in Data.Semigroup.Commutative

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

Defined 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
Reductive IntSet Source #

O(m+n)

Instance details

Defined in Data.Semigroup.Cancellative

Reductive () Source # 
Instance details

Defined in Data.Semigroup.Cancellative

Methods

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

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

Defined in Data.Semigroup.Cancellative

Methods

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

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

Defined in Data.Semigroup.Cancellative

Methods

(</>) :: Product a -> Product a -> Maybe (Product 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 #

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

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

Instances details
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 ByteStringUTF8 Source #

O(n)

Instance details

Defined in Data.Monoid.Instances.ByteString.UTF8

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

O(1)

Instance details

Defined in Data.Semigroup.Cancellative

Methods

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

stripPrefix :: () -> () -> Maybe () 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 #

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

Defined in Data.Semigroup.Cancellative

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 #

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 #

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

Defined in Data.Monoid.Instances.Concat

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

Defined in Data.Monoid.Instances.Measured

(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

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

Defined in Data.Monoid.Instances.PrefixMemory

Eq a => LeftReductive (Vector a) Source #

O(n)

Instance details

Defined in Data.Semigroup.Cancellative

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 #

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 #

(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 (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 #

(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

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

RightReductive () Source #

O(1)

Instance details

Defined in Data.Semigroup.Cancellative

Methods

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

stripSuffix :: () -> () -> Maybe () 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 #

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

Defined in Data.Semigroup.Cancellative

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 #

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 #

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

Defined in Data.Monoid.Instances.Concat

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

Defined in Data.Monoid.Instances.Measured

(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

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

Defined in Data.Monoid.Instances.PrefixMemory

Eq a => RightReductive (Vector a) Source #

O(n)

Instance details

Defined in Data.Semigroup.Cancellative

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 #

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 #

(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 (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 #

(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

Instances details
LeftCancellative ByteString Source # 
Instance details

Defined in Data.Semigroup.Cancellative

LeftCancellative ByteString Source # 
Instance details

Defined in Data.Semigroup.Cancellative

LeftCancellative ByteStringUTF8 Source # 
Instance details

Defined in Data.Monoid.Instances.ByteString.UTF8

LeftCancellative Text Source # 
Instance details

Defined in Data.Semigroup.Cancellative

LeftCancellative Text Source # 
Instance details

Defined in Data.Semigroup.Cancellative

LeftCancellative () 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

Eq x => LeftCancellative [x] 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