In abstract algebra, a semigroup is a set together with a binary operation. For set, in Haskell, you can more or less substitute the word type; there are ways in which types do not perfectly correspond to sets, but it is close enough for this purpose. A binary operation is a function that takes two arguments. The binary operation must be closed – that is, its two arguments and its return value but must all be values from the same set. A semigroup must also obey one law: the law of associativity. That is usually summarized as
Many sets have more than one such operation over them. Integers, for example, are semigroups under both a minimum and a maximum operation.
In Haskell, this algebra is represented by the
Semigroup typeclass, which is in
base since the 188.8.131.52 release, and in
Prelude since GHC 8.4. The
Semigroup class is defined with one main operation,
<>, and a couple of supporting functions.
Because the relationship between a type in Haskell and a typeclass must be unique, it is common to use
newtype wrappers to implement different semigroup operations over what is the same underlying type. For example, the module gives
Max types wrappers around
a, which means they can be wrappers around a great number of types. The
Data.Semigroup module provides many such
Any type that might form semigroups under both such operations can be wrapped in these types and have two unique
Semigroup instances. The
Data.Semigroup are not in
Prelude by default, so they must be imported.
If you’ve come from a language less finicky about typing, you might have been able to do to, for example, multiply a number times a string and had that result in printing the string the requested number of times. You may have worried that Haskell, with its more finicky typing, would not provide you with such a feature. Never fear,
stimes is here.
It’s always relying on the semigroup for the type of the second value – in this case, that is
String – to know how to combine or join the repetition of the value into one value. The above example works like that because the semigroup of strings is the same as that of lists: concatenation. We can also compare using
Product values to see that the final result depends on the chosen semigroup.
When the underlying semigroup is addition, you can understand this as giving you four 2s and then combining them into a final result using addition; when the semigroup is
Product, it gives you four 2s and combines them via multiplication.
In algebra, a group is a set with a binary operation that satisfies the four group axioms:
- closure: the operation on two members of that set produce another member of that same set;
- associativity: often stated as the abiilty to rearrange the order of parentheses when doing multiple applications of the operator, e.g.,
x * (y * z) == (x * y) * z.
- identity: the set has a neutral element – neutral with regard to the binary operation – that, when used as one argument to that binary operation leaves the other argument unchanged; and
- invertibility: every member of the set has an inverse
Semigroup gets its name from being half of a group; a semigroup must satisfy the closure and associativity axioms, but is not beholden to the identity and invertibility axioms.
If you have a semigroup, you might also have a monoid. A monoid has all the components of a semigroup (a set with an associative operation), plus an identity.