iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 24
0
Software Development

Functional Programming in Kotlin系列 第 24

Monad: a Monoid in the Category of EndoFunctors

終於要來解釋這句話了,距離上一次出現這句話時,我們都還不知道 Monoid, Category, Endofunctor 是什麼,現在除了 Endofunctor 之外,其他都介紹過了!不過忘了也沒關係,我們再來一個一個解釋吧。

Monoid

在之前有讓大家回去想,List 中的 Monoid 是長什麼樣子的,其中最簡單的當然是 + 當做是 op 啦。

// 右單位元
listOf(1, 2) + listOf() = lostOf(1, 2)
// 左單位元
listOf() + listOf(2, 3) = listOf(2, 3)
// 結合律
(listOf(1, 2) + listOf(2, 3)) + listOf (3, 4) = 
listOf(1, 2) + (listOf(2, 3) + listOf (3, 4))
listOf(1, 2, 2, 3, 3, 4)

還有什麼呢?以前不是也有學過聯集嗎?這個也可以是一個 Monoid 嗎?

// 右單位元
listOf(1, 2) union listOf() = lostOf(1, 2)
// 左單位元
listOf() union listOf(2, 3) = listOf(2, 3)
// 結合律
(listOf(1, 2) union listOf(2, 3)) union listOf(3, 4) = 
listOf(1, 2) union (listOf(2, 3) union listOf(3, 4)) =
listOf(1, 2, 3, 4)

但是 list 是有順序性的,[1, 2] 跟 [2, 1] 是不一樣的,而且元素是允許重複的,例如 [2, 2, 2] ,當 [2, 2, 2] 跟 empty list [] 做交集時,最後卻得到 [2] ,這跟就違反了左單位元或右單位元,所以這就不是 monoid 了。

但,我們不是有另外一個資料結構,Set 嗎?Set 搭配上聯集就形成了一個 Monoid

// 右單位元
setOf(1, 2) union setOf() = setOf(1, 2)
// 左單位元
setOf() union setOf(2, 3) = setOf(2, 3)
// 結合律
(setOf(1, 2) union setOf(2, 3)) union setOf(3, 4) = 
setOf(1, 2) union (setOf(2, 3) union setOf(3, 4)) =
setOf(1, 2, 3, 4)

Category

在介紹 Category theory 時,介紹了 Object 與 morphism 這兩個概念。對應到程式時,Object 就是 Type ,morphism 就是 function。 1 到多個 Object 以及 Object 之間的 morphism 會形成一個 Category,也就是說一個 Programming Category 裡可能會有一個到多個 Type 以及零到多個 function 來描述 Type 之間的轉換( 一個 Category 裡也可以沒有任何 morphism,只有 object )。像 List 是一個 Category,Maybe、Either 也都是 Category。

在我們要把問題範圍擴大時,還會有巢狀 Category,也就是CAT(Category of small Categories),在描述 Functor 時,就會用到 CAT,因為 Functor 指的是兩個 Category 之間的對應關係,這時候,原本的 Category 就會變成了另一個大的 Category 中的 Object,藉此,就可以使用 morphism(Functor)來描述 Category 跟 Category 之間的關係。

Endofunctor

Endofunctor 乍看之下是一個很抽象的單字,但是他的概念非常簡單,就只是一個 Category 的 morphism 又轉換為同一個 Category 罷了(好吧,這句話還是很抽象)。其實目前為止我們看的所有 Functor 都是 Endofunctor!有注意到嗎?List 經過 map 轉換後還是一個 List ,Maybe 經過轉後還是一個 Maybe,除非現在有一個轉換是從 Maybe 轉成 List,這樣的行為才不會被稱作是一個 Endofunctor。

Monoid in the Category of functions

現在我們都知道他們各代表什麼意思了,組合起來是什麼呢?讓我們再看一下原本的話是怎麼講的 - "Monad is just a Monoid in the Category of EndoFunctors"。首先讓我們從簡單的開始,如果把最後一個字換成 Types 呢?就會變成了 “Monoid in the Category of Types”,其實我們在之前的介紹中的 Monoid 就是已經作用在 Type 上了,所以這句話等於是在說廢話。接下來,如果替換成 function 呢?這句話就變成了 “Monoid in the Category of functions",從這開始就有挑戰多了。

fa: (A) -> B
fb: (B) -> C
fc: (C) -> D
// 右單位元
fa op ID_f = fa
// 左單位元
ID_F op fa = fa
// 結合律
(fa op fb) op fc = fa op (fb op fc) = fa op fb op fc

function 跟 funciton 之間的二元運算子要選什麼比較適合呢?其中第一個會想到的應該就是 compose 了,那如果這個二元運算子是 compose 的話,什麼樣的 function 會是單位元呢?當然就是一個什麼都不做,直接拿輸入來當作輸出的函式了:

// 1
fun <T> identity(value: T): T = value    
fun intIdentity(value: Int) = value      
fun stringIdentity(value: String) = value

infix fun <T, Q, R> ((Q) -> R).compose(anotherFun: (T) -> Q): (T) -> R {
    return { x: T ->
        this(anotherFun(x))
    }
}

fun identityTests() {
    // 2
    val addFun = { x: Int -> x + 1}
    val intToStringFun = { x: Int -> x.toString()}

    // 3
    val rightIDAddFun: (Int) -> Int = addFun compose ::intIdentity
    val leftIDAddFun : (Int) -> Int = ::intIdentity compose addFun

    val rightIDintToStringFun: (Int) -> String = intToStringFun compose ::intIdentity
    val leftIDintToStringFun: (Int) -> String = ::stringIdentity compose intToStringFun

    // 4
    println(rightIDAddFun(311))
    println(leftIDAddFun(311))
    println(rightIDintToStringFun(311))
    println(leftIDintToStringFun(311))
}

identityTests()

// output:
312
312
311
311
  1. 理想中的 identity ,但是 Kotlin 不允許我們在還沒有型別的時候去使用它,所以當 leftIDAddFun 直接使用 identity 的話會有 compile error ,在這邊做了一個妥協,做了兩個型別的 identity ,分別是 intIdentitystringIdentity
  2. 用來驗證 identity 的兩個 function ,型別分別是 (Int) → Int(Int) -> String ,根據 Monoid 的規則,在與 identity 做過 compose 之後,應該還是跟原來函式一模一樣。
  3. 與個別 function 組合起來的結果,要驗證的有兩個 function ,而且個別驗證左單位元與右單位元,所以總更產生出來了四個 function 。其中要符合 rightIDAddFun == leftIDAddFun == addFun 還有 rightIDintToStringFun == leftIDintToStringFun == intToStringFun
  4. 執行結果印出來,結果與原來的函式會是一樣的。

單位元看來是沒問題的,那結合律呢?這個....應該不需要再解釋了吧,第二篇就在做這件事了,他一定符合結合律!

Monoid in the Category of EndoFunctors

好了, function 推導完成了,接下來就是重頭戲 EndoFunctor 了!根據之前的定義,一個 Functor 作用在 Type a 可以寫成這樣:

f: a -> Ma

Functor 是 object 之間的對應關係,所以 Functor 可以寫成上述的 function,其中 M 就代表了“容器”。然後我們可以再加上另外兩個 Functor 的實作 g 跟 h :

f: a -> Ma
g: a -> Ma
h: a -> Ma

OK ,接下來再寫出 Monoid 的樣子,讓這三個 Functor 之間有著這樣的關係:

f op g = h

這就是一個 Monoid 基本的長相,前面也介紹過很多次了,接下來,將這三個 Functor 給展開:

(a -> Ma) op (a -> Ma) = a -> Ma

現在,做一點加工,調整一下括弧的位置:

a -> (Ma op (a -> Ma)) = a -> Ma

等式的左邊與右邊同時都是一個輸入值為 a 的函式,既然這兩個函式的輸入一樣,那也可以把他們一起拿掉,得到下面這個式子:

Ma op (a -> Ma) = Ma

快接近完成了,將 M 取代成隨便一個我們已知的 Functor ,這邊就直接取代為 List ,並且將 a 轉換成 Type T:

List<T> op (T) -> List<T> = List<T>

所以這個式子在說明著什麼呢?等式的左邊有兩個輸入,而這兩個輸入再經過 op 的運算,會得到一個型別為 List 的結果,所以在 Kotlin 中可以寫成這樣的函式:

fun op(a: List<T>, b: (T) -> List<T>): List<T> {
   ...
}

這...不就是...如果再把這函式放在 List 的類別中,省去第一個參數當作 this 就得到了.....!!!!

class List<T> {

	fun flatMap(transform: (T) -> List<T>): List<T> {
	   ...
	}
}

登登! flatMap 出現了! Monad is just a Monoid in the Category of EndoFunctors, what's the problem?

如果還是沒有很懂的話,極度推薦看下方 youtube 的影片,這是我看過最淺顯易懂的

References:

https://www.youtube.com/watch?v=ZhuHCtR3xq8

https://blog.softwaremill.com/monoid-in-the-category-of-endofunctors-b85bab43587b


上一篇
Natural transformation
下一篇
Bind, Return and Monad laws
系列文
Functional Programming in Kotlin30

尚未有邦友留言

立即登入留言