A semigroup is an algebraic structure in which is a non-empty set and is a binary associative operation on , such that the equation holds for all . In category theory, a semigroup is a monoid where there might not be an identity element. More formally, a semigroup is a semicategory (a category without the requirement for identiy morphism) with just one object and the following conditions:
-
The set of morphisms (hom-set) is closed under composition: For every pair of morphisms in , their composition also belongs to
-
The composition operation is associative: For any three morphisms in , we have .
Example
A type qualifies as a Semigroup if it offers an associative function (<>), allowing the merging of any two type values into a single one.
Haskell Definition of Semigroup (Interface)
Associativity implies that the following condition must always hold:
An Instance of Semigroup, the List Semigroup
Another Instance, the Maybe Semigroup
All of the above is already implemented in the standard Haskell library, so you can also simply open an interactive Haskell interpreter (ghci) and test the following examples.
Some more examples are:
-
The naturals numbers without zero under addition. This forms a semigroup because addition is associative.
-
The natural numbers under multiplication. This forms a semigroup because multiplication is associative, but is also a monoid since 1 serves as the identity, as any number multiplied by 1 remains the same.
-
Non-empty strings under concatenation. This forms a semigroup because string concatenation is associative.
References
- 0.The diagram displayed at the top of this post is a modified version of Brent Yorgey's Typeclassopedia diagram ↩
- 1.Semigroups in ncatlab ↩
- 2.Semigroups and Monoids ↩