alg-0.2.0.0: Algebraic structures

Algebra

Synopsis

# Documentation

class Semigroup a where #

The class of semigroups (types with an associative binary operation).

Since: 4.9.0.0

Methods

(<>) :: a -> a -> a infixr 6 #

An associative operation.

(a <> b) <> c = a <> (b <> c)


If a is also a Monoid we further require

(<>) = mappend


sconcat :: NonEmpty a -> a #

Reduce a non-empty list with <>

The default definition should be sufficient, but this can be overridden for efficiency.

stimes :: Integral b => b -> a -> a #

Repeat a value n times.

Given that this works on a Semigroup it is allowed to fail if you request 0 or fewer repetitions, and the default definition will do so.

By making this a member of the class, idempotent semigroups and monoids can upgrade this to execute in O(1) by picking stimes = stimesIdempotent or stimes = stimesIdempotentMonoid respectively.

Instances

 Methodsstimes :: Integral b => b -> Ordering -> Ordering # Methods(<>) :: () -> () -> () #sconcat :: NonEmpty () -> () #stimes :: Integral b => b -> () -> () # Methods(<>) :: Void -> Void -> Void #stimes :: Integral b => b -> Void -> Void # Methods(<>) :: All -> All -> All #stimes :: Integral b => b -> All -> All # Methods(<>) :: Any -> Any -> Any #stimes :: Integral b => b -> Any -> Any # Semigroup [a] Methods(<>) :: [a] -> [a] -> [a] #sconcat :: NonEmpty [a] -> [a] #stimes :: Integral b => b -> [a] -> [a] # Semigroup a => Semigroup (Maybe a) Methods(<>) :: Maybe a -> Maybe a -> Maybe a #sconcat :: NonEmpty (Maybe a) -> Maybe a #stimes :: Integral b => b -> Maybe a -> Maybe a # Semigroup a => Semigroup (Identity a) Methods(<>) :: Identity a -> Identity a -> Identity a #sconcat :: NonEmpty (Identity a) -> Identity a #stimes :: Integral b => b -> Identity a -> Identity a # Ord a => Semigroup (Min a) Methods(<>) :: Min a -> Min a -> Min a #sconcat :: NonEmpty (Min a) -> Min a #stimes :: Integral b => b -> Min a -> Min a # Ord a => Semigroup (Max a) Methods(<>) :: Max a -> Max a -> Max a #sconcat :: NonEmpty (Max a) -> Max a #stimes :: Integral b => b -> Max a -> Max a # Methods(<>) :: First a -> First a -> First a #sconcat :: NonEmpty (First a) -> First a #stimes :: Integral b => b -> First a -> First a # Methods(<>) :: Last a -> Last a -> Last a #sconcat :: NonEmpty (Last a) -> Last a #stimes :: Integral b => b -> Last a -> Last a # Monoid m => Semigroup (WrappedMonoid m) Methods(<>) :: WrappedMonoid m -> WrappedMonoid m -> WrappedMonoid m #stimes :: Integral b => b -> WrappedMonoid m -> WrappedMonoid m # Semigroup a => Semigroup (Option a) Methods(<>) :: Option a -> Option a -> Option a #sconcat :: NonEmpty (Option a) -> Option a #stimes :: Integral b => b -> Option a -> Option a # Methods(<>) :: NonEmpty a -> NonEmpty a -> NonEmpty a #sconcat :: NonEmpty (NonEmpty a) -> NonEmpty a #stimes :: Integral b => b -> NonEmpty a -> NonEmpty a # Semigroup a => Semigroup (Dual a) Methods(<>) :: Dual a -> Dual a -> Dual a #sconcat :: NonEmpty (Dual a) -> Dual a #stimes :: Integral b => b -> Dual a -> Dual a # Methods(<>) :: Endo a -> Endo a -> Endo a #sconcat :: NonEmpty (Endo a) -> Endo a #stimes :: Integral b => b -> Endo a -> Endo a # Num a => Semigroup (Sum a) Methods(<>) :: Sum a -> Sum a -> Sum a #sconcat :: NonEmpty (Sum a) -> Sum a #stimes :: Integral b => b -> Sum a -> Sum a # Num a => Semigroup (Product a) Methods(<>) :: Product a -> Product a -> Product a #sconcat :: NonEmpty (Product a) -> Product a #stimes :: Integral b => b -> Product a -> Product a # Methods(<>) :: First a -> First a -> First a #sconcat :: NonEmpty (First a) -> First a #stimes :: Integral b => b -> First a -> First a # Methods(<>) :: Last a -> Last a -> Last a #sconcat :: NonEmpty (Last a) -> Last a #stimes :: Integral b => b -> Last a -> Last a # Semigroup b => Semigroup (a -> b) Methods(<>) :: (a -> b) -> (a -> b) -> a -> b #sconcat :: NonEmpty (a -> b) -> a -> b #stimes :: Integral b => b -> (a -> b) -> a -> b # Semigroup (Either a b) Methods(<>) :: Either a b -> Either a b -> Either a b #sconcat :: NonEmpty (Either a b) -> Either a b #stimes :: Integral b => b -> Either a b -> Either a b # (Semigroup a, Semigroup b) => Semigroup (a, b) Methods(<>) :: (a, b) -> (a, b) -> (a, b) #sconcat :: NonEmpty (a, b) -> (a, b) #stimes :: Integral b => b -> (a, b) -> (a, b) # Semigroup (Proxy k s) Methods(<>) :: Proxy k s -> Proxy k s -> Proxy k s #sconcat :: NonEmpty (Proxy k s) -> Proxy k s #stimes :: Integral b => b -> Proxy k s -> Proxy k s # (Semigroup a, Semigroup b, Semigroup c) => Semigroup (a, b, c) Methods(<>) :: (a, b, c) -> (a, b, c) -> (a, b, c) #sconcat :: NonEmpty (a, b, c) -> (a, b, c) #stimes :: Integral b => b -> (a, b, c) -> (a, b, c) # Semigroup a => Semigroup (Const k a b) Methods(<>) :: Const k a b -> Const k a b -> Const k a b #sconcat :: NonEmpty (Const k a b) -> Const k a b #stimes :: Integral b => b -> Const k a b -> Const k a b # Alternative f => Semigroup (Alt * f a) Methods(<>) :: Alt * f a -> Alt * f a -> Alt * f a #sconcat :: NonEmpty (Alt * f a) -> Alt * f a #stimes :: Integral b => b -> Alt * f a -> Alt * f a # (Semigroup a, Semigroup b, Semigroup c, Semigroup d) => Semigroup (a, b, c, d) Methods(<>) :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d) #sconcat :: NonEmpty (a, b, c, d) -> (a, b, c, d) #stimes :: Integral b => b -> (a, b, c, d) -> (a, b, c, d) # (Semigroup a, Semigroup b, Semigroup c, Semigroup d, Semigroup e) => Semigroup (a, b, c, d, e) Methods(<>) :: (a, b, c, d, e) -> (a, b, c, d, e) -> (a, b, c, d, e) #sconcat :: NonEmpty (a, b, c, d, e) -> (a, b, c, d, e) #stimes :: Integral b => b -> (a, b, c, d, e) -> (a, b, c, d, e) #

class Monoid a where #

The class of monoids (types with an associative binary operation that has an identity). Instances should satisfy the following laws:

• mappend mempty x = x
• mappend x mempty = x
• mappend x (mappend y z) = mappend (mappend x y) z
• mconcat = foldr mappend mempty

The method names refer to the monoid of lists under concatenation, but there are many other instances.

Some types can be viewed as a monoid in more than one way, e.g. both addition and multiplication on numbers. In such cases we often define newtypes and make those instances of Monoid, e.g. Sum and Product.

Minimal complete definition

Methods

mempty :: a #

Identity of mappend

Instances

 Methodsmconcat :: [Ordering] -> Ordering # Monoid () Methodsmempty :: () #mappend :: () -> () -> () #mconcat :: [()] -> () # Methodsmappend :: All -> All -> All #mconcat :: [All] -> All # Methodsmappend :: Any -> Any -> Any #mconcat :: [Any] -> Any # Monoid [a] Methodsmempty :: [a] #mappend :: [a] -> [a] -> [a] #mconcat :: [[a]] -> [a] # Monoid a => Monoid (Maybe a) Lift a semigroup into Maybe forming a Monoid according to http://en.wikipedia.org/wiki/Monoid: "Any semigroup S may be turned into a monoid simply by adjoining an element e not in S and defining e*e = e and e*s = s = s*e for all s ∈ S." Since there is no "Semigroup" typeclass providing just mappend, we use Monoid instead. Methodsmempty :: Maybe a #mappend :: Maybe a -> Maybe a -> Maybe a #mconcat :: [Maybe a] -> Maybe a # Monoid a => Monoid (IO a) Methodsmempty :: IO a #mappend :: IO a -> IO a -> IO a #mconcat :: [IO a] -> IO a # Monoid a => Monoid (Identity a) Methodsmappend :: Identity a -> Identity a -> Identity a #mconcat :: [Identity a] -> Identity a # (Ord a, Bounded a) => Monoid (Min a) Methodsmempty :: Min a #mappend :: Min a -> Min a -> Min a #mconcat :: [Min a] -> Min a # (Ord a, Bounded a) => Monoid (Max a) Methodsmempty :: Max a #mappend :: Max a -> Max a -> Max a #mconcat :: [Max a] -> Max a # Monoid m => Monoid (WrappedMonoid m) Methodsmconcat :: [WrappedMonoid m] -> WrappedMonoid m # Semigroup a => Monoid (Option a) Methodsmappend :: Option a -> Option a -> Option a #mconcat :: [Option a] -> Option a # Monoid a => Monoid (Dual a) Methodsmempty :: Dual a #mappend :: Dual a -> Dual a -> Dual a #mconcat :: [Dual a] -> Dual a # Monoid (Endo a) Methodsmempty :: Endo a #mappend :: Endo a -> Endo a -> Endo a #mconcat :: [Endo a] -> Endo a # Num a => Monoid (Sum a) Methodsmempty :: Sum a #mappend :: Sum a -> Sum a -> Sum a #mconcat :: [Sum a] -> Sum a # Num a => Monoid (Product a) Methodsmappend :: Product a -> Product a -> Product a #mconcat :: [Product a] -> Product a # Monoid (First a) Methodsmempty :: First a #mappend :: First a -> First a -> First a #mconcat :: [First a] -> First a # Monoid (Last a) Methodsmempty :: Last a #mappend :: Last a -> Last a -> Last a #mconcat :: [Last a] -> Last a # Monoid b => Monoid (a -> b) Methodsmempty :: a -> b #mappend :: (a -> b) -> (a -> b) -> a -> b #mconcat :: [a -> b] -> a -> b # (Monoid a, Monoid b) => Monoid (a, b) Methodsmempty :: (a, b) #mappend :: (a, b) -> (a, b) -> (a, b) #mconcat :: [(a, b)] -> (a, b) # Monoid (Proxy k s) Methodsmempty :: Proxy k s #mappend :: Proxy k s -> Proxy k s -> Proxy k s #mconcat :: [Proxy k s] -> Proxy k s # (Monoid a, Monoid b, Monoid c) => Monoid (a, b, c) Methodsmempty :: (a, b, c) #mappend :: (a, b, c) -> (a, b, c) -> (a, b, c) #mconcat :: [(a, b, c)] -> (a, b, c) # Monoid a => Monoid (Const k a b) Methodsmempty :: Const k a b #mappend :: Const k a b -> Const k a b -> Const k a b #mconcat :: [Const k a b] -> Const k a b # Alternative f => Monoid (Alt * f a) Methodsmempty :: Alt * f a #mappend :: Alt * f a -> Alt * f a -> Alt * f a #mconcat :: [Alt * f a] -> Alt * f a # (Monoid a, Monoid b, Monoid c, Monoid d) => Monoid (a, b, c, d) Methodsmempty :: (a, b, c, d) #mappend :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d) #mconcat :: [(a, b, c, d)] -> (a, b, c, d) # (Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) => Monoid (a, b, c, d, e) Methodsmempty :: (a, b, c, d, e) #mappend :: (a, b, c, d, e) -> (a, b, c, d, e) -> (a, b, c, d, e) #mconcat :: [(a, b, c, d, e)] -> (a, b, c, d, e) #

class Monoid a => Group a where Source #

Minimal complete definition

invert

Methods

invert :: a -> a Source #

Instances

 Group () Source # Methodsinvert :: () -> () Source # Group a => Group (Identity a) Source # Methods Group a => Group (Dual a) Source # Methodsinvert :: Dual a -> Dual a Source # Source # Methods Source # Methods Source # Methods Group b => Group (a -> b) Source # Methodsinvert :: (a -> b) -> a -> b Source # (Group a, Group b) => Group (a, b) Source # Methodsinvert :: (a, b) -> (a, b) Source # Group (Proxy k a) Source # Methodsinvert :: Proxy k a -> Proxy k a Source # (Group a, Group b, Group c) => Group (a, b, c) Source # Methodsinvert :: (a, b, c) -> (a, b, c) Source # Group a => Group (Const k a b) Source # Methodsinvert :: Const k a b -> Const k a b Source # (Group a, Group b, Group c, Group d) => Group (a, b, c, d) Source # Methodsinvert :: (a, b, c, d) -> (a, b, c, d) Source # (Group a, Group b, Group c, Group d, Group e) => Group (a, b, c, d, e) Source # Methodsinvert :: (a, b, c, d, e) -> (a, b, c, d, e) Source #

class Semigroup a => Abelian a Source #

Instances

 Abelian () Source # Source # Source # Abelian a => Abelian (Identity a) Source # Source # Source # Source # Source # Source # Source # Source # Source # Abelian a => Abelian (Dual a) Source # Source # Source # Source # Source # Source # Source # Source # Source # Abelian b => Abelian (a -> b) Source # (Abelian a, Abelian b) => Abelian (a, b) Source # Abelian (Proxy k a) Source # (Abelian a, Abelian b, Abelian c) => Abelian (a, b, c) Source # Abelian a => Abelian (Const k a b) Source # (Abelian a, Abelian b, Abelian c, Abelian d) => Abelian (a, b, c, d) Source # (Abelian a, Abelian b, Abelian c, Abelian d, Abelian e) => Abelian (a, b, c, d, e) Source #

class Semigroup a => Idempotent a Source #

Instances

 Source # Idempotent a => Idempotent (Identity a) Source # Ord a => Idempotent (Min a) Source # Ord a => Idempotent (Max a) Source # Idempotent a => Idempotent (Dual a) Source # Idempotent b => Idempotent (a -> b) Source # (Idempotent a, Idempotent b) => Idempotent (a, b) Source # Idempotent (Proxy k a) Source # (Idempotent a, Idempotent b, Idempotent c) => Idempotent (a, b, c) Source # Idempotent a => Idempotent (Const k a b) Source # (Idempotent a, Idempotent b, Idempotent c, Idempotent d) => Idempotent (a, b, c, d) Source # (Idempotent a, Idempotent b, Idempotent c, Idempotent d, Idempotent e) => Idempotent (a, b, c, d, e) Source #

(+) :: Semigroup (Sum a) => a -> a -> a Source #

(-) :: (Semigroup (Sum a), Group (Sum a)) => a -> a -> a Source #

(*) :: Semigroup (Product a) => a -> a -> a Source #

(/) :: (Semigroup (Product a), Group (Product a)) => a -> a -> a Source #