Definition of Semigroup

Semigroup is magma algebraic structure with additional requirement - associativity property of operation. So in exactly the same way how we describe magma as pair (S, *) where S is a set (in our context set equal type), and * is binary, closed operation over S defined as (S,S) -> S, we describe semigroup, with one additional rule:

// associativity rule of operation *
forall a,b,c in S, a * (b * c) = (a * b) * c = a * b * c

In other words - grouping of operations has no meaning for the end result, there is no difference if we compose firstly a with b or b and c, the result should not change.

Basic algebra operations for numbers like +, * are associative. It is no difference if you do (1 + 2) + 3 or 1 + (2 + 3), the result will be the same. Semigroup is exactly about the notion of addition behavior, but semigroup is a concept abstracted from numbers, we can define it in other areas, in programming areas will have a form of types.

Note There are also many non-associative operations like exponentiation, subtraction or division

What it has to programming

In programming semigroups are visible very often, not only in number operations, but in other types also. I believe you were doing many times string concatenation or array concatenation, these operations are nominal examples of semigroups. We can say - every time you join two things together, for sure you have magma, and almost for sure you have semigroup too.

Humble examples

Pair (string, +) forms a semigroup in TypeScript

[TS]
const a = "Hello";
const c = " ";
const b = "World";

const concat1 = (a + b) + c;
const concat2 = a + (b + c);

// concat1 and concat2 are the same - "Hello World"

Pair (Array<any>, Array.prototype.concat) forms a semigroup in TypeScript.

[TS]
type S = Array<number>; // type contains all lists with number type inside

const a: S = [1, 2]; // a is member of S
const b: S = [3, 4]; // b is member of S

const c = a.concat(b); // c is member of S
c // [1,2,3,4]

That proofs that concat is an operation together with type Array<any> forms a magma, but does concat form a semigroup also?

const res1 = a.concat(b.concat(c)); // read us a `conc` ( b `conc` c)
const res2 = a.concat(b).concat(c);// read us (a `conc` b) `conc` c 
// all two results are [1,2,3,4,5,6]

Above is more like a test then the proof, but you need to believe me that concat with set List<any> forms a semigroup.

Note Take a second look at this Array example, we are using here typical for OOP implicit this passing. Isn't it a problem for pure mathematical concepts? No, not at all. We can represent mathematical abstractions also in OOP.

Type level semigroup

Algebra is visible not only at value level, but also at type level. Algebraic data types are great examples of such algebraic structures. As we have seen before in first article of the series - we have three kinds of algebraic data types - sums (+), products (*), exponentials (^). Exponential types are not associative, as exponential operation is not, that said - exponentiation does not form a semigroup.

[TS]
type Status = "Idle" | "Pending" | "Error" | "Success" // sum
type User = { name: string, lastname: string } // product

Sum type semigroup (or)

Let's take the first sum type and analyze how it is related to + operation and if it is a semigroup. Take a look that we can consider every element of the the sum type as element with value equal 1, if we consider then | as + we will have an expression 1 + 1 + 1 + 1 and its 4, exactly how many members we have of the type Status. That is to say | operation is a notion of addition algebra.

Numbers set, with + operation forms a semigroup, does sum type also forms a semigroup. Lets check that.

[TS]
type Status1 = ("Idle" | "Pending") | "Error" | "Success"
type Status2 = "Idle" | ("Pending" | "Error") | "Success"
type Status3 = "Idle" | "Pending" | ("Error" | "Success")

All above are evaluated to the same type, so we can say pair (any, |) forms a semigroup.

Note Not all usages of | form a sum type in TS, but all form a semigroup. For example type NotSum = 'a' | 'a' | 'b' is evaluated as 'a' | 'b', so the sum is 2, and should be 3.

Product type semigroup (and)

Product type is a notion of * in the type level, this is because the amount of possible elements of the type is multiplicated for every joined member. For example tuple (string, string) has string * string amount of elements. Lets take very small type like Boolean with two members True, False and create a pair type - (boolean, boolean).

[TS]
type PairBool = [boolean, boolean]; // tuple syntax in TypeScript
// all possible values/members:
[true,true]
[true,false]
[false, false]
[false, true]

We have four members, original type has two members, it means we have multiplicated the size of the type - (bool, bool) ≅ bool * bool ≅ 2 * 2. That is why we can say product type is a notion of multiplication at the type level.

Is it semigroup?

[TS]
type User1 = (Id & Name) & Lastname;
type User2 = Id & (Name & Lastname);
type User3 = {
  id: string,
  name: string,
  lastname: string
}

All types above are equal to Id & Name & Lastname, so yes pair (object, &) and tuple syntax (any, any, ...) and record syntax forms a semigroup.

Note OCaml syntax for product types is * symbol, for example string * int is a type of tuple (string, int)

Custom semigroup

Semigroups are interesting because are notion of joining elements, notion of addition, we can use this notion in our custom types. Lets create custom domain type - Money and add to it some algebraic semigroup notion. But wait, lets firstly create some naive implementation of adding money operations.

[ELM]
-- Naive implementation, not a semigroup, only magma
type Currency = PLN | USD | GBP
type Money = Money { amount: Float, currency: Currency}
addMoney : Money -> Money -> Money
addMoney (Money a) (Money b) = 
  if a.currency == b.currency then 
    Money {a | amount = a.amount + b.amount} 
  else 
    Money a

-- example values of type Money
m1 = Money {amount = 1.0, currency = PLN}
m2 = Money {amount = 2.0, currency = PLN}
m3 = Money {amount = 3.0, currency = GBP}

-- using
addMoney (addMoney m1 m2) m3

We have created a type - Money and closed operation over this type addMoney. Function addMoney adds amounts only if currency match, if not it does not add them, in this situation it returns the first argument.

Let's for a moment think about behavior of addMoney, if currency is the same it will add them, if not it will result by the left argument, and totally skip the right. Very implicit behavior, very not predictable one. Our naive implementation is not associative, how we group operations does matter. Such implementation is not predictable and risky to use, its very error prone as if you add firstly a with b and c after the result will be different from adding firstly b and c and a after. The fact that we don't have a semigroup has a meaning, such abstraction is just not the best one.

Lets try to make it better. Below the second try for the same operation.

-- [ELM]
-- implementation is a semigroup
type Currency
    = PLN
    | USD
    | GBP
type Money
    = Money { amount : Float, currency : Currency }

-- dictionary with rates to USD
rateToUSD : Dict Currency Float
rateToUSD = Dict.fromList [(PLN, 0.5), (GBP, 1.2), (USD, 1)]

addMoney : Money -> Money -> Money
addMoney (Money a) (Money b) =
    if a.currency == b.currency then
        Money { a | amount = a.amount + b.amount }
    else 
        let 
            aRate = Dict.get a.currency rateToUSD
            bRate = Dict.get b.currency rateToUSD
            amountA = a.amount * withDefault 1 aRate
            amountB = b.amount * withDefault 1 bRate
            finalAmount = (amountA + amountB) / (withDefault 1 aRate)
        in
            Money {a | amount = finalAmount }

Yes it is more code. The difference is that instead of skipping the situation where the currency does not match, we are recalculating the amount by the rate to USD currency, we add amounts as USD and recalculate it again to the original currency of the left argument. The new behavior means that we always will calculate, never skip it. Thanks to such behavior we got associativity of the addMoney operation, and abstraction is well more predictable.

Pair (Money, addMoney) forms a semigroup.

Haskell the Heaven of algebra

Haskell by its language features like ad-hoc polymorphism and parametric polymorphism is the best language for creating custom algebraic structures. Not surprising Haskell already has abstraction for semigroup, what is left for the developer is to implement instance of it. Continuing our example with Money I will recreate the same algebra in Haskell.

[Haskell]
import Data.Map
data Currency = USD | PLN | GBP deriving (Show, Eq, Ord)

usdRates = fromList [(PLN, 0.5), (GBP, 1.2), (USD, 1.0)]

data Money = Money {amount :: Float, currency :: Currency} deriving Show

instance Semigroup Money where
    Money am1 c1 <> Money am2 c2 = 
        if c1 == c2 then 
            Money (am1+am2) c1
        else
            let 
                amount1 = am1 * (findWithDefault 1 c1 usdRates)
                amount2 = am2 * (findWithDefault 1 c2 usdRates)
                finalUSDAmount = amount1 + amount2
            in Money (finalUSDAmount / (findWithDefault 1 c1 usdRates)) c1

-- values of type Money:
m1 = Money { amount = 1.0, currency = PLN }
m2 = Money { amount = 2.0, currency = GBP }
m3 = Money { amount = 3.0, currency = PLN }

In Haskell Semigroup typeclass has <> infix operator. Now we can simply use it.

[Haskell]
m1 <> m2 <> m3
(m1 <> m2) <> m3
m1 <> (m2 <> m3)

in comparison to Elm code:

[Elm]
addMoney (addMoney m1 m2) m3
addMoney m1 (addMoney m2 m3)

Difference is significant. As I said before, Haskell is a heaven for definition of own algebras. They look and feel as addition and multiplication on numbers, and because we made our operation associative, it also behaves like them.

Exercise for the reader take a look at the code you lately wrote, do you see semigroups there?

What next in the series

Great. We know what is Semigroup in next article we will go one step further into Monoid.

If you are interested in notifications about next articles please follow me on dev.to and twitter.