Category theory

12th鐵人賽 kotlin functional programming

hungyanbin

團隊Kotlin 鐵人陣

2020-09-19 01:03:41

1500 瀏覽

分享至

在本文開始之前先打個預防針，我學習 Category theory 的時間其實沒有多長，所以如果以下或之後的內容有誤，或是有不完善的地方請各位多多包含。另外為了避免傳達不正確的知識，本篇的內容將會與這本書（Category Theory for Programmer）十分雷同，基本上就是做翻譯跟加上我自己的理解，那，讓我們開始吧！

Arrows as Functions

Category theory 組成的元素其實十分的簡單，就只有 Object 跟 Arrow 這兩種元素。在表示上，Object 會被畫成一個圓或是點，而 Arrow 呢...就是箭頭。這些 Arrow 是可以組合（Composition）起來的，假設現在有一個 Arrow 從 Object A 指到 Object B，同時有另外一個 Arrow 從 Object B 指到 Object C，那麼就會有一個組合的 Arrow 從 Object A 指到 Object C。

這些聽起來太抽象了嗎？這些 Arrow 也被稱做 morphism，同時也可以當他們為函式。如果現在有一個函式 f 他的參數型別為 A 回傳型別是 B，有另一個函式 g 的參數型別為 B 回傳型別為 C 時，你就可以組合這兩個函式 h = g。f ，得到一個參數型別為 A 回傳型別是 C 的函式。

而在 Kotlin 中組合的觀念在第二篇也有介紹過了，下面這段程式碼讓大家回想一下：

val addOne: (Int) -> Int = { x: Int -> x + 1}
val timesTwo: (Int) -> Int = { x: Int -> x * 2}
val composeFun: (Int) -> Int = { x: Int -> addOne(timesTwo(x)) }

Properties of Composition

Category 內的組合有兩個非常重要的特性，這是任何的 Category 都必備的。

結合律（Associativity）- 假如有三個 morphism f, g, h ，而且他們都可以被組合起來（他們的 object 是可以對起來的），就一定會符合以下條件：

h。( g。f ) = ( h。 g )。f = h。g。f

在 Kotlin 中則是：
```
val h: (C) -> D = { ... }
val g: (B) -> C = { ... }
val f: (A) -> B = { ... }

fun testAccociativity(a: A) {
	assertTrue((h compose (g compose f))(a) == ((h compose g) compose f)(a))
	assertTrue(((h compose g) compose f)(a) == (h compose g compose f)(a))
}
```
對於任何型別 A, B, C, D 以及輸入 a ，這個測試一定會通過。
單位元（Identity）- 對於任一個 object A ，會有非常多個 Arrow ，有的會指向其他 object ，有個會指向自己。其中一定會有一條 Arrow 會是組合的基本單位，而這條 Arrow 會指向 object 自己，形成一個迴圈。而這個基本單位也稱為 identity on A，同時單位元也符合以下條件(f 是一個從 A 到 B 的 morphism)：

f。(identity on A) = f

(identity on B)。f = f

單位元有點太抽象？沒關係一樣來看 Kotlin 是長什麼樣子的吧
```
val f: (Int) -> String = { ... }
val idInt: (Int) -> Int = { x: Int -> x }
val idString: (String) -> String = { x: String -> x }
// 非 lambda 版本
fun <T> identity(x: T) = x

val composeRight: (Int) -> String = f compose idInt
val composeLeft: (Int) -> String = idString compose f
// composeRight, composeLeft, f 都是等價的 function
```
這時候你可能會想問一個問題，為什麼需要 Identity function？為什麼需要一個完全沒作用的 function？反過來可以想想，為什麼我們需要數字零？零是一個代表“無”狀態的值，古羅馬沒有零這個概念卻還是可以建造宏偉的道路，那零對我們還說是什麼意義呢？

在使用符號表示時，零跟單位元都是非常有用的，這也是為什麼羅馬不擅長於代數（這是原書的觀點喔，不同意請別鞭我ＸＤ）。另外在我們寫程式時，identity function 對於 higher order function 來說，可以是個很方便的參數、或是回傳值。

如果還是沒感覺，以下再列出幾個例子：加法的 identity 是 0 ，乘法的 identity 是 1，矩陣運算的 identity 呢？正好叫做單位矩陣不是嗎？

// 加法的 identity 是 0，同時加法也符合結合律，
// 所以把加法當成是 morphism 的話，就可以形成一個 Category
x + 0 = x
0 + x = x

// 乘法的 identity，同理，也會形成一個 Category。
x * 1 = x
1 * x = x

組合（composition）的重要性

從以前到現在，程式演進了很多次，從組合語言開始，新的概念一直不斷的被提出、創新，像是micro、函式、物件、設計模式、架構等等，為什麼要有這些概念？因為我們大腦的空間是有限的，無法裝進太多東西，如果把 linux 的所有程式碼都展開來變成一個大 function 的話應該沒人讀得懂。所以我們需要把大問題分解成一個個小問題，如果還不夠小，就繼續切割下去。而這些小小問題最終要被組合起來一起解決大問題。

大家習慣使用的 UML ，不也是一堆圈圈跟箭頭組合起來的嗎？跟 Category theory 有點相似不是嗎？

這樣分解又組合的過程不就很解數學題目時很像嗎？這證明了我們人腦在解決問題時，最終還是會使用這種方式解決問題，而這一切都有一個類似的模式。所以有人就把這模式統整起來了，這個模式就是 - Category theory 。在 functional programming 中借用了 Category theory 的很多理論，幫忙用各種方式來分解問題與組合問題，而且這是非常接近我們習慣的解決問題方式，只是這些理論實在太過抽象，讓人望之卻步。不過也不要太過氣餒，實際會用在寫程式中的理論並沒有想像中的這麼困難，甚至只要了解一小部分就很夠用了，下一篇將來介紹一個 Category theoey 在程式中非常常見的概念 - Functor。