iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 18
0
Software Development

Functional Programming in Kotlin系列 第 18

Function type - Another Algebraic Data Type

在之前的 Algebraic Data Type 中介紹了加法與乘法,也就是 Sum Type and Product Type,今天再來介紹另外一種 Algebraic Data Type - Exponential Type!

怎樣的資料格式會是“指數”的關係呢?其實標題已經爆雷了,就是 function type!其實這比 Sum Type 跟 Product Type 還難理解一點。什麼,連這兩個都忘了嗎?沒關係,先讓我們複習一下 Sum Type 跟 Product Type 吧。

// Sum type:只有 Some 或是 None 兩種 ( T + 1 )
sealed class Maybe<T> {
  class Some(value T): Maybe<T>
  class None(); Maybe<T>
}

// Product type :  first, second 彼此是獨立的互不干擾,可能性為 (T * R)
class Pair<T, R>(val first: T, val second: R)

Maybe<Boolean> => 2 + 1 種可能的值
Pair<Boolean, Byte> => 2 * 256 種可能的值

那 Function Type 的數量怎麼算呢?就用最簡單的方法,窮舉法。

// 紅燈要停還是要走呢?不同地區應該有不同的策略XD
typealias Walk = (Light) -> Boolean

enum class Light { GREEN, YELLOW, RED}
// 不管是什麼燈,往前衝就對了
val walk1: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> true
        Light.GREEN -> true
        Light.YELLOW -> true
    }
}

val walk2: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> true
        Light.GREEN -> true
        Light.YELLOW -> false
    }
}

val walk3: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> true
        Light.GREEN -> false
        Light.YELLOW -> true
    }
}

val walk4: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> true
        Light.GREEN -> false
        Light.YELLOW -> false
    }
}

val walk5: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> false
        Light.GREEN -> true
        Light.YELLOW -> true
    }
}

val walk6: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> false
        Light.GREEN -> true
        Light.YELLOW -> false
    }
}

val walk7: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> false
        Light.GREEN -> false
        Light.YELLOW -> true
    }
}

val walk8: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> false
        Light.GREEN -> false
        Light.YELLOW -> false
    }
}

上面的範例中, Light.RED 有可能為 true 或是 falseLight.YELLOW 有可能為 true 或是 falseLight.GREEN 有可能為 true 或是 false ,所以是 2 * 2 * 2 = 8 ,總共 8 種,也可以寫成 2^3 = 8 ,2 對應到的是 Boolean , 3 對應到的則是 Light,由這個例子中看出了原來 Function Type 是一個“指數”的關係:

function type: (T) -> R
number of possibilities: (number of R) ^ (number of T)

更多的代數

還記得上次的 Algebraic Data Type 轉成數學式的推斷嗎?有了 Exponential Type 我們可以玩更多了!來看看下面這幾種各代表什麼意思:

a ^ 1 = a    //1
1 ^ a = 1    //2
  1. 任何數字的 1 次方還是等於本身的數字,還記得 1 可以替換成誰嗎?是 Unit ! ,所以等式的左邊可以替換成: (Unit) → A ,這是什麼函式呢?一個輸入是 Unit 的 function 幾乎等於沒有輸入只有輸出!也就是說可以把它看成 getter() ,所以總共是 A 種可能性,跟等式的右邊一樣。
  2. 數字 1 的任何次方,就是等於 1 乘了很多次,那最後的結果當然還是等於 1。接著,等式的左邊 1 ^ a 可以替換成 (A) → Unit ,這又是什麼意思呢? 這是一個完全不管輸入的 function ,輸出永遠是 Unit , fun boo(input: A) = Unit ,所以只有一種可能性,與等式的右邊也相同。

再來看看下一個:

https://user-images.githubusercontent.com/7949400/94345978-18eb5800-005c-11eb-84fd-66046771dd44.png

不知道大家有沒有忘了這條公式呢?乘方的乘方等於乘方相乘,那他相對應的 Algegraic Data Type 又會是怎樣呢?

Left: (N) -> (M) -> A
Right: (Pair<N, M>) -> A

竟然出現了兩個箭頭!這是什麼可怕的東西!為了讓左邊看起來不這麼可怕,把第一個箭頭轉換成我們熟悉的 kotlin function 吧!把 N 當成輸入, (M) → A 當成輸出

fun left(n: N): (M) -> A { ... }

Left 變成了我們比較熟悉的 Higher order function 了,返回值是一個 function type ,恩...?等等,在兩天前好像看過類似的結構不是嗎? left 的返回類型可以轉為 Reader Monad !

fun left(n: N): Reader<M, A> = { ... }

再來看看右邊,一樣先把他轉為我們熟悉的 kotlin function

fun right(pair: Pair<N, M>): A { ...}

一個輸入為 Pair 的參數其實有點冗余,他其實可以拆開來變成兩個參數:

fun right(n: N, m: M): A {...}
// 一起拿來比較
fun left(n: N): Reader<M, A> = { ... }

這不就是跟兩天前的內容一模一樣嗎?不過是對象 M 換成 GithubRepository 罷了!更好玩的是,如果再轉換回函數型別,就會意外得到柯里化(之後將會介紹)的轉換公式:

left = (Pair<N, M>) -> A = (N, M) -> A 
right = (N) -> (M) -> A 

(N, M) -> A = (N) -> (M) -> A

小結

今天介紹了 function type 作為 Algebraic Data Type 的樣子,不知道你是否也覺得很有趣呢?其實任何一個 Algebraic Data Type 本身都可以形成一個 Functor ,就如同今天提到的 Reader 是 Exponential Type, Maybe 是 Sum Type,還有一些不會介紹到的容器例如: State - [ (S) → (S, A) ] 是 Exponential Type 跟 Product Type 的綜合體 。至於為什麼他們一定都是 Functor 呢?恩...請原諒我現在還沒有能力證明他們,如果對這相關的證明有興趣的話,可以觀看以下這一系列影片:

https://www.youtube.com/watch?v=I8LbkfSSR58&list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_

大概看到 6.2 就會證明給你看了,祝大家觀看愉快!


上一篇
Composition, Abstraction and Principles
下一篇
Curried function
系列文
Functional Programming in Kotlin30

尚未有邦友留言

立即登入留言