semigroup

Definition

A semigroup is a pair consisting a set and a binary operation of such that the operation is associative, a.k.a

Semigroups are a generalization of monoids and groups. A semigroup with an identity element is called a monoid, and a monoid in which every element has an inverse is called a group. associative

In Programming

A semigroup may be represented as something like ¹

module type Semigroup = sig
  type t
  val append : t -> t -> t
end

Note that the append function can be called by a lot of different names such as add, multiply. But we use append throughout this note for consistency.

Programming languages usually can’t guarantee associativity mechanically, so an implementation of Semigroup must ensure the following holds:

append a (append b c) = append (append a b) c

Examples of Semigroup

Numbers

module IntAdd = struct
  type t = int
  let append = ( + )
end
 
module IntMul = struct
  type t = int
  let append = ( * )
end

Boolean

module BoolAnd = struct
  type t = bool
  let append = ( && )
end
 
module BoolOr = struct
  type t = bool
  let append = ( || )
end

String

module String = struct
  type t = string
  let append = ( ^ ) (* ^ is string concatenation syntax in OCaml *)
end

Generic Calculation of Min (or max)

module type Comparible = sig
  type t
  val compare : t -> t -> int
end
 
module Min(C: Comparible) = struct
  type t = C.t
  let append x y = if C.compare x y <= 0 then x else y
end

Applications

• power
• fold/reduce

Footnotes

1. Pragmatic Category Theory | Part 1: Semigroup Intro ↩