Semigroup Algebraic structure

Typescript Functional Programming fp-ts algebra

Semigroup，為代數結構的一種，也是 Magma 的延伸，從 Magma 添加一條結合律(Associative Property) 的規則。

結合律

首先我們定義一個 Magma 為 (M, ∙)(M,\ \bullet)，從 MM 隨機取出三個元素(可以超過三個) x, y, zx,\ y,\ z，將其作運算，而運算的優先度有以下幾種變化：

  1. ((x∙y)∙z)((x\bullet y)\bullet z)
  2. (x∙(y∙z))(x\bullet (y\bullet z))
  3. x∙y∙zx\bullet y\bullet z

x∙y∙zx\bullet y\bullet z 這個 case 看起來是合理的，但在 Magma 中的定義的是二元運算(Binary operation)，所以不會討論這個 case。

而結合律必須滿足 ((x∙y)∙z)=(x∙(y∙z))((x\bullet y)\bullet z) = (x\bullet (y\bullet z)) 也就是說不管元素有多少，執行計算優先度如何換，最終都不影響結果，最常見的就是加法跟乘法：

((1+2)+3)=(1+(2+3))=6((1+2)+3) = (1+(2+3)) = 6

((1∗2)∗3)=(1∗(2∗3))=6((1*2)*3) = (1*(2*3)) = 6

在 fp-ts interface 為

interface Semigroup<A> extends Magma<A> {}

竟然就是 Magma！為什麼呢？ 因為以型別來說 TS 無法知道你的運算（concat）到底有沒有遵守結合律，這是我們自己要去證明或確定的，以這裡來說只是給我們使用時識別這個 type 運算時需不需要遵守結合律。

我們用先前 Coord Magma 的例子來看有沒有遵守結合律：

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

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

const coordA: Coord = { x: 2, y: 5 };
const coordB: Coord = { x: 4, y: 8 };
const coordC: Coord = { x: 1, y: 7 };

// ((a + b) + c)
const res1 = MagmaCoordAdd.concat(MagmaCoordAdd.concat(coordA, coordB), coordC);
// (a + (b + c))
const res2 = MagmaCoordAdd.concat(coordA, MagmaCoordAdd.concat(coordB, coordC));

res1 === res2 // true

自己嘗試過後是有的，所以我們可以說 type Coord 相加是一個 Semigroup。

其他案例

還有些在程式裡擁有 Semigroup 特性的 Magma，像是字串相加、&&、||。

('a' + 'b') + 'c' === 'a' + ('b' + 'c')
(true && false) && true === true && (false && true)
(true || false) || false === true || (false || false)

而在這篇文章中提了兩個有趣的案例，可以自己實驗看看

import { Semigroup } from 'fp-ts/Semigroup'

/** Always return the first argument */
const first = <A>(): Semigroup<A> => ({
  concat: (first, _second) => first
})

import { Semigroup } from 'fp-ts/Semigroup'

/** Always return the second argument */
const last = <A>(): Semigroup<A> => ({
  concat: (_first, second) => second
})

參考資訊