iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 10
0
Software Development

Functional Programming in Kotlin系列 第 10

Category theory

在本文開始之前先打個預防針,我學習 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。

https://user-images.githubusercontent.com/7949400/93623322-23c93b80-fa11-11ea-9a75-1ff404a1eeae.png

這些聽起來太抽象了嗎?這些 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 都必備的。

  1. 結合律(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 ,這個測試一定會通過。

  2. 單位元(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?反過來可以想想,為什麼我們需要數字零?零是一個代表“無”狀態的值,古羅馬沒有零這個概念卻還是可以建造宏偉的道路,那零對我們還說是什麼意義呢?

    https://user-images.githubusercontent.com/7949400/93623351-2f1c6700-fa11-11ea-858b-ae8dabc9c662.png

在使用符號表示時,零跟單位元都是非常有用的,這也是為什麼羅馬不擅長於代數(這是原書的觀點喔,不同意請別鞭我XD)。另外在我們寫程式時,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。


上一篇
More FlatMap : List and Try
下一篇
Introduce Functor
系列文
Functional Programming in Kotlin30

尚未有邦友留言

立即登入留言