iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 25
0
Software Development

Functional Programming in Kotlin系列 第 25

Bind, Return and Monad laws

先複習一下上一篇的內容,一個 Monad,就是一種 Moniod ,而且中間有個特別的 operator ,而他,剛好就是我們熟悉的 flatMap 如下:

Ma op (a -> Ma) = Ma

但是正常的來說,我們不會想要只有一個 Type a ,而是有另一個 Type b 來讓這個函式更有彈性:

Ma op (a -> Mb) = Mb

這個 op 的輸入是 Ma 跟 (a → Mb) 回傳值是一個 Mb,再來將它表示成一個函式:

f_op = (Ma, (a -> Mb)) -> Mb
// currying
f_op = Ma -> (a -> Mb) -> Mb
     = bind

最後再經過柯里化,得到了一個式子,而這個式子在 Monad 中有一個名字,他就是 bind

所謂的 bind 就是 Ma -> (a -> Mb) -> Mb

既然我們把 op 換個名字叫做 bind 了,那我們試試看使用 bind 來寫出 Moniod 的左單位元、右單位元、以及結合律。

// 左單位元
Id bind (a -> Mb) = a -> Mb
// 右單位元
(a -> Mb) bind Id = a -> Mb  
// 結合律
((a -> Mb) bind (b -> Mc)) bind (c -> Md) = (a -> Mb) bind ((b -> Mc) bind (c -> Md))

但是這三條式子還不完整,目前還不知道這個單位元(Id)會是什麼,根據 Monad 的定義, bind 的左右邊都是一個 Functor,那怎樣的 Functor 才會符合左單位元與右單位元這兩個規則呢?根據我們對於程式中對於型別的理解,應該不難推斷出這是一個泛型的函式,一個不管輸入為什麼類型,輸出就會是一個“容器”再加上該類型的函式,像是下面這幾個:

val a = 1
val ListMonadId = listOf(a)
val MaybeMonadId = Maybe.just(a)

其中,這個 Id 又被稱作 return ,如果 Monad 是一個介面的話,單位元就可以寫成:

// 其中 t 為任意類型
interface Monad<T> {
    fun <T> return(input: T): F<T>
}
// return in List => listOf
interface List<T>: Monad<T> {
    fun <T> return(input: T) = listOf(input)
}

所以我們現在有 bind 跟 return 了,有了這些就可以組成三條規則:

f: (a -> Mb)
g: (b -> Mc)
h: (c -> Md)

// 左單位元
(a -> return(a)) bind f = f
// 右單位元
f bind (a -> return(a)) = f
// 結合律
(f bind g) bind h = f bind (g bind h) = f bind g bind h

而這三條規則就是所謂的 Monad laws ,跟網路看到的 Monad laws 還是有點不一樣。根據我的理解,這是因為網路上常常看到的 Monad laws 是以 haskell 這語言為出發點寫出來的,有做過一些轉化與化簡,但基本的核心精神是一樣的,其精神就是要符合 Category theory 中的單位元與結合律。

Monad laws in Programming

這邊還是以最簡單的 Maybe 來做示範,Maybe 的 returnbind 是什麼呢?其實之前都實做過了,就是 justflatMap

 sealed class Maybe<T>{
    class Some<T>(val value: T): Maybe<T>()
    class None<T> : Maybe<T>()

		fun <R> flatMap(function: (T) -> Maybe<R>): Maybe<R> {
		    return when(this) {
		        is Some -> function(this.value)
		        else -> None()
		    }
		}

		companion object {
		    fun <T> just(value: T?): Maybe<T> {
		        return if (value == null) {
		            None()
		        } else {
		            Some(value)
		        }
		    }
		}
}

讓我們來測試左單位元的規則:

//  try to verify: (a -> return(a)) bind f = f
fun testLeftIdentity() {
    // f: toOdd
    val toOdd: (Int) -> Maybe<Int> = { x ->
        when(x%2) {
            0 -> Maybe.None()
            else -> Maybe.Some(x)
        }
    }
    val input = 1

    // left hand side: (a -> return(a)) bind f
    val afterId = Maybe.just(input)
    val afterFlatMap = afterId.flatMap(toOdd)
    // right hand side: f
    val onlyApplyToOdd = toOdd(input)
    
    println(afterFlatMap)
    println(onlyApplyToOdd)
}

我們沒辦法很簡單的就可以證明這些式子成立,所以先帶入簡單的實作來做實驗看看,在這裡有一個 Functor f 的實作: toOdd 。這是一個 pure function,其中輸入只要不是基數就會回傳 None 。然後在這邊我們要驗證的是,左邊的式子 (a -> return(a)) bind f 執行過後,是不是跟右邊只執行 f 的結果是一樣的。當然最後的結果很明顯都是 Some(1) ,而且,你將會發現,如果改掉 input 的值,這兩個函式執行的結果也都會是一樣的。接下來,看看右單位元:

// try to verify: f bind (a -> return(a)) = f
fun testRightIdentity() {
    val toOdd: (Int) -> Maybe<Int> = { x ->
        when(x%2) {
            0 -> Maybe.None()
            else -> Maybe.Some(x)
        }
    }

    val input = 1
    // left hand side: f bind (a -> return(a))
    val afterF = toOdd(input)
    val afterFlatMapId = afterF.flatMap(Maybe.Companion::just)
    // right hand side: f
    val onlyApplyToOdd = toOdd(input)

    println(afterFlatMapId)
    println(onlyApplyToOdd)
}

這次左邊執行的順序不太一樣了,首先先執行過 toOdd ,接下來跟 justflatMaptoOdd 的結果是 Some(1) ,然後是 flatMap(Maybe.Companion::just) ,很容易就發現他其實沒有什麼作用,結果一樣會是 Some(1) 。再加上任意數字的輸入也會得到一樣的結果,所以右單位元也成立。最後是結合律:

// try to verify: (f bind g) bind h = f bind (g bind h) = f bind g bind h
fun testRightIdentity(input: Int) {
    // f
    val toOdd: (Int) -> Maybe<Int> = { x ->
        when(x%2) {
            0 -> Maybe.None()
            else -> Maybe.Some(x)
        }
    }

    // g
    val sqrt: (Int) -> Maybe<Int> = { x ->
        val result = sqrt(x.toDouble())
        when(result) {
            Double.NaN -> Maybe.None()
            else -> Maybe.Some(result.toInt())
        }
    }

    // h
    val toString: (Int) -> Maybe<String> = {x ->
        Maybe.Some(x.toString())
    }

    // (f bind g) bind h
    val left = (toOdd(input).flatMap(sqrt)).flatMap(toString)
    // f bind (g bind h)
    val middle = toOdd(input).flatMap { x: Int -> sqrt(x).flatMap(toString) }
    // f bind g bind h
    val right = toOdd(input).flatMap(sqrt).flatMap(toString)
}

這邊有三個不一樣的 pure function: toOdd, sqrt, toString 。那他們的組合是不是符合結合律呢?首先最左邊的組合最簡單,只要先執行 toOdd ,再使用 flatMap 來執行 sqrt ,就已經是描述了第一個括弧的部分,他們一定會先執行,所以很自然而然的 left (f bind g) bind h 跟 right f bind g bind h 結果會是一樣的。比較難一點的是 middle f bind (g bind h) 的部分,要如何讓後面兩個函式用 flatMap 先組合起來呢?還記得嗎,要寫出一個回傳 function type 的函式要用的是 - lambda 表式示,所以只要在這裡寫出了一個 lambda 來組合 sqrttoString,接下來就可以跟 toOddflatMap 來組合了。

可是 middle 跟 left 會是一樣的結果嗎?讓我們用 Input 為 9 來試試看吧:

  • 首先是 left 的 toOdd(input),會得到 Some(9),接下來是 flatMap(sqrt) ,會得到 Some(3) ,最後是 flatMap(toString) ,得到的值會是 Some("3")
  • 接下來換 middle ,第一個一樣是 toOdd(input) ,結果也會是 Some(9),接著就是後面的 lambda 了,由於上一個的結果是 Some(9) ,所以 lambda 的 x 就會是 9,再來是 sqrt(x),就會得到 Some(3),然後 Some(3) 再跟 flapMap(toString) 組合,會得到 Some("3"),所以這個 flatMap 的 lambda 的內容最後會回傳 Some("3"),最後的結果也自然而然的是 Some("3") 了。

看來 Input 為 9 的時候,不管是 left, middle, right 哪一個,求得的值都一樣,而且不只這樣,不管輸入的值是多少,只要是整數,就會得到一樣的結果,還有你會發現,將這些函式(f, g, h) 替換成任意 pure function ,也絕對會是一樣的結果,這部分讀者可以自己用不同的值跟函式去試試看,就不做給大家看了。

flatMap 波動拳

不知道大家有沒有看過 flatMap 波動拳,如果是以今天的程式來當作範例的話,就會長的像這樣:

// 我好奇到底會有多少人會有耐心想看完這個...而且別懷疑,實際上真的會出現這種程式碼
fun flatMapHell(inputMaybe: Maybe<Int>): Maybe<String> {
    return inputMaybe.flatMap { x ->
        when(x%2) {
            0 -> Maybe.None()
            else -> Maybe.Some(x)
        }.flatMap { y ->
            val result = sqrt(y.toDouble())
            when(result) {
                Double.NaN -> Maybe.None()
                else -> Maybe.Some(result.toInt())
            }.flatMap {z ->
                Maybe.Some(z.toString())
            }
        }
    }
}

但其實,如果這些都是 pure function 的話,完全可以不用這樣寫,剛剛的結合律已經說明了巢狀的 flatMap 跟 function chaining 的 flatMap 是一樣的!( 上面的 right 與 middle 分別是 function chaining巢狀 ) ,而且巢狀的 flatMap 還有一個很大的風險,因為 closure 的關係,裡面的 flatMap 也可以存取的到外面 flatMap 的變數,萬一為了方便而使用了上一層的變數,會使得程式碼跟流程更加的混亂。所以下次各位就知道了,如果再看到這種巢狀的 flatMap ,請將他們轉成 function chaining 的風格,可讀性會大大上升喔。

// 做的事情其實是一樣的,但是可讀性好很多
fun flatMapChaining(inputMaybe: Maybe<Int>): Maybe<String> {
    return inputMaybe
        .flatMap { x ->
            when (x % 2) {
                0 -> Maybe.None()
                else -> Maybe.Some(x)
            }
        }.flatMap { y ->
            val result = sqrt(y.toDouble())
            when (result) {
                Double.NaN -> Maybe.None()
                else -> Maybe.Some(result.toInt())
            }
        }.flatMap { z ->
            Maybe.Some(z.toString())
        }
}

小結

今天嘗試著用 Kotlin 解釋了 Monad Laws ,還有其中的一些專有名詞: bindreturn,除非是我理解錯誤,雖然跟原來以 Haskell 寫出來的版本有所差別,但是大致上的意思應該是不會相差太遠才對,唯一不一樣的地方是, Haskell 寫出來的版本也考慮了 lambda 的執行與否,在我這邊是直接省去了。接下來,下一篇要以實際點的角度來看待 Monad 了,到底,為什麼我們需要他,他到底解決了我們什麼問題?


上一篇
Monad: a Monoid in the Category of EndoFunctors
下一篇
所以 Monad 到底哪裡好用了?
系列文
Functional Programming in Kotlin30

尚未有邦友留言

立即登入留言