iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 14
0

本章重點

  • Semigroup 為 可以加起來,而且具有結合律 ,必須實作 concat 。
  • Monoid 為 具有單位元素的 Semigroup ,必須實作 empty ,單位元素舉例來說,就是加法中的 0 。
  • Group 為 具有反元素的 Group ,必須實作 invert ,反元素舉例來說,就是加法中的 -1 * 元素。

Semigroup

Semigroup 中文翻譯為 半群
聽起來也很恐怖,不過你可以把當作 可以加起來,而且具有結合律
Semigroup 的 instance 必須實作 concat ,而 concat 還必須遵守以下規則︰

concat :: Semigroup a => a ~> a -> a

1. a.concat(b).concat(c) is equivalent to a.concat(b.concat(c)) (associativity)

那個規則就是結合律, Semigroup 的 instance 也相當常見。

class Sum{
    constructor(a){
        this._a = a
    }
    concat(other){
        const a = this._a
        return new Sum(a + other._a)
    }
    toString(){
        const a = this._a
        return `Sum(${a})`
    }
}

const s1 = new Sum(1)
const s2 = new Sum(2)
const s3 = new Sum(3)

console.log(
    s1.concat(s2).concat(s3), // Sum(6)
    s1.concat(s2.concat(s3)) // Sum(6)
)
class All{
    constructor(a){
        this._a = a
    }
    concat(other){
        const a = this._a
        return new All(a && other._a)
    }
    toString(){
        const a = this._a
        return `All(${a})`
    }
}

const a1 = new All(true)
const a2 = new All(true)
const a3 = new All(false)

console.log(
    a1.concat(a2).concat(a3), // All(false)
    a1.concat(a2.concat(a3)) // All(false)
)

class First{
    constructor(a){
        this._a = a
    }
    concat(other){
        const a = this._a
        return new First(a)
    }
    toString(){
        const a = this._a
        return `First(${a})`
    }
}

const f1 = new First(1)
const f2 = new First(2)
const f3 = new First(3)

console.log(
    f1.concat(f2).concat(f3), // First(1)
    f1.concat(f2.concat(f3)) // First(1)
)

Sum 、 All 、 First 都是 Semigroup 的 instance ,直接看程式碼應該都能明白。

Monoid

Monoid 的中文翻譯為 么群 ,又做 3 / 4 群
Monoid 即為 擁有 的 Semigropup ,
Monoid 繼承自 Semigroup ,所以是 Monid 的 instance 之前,必須是 Semigroup 的 instance 。
Monoid 的 instance 必須實作 empty ,而 empty 還必須遵守以下規則︰

empty :: Monoid m => () -> m

1. m.concat(M.empty()) is equivalent to m (right identity)
2. M.empty().concat(m) is equivalent to m (left identity)

正確的說法是 單位元素任何元素單位元素 運算後都不會改變,
在加法中是 0 ,任何元素 + 0 ,不會改變,
在乘法中是 1 ,任何元素 * 1 ,不會改變,
在 All 是 true ,任何元素 && true ,不會改變,
在 Array 是 [] ,任何元素 concat [] ,不會改變。

Sum.empty = _ => new Sum(0)

const s1 = new Sum(1)

console.log(
    Sum.empty().concat(s1), // Sum(1)
    s1.concat(Sum.empty()) // Sum(1)
)
All.empty = _ => new All(true)

const a1 = new All(true)
const a2 = new All(false)

console.log(
    All.empty().concat(a1), // All(true)
    a1.concat(All.empty()) // All(true)
)

console.log(
    All.empty().concat(a2), // All(false)
    a2.concat(All.empty()) // All(false)
)

但我們無法找到 First 的單位元素,所以 First 並不是 Monoid 。

Group

Group 的中文翻譯為
Group 即為具有 反元素 的 Moniod 。
Group 繼承自 Moniod ,所以是 Group 的 instance 之前,必須是 Moniod 的 instance 。
Group 的 instance 必須實作 invert ,而 invert 還必須遵守以下規則︰

invert :: Group g => g ~> () -> g

1. g.concat(g.invert()) is equivalent to g.constructor.empty() (right inverse)
2. g.invert().concat(g) is equivalent to g.constructor.empty() (left inverse)

反元素 為運算後為單位元素,
舉例來說, 18 的反元素即為 -18 。

Sum.prototype.invert = function(){
    const a = this._a
    return new Sum(a * -1)
}

const s1 = new Sum(1)

console.log(
    s1.concat(s1.invert()), // Sum(0)
    s1.invert().concat(s1) // Sum(0)
)

但我們無法找到 All 的單位元素,所以 All 並不是 Group 。

簡單的應用

其實只要任何 Type 在結合的時候,就是 Semigroup 的應用,假設我們有一個遊戲。

const concat = (a, b) => a.concat(b)

class Player {
	constructor({ name, isPaid, points, friends }) {
		this._name = new First(name)
		this._isPaid = new All(isPaid)
		this._points = new Sum(points)
		this._friends = friends
	}
	concat(other) {
		return new Player({
			name: concat(this._name, other._name),
			isPaid: concat(this._isPaid, other._isPaid),
			points: concat(this._points, other._points),
			friends: concat(this._friends, other._friends)
		})
	}
}

如此就簡單的定義好了 Player.concat 。

後記

參考資料


上一篇
Setoid 、 Ord
系列文
30天快樂學習 Functional Programming14

1 則留言

0
LeeBoy
iT邦新手 4 級 ‧ 2017-12-29 11:39:52

醒醒~

我要留言

立即登入留言