iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 13
0

本章重點

  • Setoid 即為 Eq ,可比較的,Setoid 的 intstance 必須實作 equals
  • Ord 為可排序的, Ord 的 intstance 必須實作 lte, lte 為 less than or equals to 的縮寫。

Setoid

其實 Setoid 這個名子看起來真的很恐怖。

oid 字根...的東西 , Setoid 想必與 Set 有關。 Set 具有 互異性 ,所以裡面的元素必須能互相比較, Typeclass 通常叫做 Eq 。

Setoid 的 intstance 必須實作 equals ,而 equals 還必須遵守以下規則︰

~> 為 a instance 底下的方法
equals :: Setoid a => a ~> a -> Boolean

1. a.equals(a) === true (reflexivity)
2. a.equals(b) === b.equals(a) (symmetry)
3. if a.equals(b) and b.equals(c), then a.equals(c) (transitivity)

幾乎所有東西都是 Setoid 的 instance ,規則也非常簡單︰

  1. a == a 。
  2. 如果 a == b ,則 b == a 。
  3. 如果 a == b 且 b == c ,則 a == c 。

這三條規則都是非常直覺的。

Ord

而 Ord 也很平易近人,Ord 即為可排序的, Typeclass 通常同名 Ord 。
在族譜中可以看到, Ord 在 Setoid 底下,這表示 Ord 必須為 Setoid 的 instance 。

Ord 的 instance 必須實作 lte , 這是 less than or equals to 的縮寫, lte 規則如下︰

lte :: Ord a => a ~> a -> Boolean

1. a.lte(b) or b.lte(a) (totality)
2. if a.lte(b) and b.lte(a), then a.equals(b) (antisymmetry)
3. if a.lte(b) and b.lte(c), then a.lte(c) (transitivity)

Ord 跟 Setoid 一樣常見,幾乎所有東西都是 Ord 的 instance,規則比 Setoid 複雜一點點。

  1. a <= b 或是 b <= a 。(不是 <= 就是 >= 嘛)
  2. 如果 a <= b 且 b <= a ,則 a == b 。(兩個都成立當然就是 a == b)
  3. 如果 a <= b 且 b <= c ,則 a <= c 。(遞移律)

稍微動腦一下,這個三條規則也是非常直覺的。

實作 Set

Set 只需要 Setoid 就能夠實作,但為了效能,底層通常為 Binary Search Tree ,所以型別會要求為 Ord 。

首先我們需要一個自訂的 === ,以及一個自訂的 Array.includes

curry 來自於 Higher-order Function = { Curry } 與 Type Signature ,也可以在 gist 找到它。

// equals :: Setoid a => a -> a -> Bool
const equals = curry((a, b) => {
	// 如果 有實作 equals
	// 就使用 equals
    if (a.equals !== undefined) {
		return a.equals(b)
	} else {
		return a === b
	}
})

// any 傳入一個 Function
// 若其中一個為 f(a) ,則回傳 true
// any :: Setoid a => (a -> Bool) -> [a] -> Boolean
const any = curry((f, array) =>
	 array.reduce(
		(acc, a) => acc || f(a),
		false
	)
)

// includes :: Setoid a => a -> [a] -> Boolean
const includes = curry((a, array) => any(equals(a), array))
class Set {
	constructor(array = []) {
		this._array = array.reduce((acc, el) => {
			// 判斷元素是否重複
			if (includes(el, acc)) {
				return acc
			} else {
				return [...acc, el]
			}
		}, [])
	}
	insert(a) {
		if (this.has(a)) {
			return this
		} else {
			const array = this._array
			return new Set([...array, a])
		}
	}
	has(a) {
        const array = this._array
		return includes(a, array)
	}
	toString() {
		const array = this._array
		return `Set(${array.join(', ')})`
	}
}

const s0 = new Set([1, 2, 3, 4])
const s1 = new Set([1, 2, 2, 3])

console.log(
    s0, // Set(1, 2, 3, 4)
    s1 // Set(1, 2, 3)
)

完美,讓我們試試 Setoid 的 instance 。

// data Test a = AlwaysEq a 
class AlwaysEq {
	constructor(a) {
		this._a = a
	}
	equals(b) {
		return true
	}
	toString() {
		const a = this._a
		return `AlwaysEq(${a})`
	}
}

class NormalObj {
    constructor(a) {
		this._a = a
	}
    toString() {
		const a = this._a
		return `NormalObj(${a})`
	}
}

const s0 = new Set([new AlwaysEq(0), new AlwaysEq(1)])
const s1 = new Set([new NormalObj(0), new NormalObj(1)])

console.log(
    s0, // Set(AlwaysEq(0))
    s1 // Set(NormalObj(0), NormalObj(1))
)

礙於 Syntax 限制,讓程式碼變得稍微冗長,
我相信這篇讓人有種「這些東西不是常識嗎?」的感覺,
不過我必須說︰「對,這是常識呀,好的抽象化就是『直觀、普遍存在』」。

後記

參考資料


上一篇
The Way to Fantasy Land
下一篇
Semigroup 、 Monoid 、 Group
系列文
30天快樂學習 Functional Programming14

2 則留言

0
Wolke
iT邦新手 3 級 ‧ 2017-12-27 09:16:36

應該是睡死了

阿志 iT邦新手 5 級‧ 2017-12-27 10:42:15 檢舉

好累QQ

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

醒醒啊,期待你補文

我要留言

立即登入留言