Monoid Algebraic structure

Monoid，是在一個 Semigroup 中存在一個 identity element。

identity element

假設我們有個集合 $S$ ，而一個 identity element 必須滿足以下條件：

$\exists e\in S, \forall a\in S\ \ a \bullet e = a\ \rm{and} \ e\bullet a=a$

白話文解釋就是，在 $S$ 中存在一個 $e$ ，使得對於所有 $S$ 中的每個元素 $a$ ，等式 $a \bullet e = a$ 與 $e\bullet a=a$ 兩者成立。

實際案例就是相加跟相乘，相加的 identity element 是 $0$ ，相乘則是 $1$ 。

$0 + 47 = 47\ and\ 47 + 0 =47$

$1 * 34 = 34\ and\ 34 * 1 =47$

Monoid

到目前為止我們已經整理了三樣規則

Magma：嘗試定義一個集合 $M$ 的二元運算， $(M,\bullet)$

$a,b\in M \Longrightarrow a \bullet b \in M$

Semigroup：以 Magma 為基礎添加一條結合律的規則， $(S,\bullet)$

$x,y,z\in S\Longrightarrow(x\bullet y)\bullet z = x\bullet (y\bullet z)$

Monoid：從 Semigroup 集合 $S$ 中尋找是否存在 identity element， $(M,\bullet)$

$\exists e\in M, \forall a\in M\ \ a \bullet e = a\ \rm{and} \ e\bullet a=a$

fp-ts interface 定義如下

interface Monoid<A> extends Semigroup<A> {
  readonly empty: A
}

實例

我們依然可以定義一個數字加法

import { Monoid } from 'fp-ts/Monoid';

const MagmaAdd: Monoid<number> = {
    concat: (first, second) => first + second,
    empty: 0,
};

我們再度把 Coord 例子拿出來，思考一下在這個結構跟運算是否存在一個 identity element

type Coord = {
    x:number;
    y:number;
}

const MagmaCoordAdd: Monoid<Coord> = {
    concat: (first, second) => ({ x: first.x + second.x, y: first.y + second.y }),
    empty: // identity element ?
};

這裡有一個關鍵特徵，就是 x 跟 y 都同為加法運算，並且我們已經知道加法的 identity element 為 0，這時我們可以大概認定兩個 Monoid 的組合還會是一個 Monoid (實際還是要經過驗證才能證明這件事)，這時我們可以把 Coord 的 identity element 補上：

type Coord = {
    x:number;
    y:number;
}

const MagmaCoordAdd: Monoid<Coord> = {
    concat: (first, second) => ({ x: first.x + second.x, y: first.y + second.y }),
    empty: { x: 0, y: 0 }
};

而另一個有趣的例子是某種函式的也能成為 Monoid

import { flow, identity } from 'fp-ts/function';
import { Endomorphism } from 'fp-ts/Endomorphism';

export const getEndomorphismMonoid = <A>(): Monoid<Endomorphism<A>> => ({
    concat: flow,
    empty: identity,
});