beuke.org

A personal blog about computer science topics.

Semigroup
An Associative Magma
Posted on Aug 29 2023 ~ 3 min read
#category theory  #haskell  #abstract algebra 


Functor Functor Applicative Applicative Functor->Applicative Traversable Traversable Functor->Traversable Applicative->Traversable Alternative Alternative Applicative->Alternative Monad Monad Applicative->Monad Apply Apply Apply->Applicative Semigroup Semigroup Semigroup->Apply Monoid Monoid Semigroup->Monoid MonadPlus MonadPlus Monad->MonadPlus MonadFix MonadFix Monad->MonadFix ArrowApply ArrowApply Monad->ArrowApply Monoid->Applicative Monoid->Alternative Monoid->Monad Monoid->MonadPlus Category Category Monoid->Category ArrowPlus ArrowPlus Monoid->ArrowPlus Foldable Foldable Monoid->Foldable Magma Magma Magma->Semigroup Arrow Arrow Category->Arrow Foldable->Traversable Arrow->ArrowApply ArrowChoice ArrowChoice Arrow->ArrowChoice ArrowZero ArrowZero Arrow->ArrowZero ArrowZero->ArrowPlus

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

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

  • The composition operation is associative: For any three morphisms f , g , h f, g, h in H o m C ( S , S ) Hom_{C}(S, S) , we have ( f g ) h = f ( g h ) (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)

class Semigroup a where
    -- ⊗  :  S x S  -> S (multiplication)
    (<>) :: a -> a -> a

Associativity implies that the following condition must always hold:

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

An Instance of Semigroup, the List Semigroup

instance Semigroup [a] where
    (<>) = (++)

Another Instance, the Maybe Semigroup

instance Semigroup a => Semigroup (Maybe a) where
    Just a  <> Just b  = Just (<> b)
    Just a  <> Nothing = Just a
    Nothing <> Just b  = Just b
    Nothing <> Nothing = Nothing

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.

ghci> [1,2,3] <> [4,5,6]
[1,2,3,4,5,6]

ghci> Just "A" <> Just "B"
Just "AB"

ghci> Nothing <> Just "A" <> Nothing
Just "A"

ghci> Nothing <> Nothing
Nothing

Some more examples are:

  • The naturals numbers without zero ( N , + ) ({\mathbb {N}},+) under addition. This forms a semigroup because addition is associative.

  • The natural numbers ( N 0 , × ) ({\mathbb {N}}_{0}, \times ) under multiplication. This forms a semigroup because multiplication is associative, but is also a monoid ( N 0 , × , 1 ) \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 ( String , + + ) (\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.Semigroups in ncatlab
  3. 2.Semigroups and Monoids