semigroups-0.16.1: Anything that associates

Copyright | (C) 2011-2014 Edward Kmett
License | BSD-style (see the file LICENSE)
Maintainer | Edward Kmett <ekmett@gmail.com>
Stability | provisional
Portability | portable
Safe Haskell | Trustworthy
Language | Haskell98

Data.Semigroup

Contents

- Semigroups
- Re-exported monoids from Data.Monoid
- A better monoid for Maybe
- Difference lists of a semigroup

Description

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element. It also (originally) generalized a group (a monoid with all inverses) to a type where every element did not have to have an inverse, thus the name semigroup.

The use of `(<>)` in this module conflicts with an operator with the same name that is being exported by Data.Monoid. However, this package re-exports (most of) the contents of Data.Monoid, so to use semigroups and monoids in the same package just

    import Data.Semigroup

Synopsis

- class Semigroup a where
  - (<>) :: a -> a -> a
  - sconcat :: NonEmpty a -> a
  - times1p :: Natural -> a -> a
- newtype Min a = Min {
  - getMin :: a
  }
- newtype Max a = Max {
  - getMax :: a
  }
- newtype First a = First {
  - getFirst :: a
  }
- newtype Last a = Last {
  - getLast :: a
  }
- newtype WrappedMonoid m = WrapMonoid {
  - unwrapMonoid :: m
  }
- timesN :: Monoid a => Natural -> a -> a
- class Monoid a where
  - mempty :: a
  - mappend :: a -> a -> a
  - mconcat :: [a] -> a
- newtype Dual a :: * -> * = Dual {
  - getDual :: a
  }
- newtype Endo a :: * -> * = Endo {
  - appEndo :: a -> a
  }
- newtype All :: * = All {
  - getAll :: Bool
  }
- newtype Any :: * = Any {
  - getAny :: Bool
  }
- newtype Sum a :: * -> * = Sum {
  - getSum :: a
  }
- newtype Product a :: * -> * = Product {
  - getProduct :: a
  }
- newtype Option a = Option {
  - getOption :: Maybe a
  }
- option :: b -> (a -> b) -> Option a -> b
- diff :: Semigroup m => m -> Endo m
- cycle1 :: Semigroup m => m -> m

# Documentation

class Semigroup a where

Minimal complete definition

Nothing

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.

times1p :: Natural -> a -> a

Repeat a value (n + 1) times.

    times1p n a = a <> a <> ... <> a  -- using <> n times

The default definition uses peasant multiplication, exploiting associativity to only require O(log n) uses of `<>`.

See also `timesN`.

Instances

Semigroup Ordering |
Semigroup () |
Semigroup All |
Semigroup Any |
Semigroup Builder |
Semigroup ByteString |
Semigroup ShortByteString |
Semigroup ByteString |
Semigroup IntSet |
Semigroup Builder |
Semigroup Text |
Semigroup Text |
Semigroup [a] |
Semigroup a => Semigroup (Dual a) |
Semigroup (Endo a) |
Num a => Semigroup (Sum a) |
Num a => Semigroup (Product a) |
Semigroup (First a) |
Semigroup (Last a) |
Semigroup a => Semigroup (Maybe a) |
Semigroup (IntMap v) |
Ord a => Semigroup (Set a) |
Semigroup (Seq a) |
(Hashable a, Eq a) => Semigroup (HashSet a) |
Semigroup (NonEmpty a) |
Semigroup a => Semigroup (Option a) |
Monoid m => Semigroup (WrappedMonoid m) |
Semigroup (Last a) |
Semigroup (First a) |
Ord a => Semigroup (Max a) |
Ord a => Semigroup (Min a) |
Semigroup b => Semigroup (a -> b) |
Semigroup (Either a b) |
(Semigroup a, Semigroup b) => Semigroup (a, b) |
Semigroup a => Semigroup (Const a b) |
Ord k => Semigroup (Map k v) |
(Hashable k, Eq k) => Semigroup (HashMap k a) |
(Semigroup a, Semigroup b, Semigroup c) => Semigroup (a, b, c) |
(Semigroup a, Semigroup b, Semigroup c, Semigroup d) => Semigroup (a, b, c, d) |
(Semigroup a, Semigroup b, Semigroup c, Semigroup d, Semigroup e) => Semigroup (a, b, c, d, e) |

# Semigroups

newtype Min a

Constructors

Min |
Fields getMin :: a

Instances

Monad Min |
Functor Min |
MonadFix Min |
Applicative Min |
Foldable Min |
Traversable Min |
Bounded a => Bounded (Min a) |
Enum a => Enum (Min a) |
Eq a => Eq (Min a) |
Data a => Data (Min a) |
Ord a => Ord (Min a) |
Read a => Read (Min a) |
Show a => Show (Min a) |
Generic (Min a) |
(Ord a, Bounded a) => Monoid (Min a) |
NFData a => NFData (Min a) |
Hashable a => Hashable (Min a) |
Ord a => Semigroup (Min a) |
Typeable (* -> *) Min |
type Rep (Min a) |

newtype Max a

Constructors

Max |
Fields getMax :: a

Instances

Monad Max |
Functor Max |
MonadFix Max |
Applicative Max |
Foldable Max |
Traversable Max |
Bounded a => Bounded (Max a) |
Enum a => Enum (Max a) |
Eq a => Eq (Max a) |
Data a => Data (Max a) |
Ord a => Ord (Max a) |
Read a => Read (Max a) |
Show a => Show (Max a) |
Generic (Max a) |
(Ord a, Bounded a) => Monoid (Max a) |
NFData a => NFData (Max a) |
Hashable a => Hashable (Max a) |
Ord a => Semigroup (Max a) |
Typeable (* -> *) Max |
type Rep (Max a) |

newtype First a

Use ``Option` (`First` a)` to get the behavior of `First` from `Data.Monoid`.

Constructors

First |
Fields getFirst :: a

Instances

Monad First |
Functor First |
MonadFix First |
Applicative First |
Foldable First |
Traversable First |
Bounded a => Bounded (First a) |
Enum a => Enum (First a) |
Eq a => Eq (First a) |
Data a => Data (First a) |
Ord a => Ord (First a) |
Read a => Read (First a) |
Show a => Show (First a) |
Generic (First a) |
NFData a => NFData (First a) |
Hashable a => Hashable (First a) |
Semigroup (First a) |
Typeable (* -> *) First |
type Rep (First a) |

newtype Last a

Use ``Option` (`Last` a)` to get the behavior of `Last` from `Data.Monoid`

Constructors

Last |
Fields getLast :: a

Instances

Monad Last |
Functor Last |
MonadFix Last |
Applicative Last |
Foldable Last |
Traversable Last |
Bounded a => Bounded (Last a) |
Enum a => Enum (Last a) |
Eq a => Eq (Last a) |
Data a => Data (Last a) |
Ord a => Ord (Last a) |
Read a => Read (Last a) |
Show a => Show (Last a) |
Generic (Last a) |
NFData a => NFData (Last a) |
Hashable a => Hashable (Last a) |
Semigroup (Last a) |
Typeable (* -> *) Last |
type Rep (Last a) |

newtype WrappedMonoid m

Provide a Semigroup for an arbitrary Monoid.

Constructors

WrapMonoid |
Fields unwrapMonoid :: m

Instances

Bounded a => Bounded (WrappedMonoid a) |
Enum a => Enum (WrappedMonoid a) |
Eq m => Eq (WrappedMonoid m) |
Data m => Data (WrappedMonoid m) |
Ord m => Ord (WrappedMonoid m) |
Read m => Read (WrappedMonoid m) |
Show m => Show (WrappedMonoid m) |
Generic (WrappedMonoid m) |
Monoid m => Monoid (WrappedMonoid m) |
NFData m => NFData (WrappedMonoid m) |
Hashable a => Hashable (WrappedMonoid a) |
Monoid m => Semigroup (WrappedMonoid m) |
Typeable (* -> *) WrappedMonoid |
type Rep (WrappedMonoid m) |

timesN :: Monoid a => Natural -> a -> a

Repeat a value `n` times.

    timesN n a = a <> a <> ... <> a  -- using <> (n-1) times

Implemented using `times1p`.

# Re-exported monoids from Data.Monoid

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.

Minimal complete definition: `mempty` and `mappend`.

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 `newtype`s and make those instances of `Monoid`, e.g. `Sum` and `Product`.

Minimal complete definition

mempty, mappend

Methods

mempty :: a

Identity of `mappend`

mappend :: a -> a -> a

An associative operation

mconcat :: [a] -> a

Fold a list using the monoid. For most types, the default definition for `mconcat` will be used, but the function is included in the class definition so that an optimized version can be provided for specific types.

Instances

Monoid Ordering |
Monoid () |
Monoid All |
Monoid Any |
Monoid Builder |
Monoid ByteString |
Monoid ShortByteString |
Monoid ByteString |
Monoid IntSet |
Monoid Builder |
Monoid Text |
Monoid Text |
Monoid [a] |
Monoid a => Monoid (Dual a) |
Monoid (Endo a) |
Num a => Monoid (Sum a) |
Num a => Monoid (Product a) |
Monoid (First a) |
Monoid (Last 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.
Monoid (IntMap a) |
Ord a => Monoid (Set a) |
Monoid (Seq a) |
(Hashable a, Eq a) => Monoid (HashSet a) |
Semigroup a => Monoid (Option a) |
Monoid m => Monoid (WrappedMonoid m) |
(Ord a, Bounded a) => Monoid (Max a) |
(Ord a, Bounded a) => Monoid (Min a) |
Monoid b => Monoid (a -> b) |
(Monoid a, Monoid b) => Monoid (a, b) |
Monoid a => Monoid (Const a b) |
Monoid (Proxy * s) |
Ord k => Monoid (Map k v) |
(Eq k, Hashable k) => Monoid (HashMap k v) |
Typeable (* -> Constraint) Monoid |
(Monoid a, Monoid b, Monoid c) => Monoid (a, b, c) |
(Monoid a, Monoid b, Monoid c, Monoid d) => Monoid (a, b, c, d) |
(Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) => Monoid (a, b, c, d, e) |

newtype Dual a :: * -> *

The dual of a monoid, obtained by swapping the arguments of `mappend`.

Constructors

Dual |
Fields getDual :: a

Instances

Generic1 Dual |
Bounded a => Bounded (Dual a) |
Eq a => Eq (Dual a) |
Ord a => Ord (Dual a) |
Read a => Read (Dual a) |
Show a => Show (Dual a) |
Generic (Dual a) |
Monoid a => Monoid (Dual a) |
Semigroup a => Semigroup (Dual a) |
type Rep1 Dual = D1 D1Dual (C1 C1_0Dual (S1 S1_0_0Dual Par1)) |
type Rep (Dual a) = D1 D1Dual (C1 C1_0Dual (S1 S1_0_0Dual (Rec0 a))) |

newtype Endo a :: * -> *

The monoid of endomorphisms under composition.

Constructors

Endo |
Fields appEndo :: a -> a

Instances

Generic (Endo a) |
Monoid (Endo a) |
Semigroup (Endo a) |
type Rep (Endo a) = D1 D1Endo (C1 C1_0Endo (S1 S1_0_0Endo (Rec0 (a -> a)))) |

newtype All :: *

Boolean monoid under conjunction.

Constructors

All |
Fields getAll :: Bool

Instances

Bounded All |
Eq All |
Ord All |
Read All |
Show All |
Generic All |
Monoid All |
Semigroup All |
type Rep All = D1 D1All (C1 C1_0All (S1 S1_0_0All (Rec0 Bool))) |

newtype Any :: *

Boolean monoid under disjunction.

Constructors

Any |
Fields getAny :: Bool

Instances

Bounded Any |
Eq Any |
Ord Any |
Read Any |
Show Any |
Generic Any |
Monoid Any |
Semigroup Any |
type Rep Any = D1 D1Any (C1 C1_0Any (S1 S1_0_0Any (Rec0 Bool))) |

newtype Sum a :: * -> *

Monoid under addition.

Constructors

Sum |
Fields getSum :: a

Instances

Generic1 Sum |
Bounded a => Bounded (Sum a) |
Eq a => Eq (Sum a) |
Num a => Num (Sum a) |
Ord a => Ord (Sum a) |
Read a => Read (Sum a) |
Show a => Show (Sum a) |
Generic (Sum a) |
Num a => Monoid (Sum a) |
Num a => Semigroup (Sum a) |
type Rep1 Sum = D1 D1Sum (C1 C1_0Sum (S1 S1_0_0Sum Par1)) |
type Rep (Sum a) = D1 D1Sum (C1 C1_0Sum (S1 S1_0_0Sum (Rec0 a))) |

newtype Product a :: * -> *

Monoid under multiplication.

Constructors

Product |
Fields getProduct :: a

Instances

Generic1 Product |
Bounded a => Bounded (Product a) |
Eq a => Eq (Product a) |
Num a => Num (Product a) |
Ord a => Ord (Product a) |
Read a => Read (Product a) |
Show a => Show (Product a) |
Generic (Product a) |
Num a => Monoid (Product a) |
Num a => Semigroup (Product a) |
type Rep1 Product = D1 D1Product (C1 C1_0Product (S1 S1_0_0Product Par1)) |
type Rep (Product a) = D1 D1Product (C1 C1_0Product (S1 S1_0_0Product (Rec0 a))) |

# A better monoid for Maybe

newtype Option a

`Option` is effectively `Maybe` with a better instance of `Monoid`, built off of an underlying `Semigroup` instead of an underlying `Monoid`.

Ideally, this type would not exist at all and we would just fix the `Monoid` instance of `Maybe`

Constructors

Option |
Fields getOption :: Maybe a

Instances

Alternative Option |
Monad Option |
Functor Option |
MonadFix Option |
MonadPlus Option |
Applicative Option |
Foldable Option |
Traversable Option |
Eq a => Eq (Option a) |
Data a => Data (Option a) |
Ord a => Ord (Option a) |
Read a => Read (Option a) |
Show a => Show (Option a) |
Generic (Option a) |
Semigroup a => Monoid (Option a) |
NFData a => NFData (Option a) |
Hashable a => Hashable (Option a) |
Semigroup a => Semigroup (Option a) |
Typeable (* -> *) Option |
type Rep (Option a) |

option :: b -> (a -> b) -> Option a -> b

Fold an `Option` case-wise, just like `maybe`.

# Difference lists of a semigroup

diff :: Semigroup m => m -> Endo m

This lets you use a difference list of a `Semigroup` as a `Monoid`.

cycle1 :: Semigroup m => m -> m

A generalization of `cycle` to an arbitrary `Semigroup`. May fail to terminate for some values in some semigroups.