Algebraic Data Type II

12th鐵人賽 kotlin software development functional programming

hungyanbin

團隊Kotlin 鐵人陣

2020-09-22 00:40:29

1879 瀏覽

Algebraic Data Type 的 0 與 1

在數學中，我們都知道數字 0 ，０乘任何數字都是 0 、 0 加上任何數字的話就是該數字本身，或是 1 ，1 跟任何數字相乘還是等於該數字，這些是我們從小到大都很熟悉的。然而在上一篇中，在討論 Algebraic Data Type 時，我們知道了 Boolean 可以代表 "2" 這個數字(True and False)。Byte 可以代表 "256"。那 0 跟 1 又是甚麼呢？有辦法在 Kotlin 中找到他們嗎？

其實上一篇就不小心透露出了 1 是誰了，就是 Unit 。在 Pair 跟 Either 的例子中都有出現過它，如果是 Either<Boolean, Unit> 轉換為數學表示式就是 2 + 1 ，Pair<Boolean, Unit> 轉換成數學則是 2 * 1 ，有發現到嗎？在 Pair 中使用 Unit 跟本沒有意義，本質上跟直接使用 Boolean 是一樣的，就跟 2 * 1 = 2 一樣，根本就不需要那個 1 ，一個 true to Unit 跟 true 所帶表的資訊是相等的。再回來說說 Either<Boolean, Unit>，2 + 1 是不是在哪裡有見過呢，這不就是 Maybe 嗎？雖然不能說他們是相等的，他們在使用上還是有所區別，但是 Either<Boolean, Unit> 與 Maybe 這兩個型別所帶來的資訊量是一樣的。

那 0 呢？ 0 又是誰？Either 要搭配誰才能有 n + 0 = n 的效果呢？Kotlin 有一個很容易讓人遺忘的型別，它正是 Nothing 。 Nothing 無法被建構，無法有一個真正的實例。所以對於 Either<Boolean, Nothing> 來說，永遠只能有 Left ，不可能會有 Right ，所以所有的可能性就跟只有一個 Boolean 一樣，是 2 。Either 是一個 Sum Type，加號的左邊是 2 (Boolean) ，而最後所有的可能性也是 2 ，根據 2 + 0 = 2 ，就可以得知 Nothing 所代表的數字就是那個 0。那 Pair<Boolean, Nothing> 又會發生什麼事呢？因為我們知道 Nothing 是無法被建構出來的，然而 Pair 又是缺一不可，一定要同時有兩個值得存在才有辦法構成一個 Pair 。所以得知 Pair<Boolean, Nothing> 是一個無用的型別，在寫程式時沒有任何作用。如果是以數學來看呢？ Pair 是一個 Product Type ，是乘法。從數學上我們得知，0 乘上任何值永遠都會是 0 ，也就是說 2 * 0 = 0，結果跟剛剛推導的結論是一樣的，不會有任何可能的值出現。下面的表格是目前為止的統整：

0             Nothing
1             Unit
2 = 1 + 1     Boolean = True | False
a + b         Either<a, b>
a * b         Pair<a, b>
a + 1         Maybe<a>

Hybrid Algebraic Data Type

當然 Sum Type 跟 Product Type 不一定是單獨存在的，有時候會混著用。舉例來說，一個 Color 的型別，有著 R, G, B 三個不同的 channel ，這邊是 Product Type ，每一個單獨的 channel 呢，又可能有 256 種不同的值，而這個是 Sum Type，如下方所示：

// Product Type: r * g * b
data class Color(val r: Channel, val g: Channel, val b: Channel)
// Sum Type: 0, 1, 2, ...255
typealias Channel = Byte

上面這型別轉成數學就會是 256 * 256 * 256 ，這個例子可能還不夠明顯，再來看看多一點數學，下面這個式子相信大家都在學校學過

a * (b + c) = (a * b) + (a * c)

那把上述的式子轉成 Either 跟 Pair 會發生甚麼事呢？

a * (b + c)       => Pair<A, Either<B, C>>
(a * b) + (a * c) => Either<Pair<A, B>, Pair<A, C>>

依照數學上來看，這兩個型別是相等的，但是真的是這樣嗎？看不太出來啊。我們先看第一個，Pair 的左邊是一個 A ，Pair 的右邊是一個 Either<B, C> ，所以等於說我只能建構出 A to Either.Left 或是 A to Either.Right 的變數對吧，所以就是 A to B 或 A to C 。那下面這個式子呢，就是建構出左邊這個 Pair<A, B> 或是右邊這個 Pair<A, C> ，那不就是一樣是A to B 或 A to C 嗎？數學上的等式推導竟然可以這樣用！再來下一個試試看 1 這個數字：

a * (b + 1) = a * b + a

a * (b + 1) => Pair<A, Maybe<B>>
a * b + a   => Either<Pair<A, B>, A>

Maybe 消失了！在左邊的式子 a * (b + 1) 中，將 1 的加法轉換成 Maybe ，但是右邊的式子卻看不到它的存在，這是怎麼回事呢？來分析看看吧！左邊式子的型別為 Pair<A, Maybe<B>> ，也就是會先處理完 Maybe<B> 的 case ，再回來跟 A 來做 Pair。現在假設 Maybe 經過 fold 的操作過後，回傳的型別是 C（fold 在前幾篇中有介紹過）。那我們就得到了 Pair<A, C> 。再來看第二個式子，其實 Either 也可以使用 fold 的，那如果 fold 之後回傳的型別是 Pair<A, C> 的話，不就是得到同一個資料 Pair<A, C> 了嗎？

val f: (B) -> C = {...}
val g: () -> C =  {...}

val result1: Pair<A, C> = maybeB.fold(some = f, none = { g() })
val result2: Pair<A, C> = eitherPair.fold(
                left: (Pair<A, B> -> Pair<A, C>) = { it.first to f(it.second) },
                right: (A -> Pair<A, C>) = { it to g()})

// 兩個 result 都同時使用了 f 與 g ，除此之外沒有執行任何其他函式。

我們可以從 Algebraic Data Type 上學到甚麼？

在發送網路請求時，結果不是成功就是失敗，那麼我們要怎麼設計一個資料結構來表達這樣的結果呢？有以下兩種選擇：

data class ResultA(val data: String?, val fail: Throwable?) {
    fun isSuccess(): Boolean {
        return fail == null && data != null
    }
}

sealed class ResultB() {
    class Success(val data: String): Result()
    class Fail(val error: Throwable): Result()
}

以上哪個比較好？都幾？

在 ResultA 中，為了要把所有資訊都塞在同一個類別裡，成功的時候，不會有 fail 的情況，所以就得使用 fail = null 來代表這種情形。相反的，失敗的時候，不會有任何我們要的結果，所以也是要有 data = null 的情況。好險至少在 Kotlin 有強迫你處理 null 的情況，如果是 Java 的話就不樂觀了，你根本不知道 null 在這個類別中是設計中的一部分，很容易誤用而發生了 NullPointerException。再來看看 isSuccess 這個函式，這邊需要同時檢查兩個值才可以放心的說這個結果是成功的，不能只檢查 fail 是不是 null ，因為你也沒有辦法確保是否在未來的某一天有一個笨蛋寫出這樣的東西： val result = ResultA(null, null) 。

相對的 ResultB 沒有這些煩惱，要嘛就是 Success，要嘛就是 Fail ，沒有模擬兩可的情況，要判斷是不是成功也非常的直覺，但是在操作上還是有點麻煩，要先轉型為 Success，才能拿到 data，有沒有更好一點的方法？答案是有的，用 Either 來取代他即可：

typealias Result<T> = Either<Throwable, T>

// 不需要 cast 就能直接對值做操作
val result: Result<String> = getResult()
val mapResult: Result<Int> = result.mapRight { s: String -> s.length }
mapResult.fold(right = { ...}, left = { ... })

所以 class ResultA 哪邊做的不好？他有太多不應該存在的狀況了，第一個是不可能有 data 跟 fail 同時存在的 case ，也不可能有 data 跟 fail 同時不存在的 case 。正是因為這樣，不管在使用上，還是設計類別實作時，都要防東防西的，因而產生了很多閱讀上的雜訊。如果將這類別轉成數學表示式，我們將會發現到總共有 (a + 1) * (b + 1) 種可能性（1 是給 null）。那 ResultB 呢？是 a + b ，在這邊意外的發現到，這兩個類別要表示的應該是同一件事，然而在可能性的數量上竟然差距如此之大！一個是加法，另一個是乘法， ResultA 有太多不會用到的可能性了！

所以之後在設計任何類別時，我們可以多想想，究竟這些資料要用的是加法，還是乘法，如此一來可以省去非常多不必要的麻煩，去檢查不應該發生的錯誤。

挑戰時間

好像隔了很多篇都沒有挑戰了，有沒有很懷念呢？在前一篇中已經提供了基本的 Either 建構子，今天就留給大家實作看看 Either 的 operator mapLeft, mapRight 還有 fold 吧！以下提供其使用方式：

sealed class Either<A, B>() {

    class Left<A, B>(val value: A): Either<A, B>()
    class Right<A, B>(val value: B): Either<A, B>()

    //TODO implement mapLeft, mapRight, fold
}

val a = Either.Left<Int, String>(1)
val b = Either.Right<Int, String>("1")

// [left = "1"]
val a2: Either<String, String> = a.mapLeft { it.toString() }
// [left = 1]
val a3: Either<Int, String> = a.mapRight { it + " this should not be executed"}
// [right = 1]
val b2: Either<Int, Int> = b.mapRight { it.length } 

// c = "1 fold right"
val c: String = b.fold(left = {
       it.toString() + " fold left"
    },right = {
       it + " fold right"
    })

// d = "1 fold left"
val d: String = a2.fold(left = {
       it.toString() + " fold left"
    },right = {
       it + " fold right"
    })