# beuke.org

## A personal blog about computer science topics.

Semigroup
An Associative Magma
Posted on Aug 29 2023 ~ 3 min read

A semigroup is an algebraic structure $(S, \otimes)$ in which $S$ is a non-empty set and $\otimes : S \times S \rightarrow S$ is a binary associative operation on $S$, such that the equation $(a \otimes b) \otimes c = a \otimes (b \otimes c)$ holds for all $a, b, c \in \mathcal{S}$. 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) $\mathcal{C}$ with just one object $S$ and the following conditions:

• The set of morphisms (hom-set) is closed under composition: For every pair of morphisms $f, g$ in $Hom_\mathcal{C}(S,S)$, their composition $f \circ g$ also belongs to $Hom_{C}(S,S)$

• The composition operation is associative: For any three morphisms $f, g, h$ in $Hom_{C}(S, S)$, we have $(f \circ g) \circ h = f \circ (g \circ h)$.

# 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 $({\mathbb {N}},+)$ under addition. This forms a semigroup because addition is associative.

• The natural numbers $({\mathbb {N}}_{0}, \times )$ under multiplication. This forms a semigroup because multiplication is associative, but is also a monoid $\left({\mathbb {N}}_{0},\times,1\right)$ since 1 serves as the identity, as any number multiplied by 1 remains the same.

• Non-empty strings $(\texttt{String},++)$ under concatenation. This forms a semigroup because string concatenation is associative.

### References

1. 0.The diagram displayed at the top of this post is a modified version of Brent Yorgey's Typeclassopedia diagram
2. 1.
3. 2.