iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 23
0
Software Development

Functional Programming in Kotlin系列 第 23

Natural transformation

Definition

今天又回到 Category theory 的領域了,從一開始提到的 object 之間的 morphism - function,到 Category 之間的 morphism ,也就是 Functor,到這裡,又有另外一個 morphism 了,就是今天要介紹的 Functor 之間的 morphism ,也就是 Nature transformation !

關於 Nature transformation,如果先不管理論中的 category theory ,單純以程式所認識的 Functor 來說,就是大家都很熟悉的 List、Maybe、Observable ,對吧。所以說,剛剛提到的, Functor 之間的 morphism ,就是在說這他們轉換的函式嗎?事實上正是如此,實際的範例會在後面提到。

先來複習一下 Functor 吧,所謂的 Functor 指的是 category 之間的 morphism ,但是在兩個 category 之間的 Functor 可以不只一個,可以在同時存在兩個以上的 Functor F , G 如下:

https://user-images.githubusercontent.com/7949400/94885320-793a2980-04a2-11eb-9826-b04e2e628dd8.png

在右邊的 category 中,同時存在著兩個 object:Fa, Ga 。他們各是 Functor F 與 Functor G 從左邊的 category map 過來的。舉例來說,如果這兩個 category 都是 List<Int> 的話,Functor F 的 map 可能是 map { x -> x + 1} ,Functor G 的 map 可能是 map { x -> x * 2} 。有了這兩個 morphism ,自然而然的,就會存在著一個 morphism alphaA 從 Fa 指到 Ga。

這個 alphaA 就是一開始所說的 Natural transformation,寫成數學函式的話,就是 F 。 alphA = G ,剛好就是 F 跟 G 兩個 Functor 之間的轉換。了解了最基本的 Natural transformation 怎麼表示的之後,接下來再把問題變得複雜一點,如果左邊有另外一個 object b ,相對應的,也會在右邊有兩個 Object Fb 與 Gb ,也會存在一個 morphism alphaB 從 Fb 指到 Gb。相信這邊這麼多代號有點難想像,如果延續剛剛 List<Int> 的例子, a 可能是 list [3] ,b 可能是 list [4],所以 Fa, Ga, Fb, Fb 就會是 [4](3 + 1), [6](3 * 2), [5](4 + 1), [8](4 * 2)。

https://user-images.githubusercontent.com/7949400/94885378-9f5fc980-04a2-11eb-98fd-37842992d4a4.png

最後再補上我們之前提到過的 function 的對應關係,如果 f 是一個從 a 到 b 的 function,那麼在右邊的 category 中也會有相對應的 Ff 與 Gf(綠色)。

https://user-images.githubusercontent.com/7949400/94885503-ef3e9080-04a2-11eb-88f4-6779ade71846.png

這時候就會發現綠色與紅色的箭頭形成了一個四邊形,有兩條不一樣的路從 Fa 連結到了 Gb ,其中一條是 Ff 與 alphaB ,另一條是 alphaA 與 Gf 。於是就產生了下面這條等式:

AlphaB。Ff = Gf。AlphaA

而這就是 Natural Transformation 中一個重要的等式,

Code sample

那 Natural Transformation (上面的 Fa → Ga, Fb → Gb)在程式中又是怎樣呈現的呢?讓我來看看下面這個例子:

class LinkedList<T> {
    fun head(): Maybe<T>
}

一個 LinkedList 可能是空的,所以拿第一個 item 時不一定會拿得到東西,所以我們可以套用之前學過的 Maybe ,來實作一個 pure and total function ,不會因為沒有第一個 item 而噴出 Exception。

這個 head function 可以寫成是這樣的函式: (LinkedList<T>) -> Maybe<T> , 然而LinkedList 是一個 Functor ,而 Maybe 也是一個 Functor ,那這不就是 Natural transformation 嗎?接下來,我們試試看推導上面出現過的等式。

首先,試看看只有一個 item 的 List :

// 推導   AlphaB。Ff
//
// F     -> LinkedList
// f     -> x + 1
// Alpha -> head
val a = 1
// [1]
val Fa: LinkedList<Int> = linkedListOf(1)
// [2]
val Ffa: LinkedList<Int> = Fa.map { it + 1} 
// Some(2)
val alphaB_Ffa: Maybe<Int> = Ffa.head()

在左邊的等式中,推導出了 Some(2) ,那右邊呢?

// 推導   Gf。AlphaA
//
// G      -> Maybe
// f      -> x + 1
// Alpha  -> head
val a = 1
// [1]
val Fa: LinkedList<Int> = linkedListOf(1)
// Some(1)
val alphaA: Maybe<Int> = Fa.head()
// Some(2)
val Gf_alphaA: Maybe<Int> = alphaA.map{ it + 1}

一樣也是 Some(2) !而且如果我們把 f 這個函式替換成任意的 pure function 也成立。 所以在只有一個 item 的情況下 Natural transformation 的等式是成立的。那如果是有多個 item 的 LinkedList 呢?由於 head 只會拿第一個 item,不會因為 LinkedList 後面有多少不一樣的 item 而改變結果。所以上述這個等式對於多個 item 也是成立的。

接下來是 item 數量為 0 的情況:

// 推導   AlphaB。Ff
//
// F     -> LinkedList
// f     -> x + 1
// Alpha -> head
// []
val Fa: LinkedList<Int> = linkedListOf()
// []
val Ffa: LinkedList<Int> = Fa.map { it + 1} 
// None
val alphaB_Ffa: Maybe<Int> = Ffa.head()

得到了 None ,那等式的右邊呢?

// 推導   Gf。AlphaA
//
// G      -> Maybe
// f      -> x + 1
// Alpha  -> head
// []
val Fa: LinkedList<Int> = linkedListOf()
// None
val alphaA: Maybe<Int> = Fa.head()
// None
val Gf_alphaA: Maybe<Int> = alphaA.map{ it + 1}

也是 None ,所以得證, head 是一個 Natural transformation!

So what?

這邊證明的這麼辛苦是為了什麼?對我來說是一個更多的啟發,在一開始接觸 FP 的時候,我被巢狀的泛型給嚇傻了,如果現在有一個 Result ,可能被 Try 包起來,外面可能要再包一個 List,然後還有可能最外面還會再有一個 Observable 像這樣: Observable<List<Try<Result>>> ,多可怕啊!光是寫這介面就累死了。但是在知道了 Natural transformation 之後,才發現原來一直都存在著另外一個選項:就是替換容器,像上面這種案例,搞不好只需要 Obserable<Result> 就夠了!跟本就不需要弄這麼多層搞死自己,因為通常在解決問題時,我們通常需要的是一個簡單的結構就足以解決問題了,所以盡量在可以轉換“容器”時就儘早轉換,不是使用了一個“容器”就一定要硬幹到底,記住這樣的準則,一定有助於日常開發的!

其他的 Natural transformation 的例子還有, last , find , length 等等,幾乎任何 Functor 之間的轉換都算是 Natural transformation!

小結

在我從影片中學習 Category theory 時,影片中的講者說明了 Natural transformation 在 Category theory 中是一個非常重要的概念,甚至連 Functor 是為了這個而存在的,雖然目前我還沒有感受到這樣的重要性,但還是給了我其他的啟發。好了,看了這麼多 Category Theory 的概念之後,接下來下三篇就是最後,最讓人期待要介紹的東西了 - Monad 。究竟他是什麼東西,能讓許許多多的人寫文章介紹,卻還是怎麼看也看不懂呢?希望在我介紹這麼多 Category Theory 的概念之後,能讓大家至少理解 Monad 80% 的內容,包含了有名的那句話,以及讓人看了就想放棄的 Monad Laws (下圖)。

https://user-images.githubusercontent.com/7949400/94886421-b94edb80-04a5-11eb-97cc-d81cb087218b.png

Reference : https://www.youtube.com/watch?v=2LJC-XD5Ffo


上一篇
Type system and nullability
下一篇
Monad: a Monoid in the Category of EndoFunctors
系列文
Functional Programming in Kotlin30

尚未有邦友留言

立即登入留言