iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 12
0

Algebra ,也就是代數,大家國小都學過,可以由簡單的加法與乘法組合而成,在 Category theory 中,也有著這樣的概念,甚至可以將這些概念應用在我們平常使用的 Type System 當中,今天來介紹其中的 sum type 跟 product type 吧。

Sum type

假如現在有一個變數 a,他是一個 boolean 值,那麼,這個變數有幾種可能的值呢?列出來看看吧

val a: Boolean = true
-----------------------
val a: Boolean = false

兩種,對吧!那紅綠燈的狀態有幾種呢?用一個 enum 來代表他:

enum Light {
   RED, YELLOW, GREEN
}

val l: Light = Light.RED
-------------------------
val l: Light = Light.YELLOW
------------------------
val l: Light = Light.GREEN

三種,這也很簡單,那再稍微難一點點,將這個 Light 放進去上一篇講的 Maybe 呢?

val maybe: Maybe<Light> = Maybe.just(Light.RED)
-------------------
val maybe: Maybe<Light> = Maybe.just(Light.YELLOW)
-------------------
val maybe: Maybe<Light> = Maybe.just(Light.GREEN)
-------------------
val maybe: Maybe<Light> = Maybe.None()

3 + 1 = 4 ,總共 4 種,依此類推, Maybe 就會是 2 + 1 = 3 總共 3 種。到這邊應該已經發現到一個規律了,不管 Maybe 裡面的 Type 是什麼,所產生出有可能的值會是原本的 Type 再加上 1。接下來,再來看看更複雜的例子,這邊介紹一個新的容器: Either。

Either 包含了兩種 Type,先暫定這兩個 Type 為 A 跟 B,而 A 跟 B 不會一起存在在同一個容器裡,有 A 就沒有 B,有 B 就沒有 A,以下是 Either 的實作:

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>()
} 

恩...我知道看起來有點抽象,直接來看用法吧!

// Left 的建構式
val a: Either<Boolean, Light> = Either.Left(true)
// Right 的建構式
val b: Either<Boolean, Light> = Either.Right(Light.RED)

現在問題來了,像上面這樣的類別,又總共有多少種可能性呢?首先, Left 就是 true 與 false,然後 Right 呢,就是 RED, YELLOW, GREEN ,剛好是 2 + 3 = 5 加起來有五種!有沒有發現到,Maybe 跟 Either 都用了“加法”,而這個“加法”呢,就是 Algebraic Data Type 中的 sum type。其實 Boolean 也是 sum type 的其中一種表現形式,因為裡面的選擇只有 true 跟 false ,也就是 1 + 1 = 2。以下再舉幾個例子:

Either<Boolean, Boolean> => 2 + 2 = 4
Either<Boolean, Unit>    => 2 + 1 = 3
Either<Unit, Byte>       => 1 + 256 = 257
Maybe<Boolean>           => 2 + 1 = 3
Maybe<Unit>              => 1 + 1 = 2

Product Type

前面講了加法,其實 Algebraic Data Type 也有乘法!其中一個最簡單的例子就是 Pair<A, B> ,一樣來舉個例子來列出所有的可能性吧!下面列出的是 Pair<Boolean, Light>:

val a: Pair<Boolean, Light> = true to Light.RED
-----------------------
val a: Pair<Boolean, Light> = true to Light.YELLOW
-----------------------
val a: Pair<Boolean, Light> = true to Light.GREEN
-----------------------
val a: Pair<Boolean, Light> = false to Light.RED
-----------------------
val a: Pair<Boolean, Light> = false to Light.YELLOW
-----------------------
val a: Pair<Boolean, Light> = false to Light.GREEN

數一數,得到了六種結果,觀察下來,其實就是兩種 Type 的可能性進行相乘的結果: 2 * 3 = 6 。那如果外面再加一層的 Pair 呢?

val a: Pair<Pair<Boolean, Light>, Byte> = (true to Light.RED) to 3

把這問題分解開來,首先我們已經知道裡面那層的 Pair<Boolean, Light> 總共有 6 種可能性了,先給他一個代號 P,那問題就只剩下 Pair<P, Byte> 了。那答案就呼之欲出了,會是 (2 * 3) * 256 = 6 * 256 = 1536 。根據結合律,其實我們可以把括弧拿掉,得到一個 2 * 3 * 256 的算式。而這是不是就代表,如果我有一個可以接受三個 Type 的 class - Tuple<A, B, C>,其實是跟 Pair<Pair<A, B>, C> 是等價的嗎?事實上就是這樣沒錯!他們所包含的資訊量是一樣的,所以下次當你使用了雙層的 Pair ,可以考慮使用一個 Tuple 來做替代。

前面講的都是泛型所建構出的類別,但其實我們最常使用的一般類別也有著一樣的特性,假如現在有一個 Point 類別,有著兩個參數分別是 x 跟 y ,x 跟 y 的型別都是 Byte ,那 Point 有多少種可能性呢?

data class Point(val x: Byte, val y: Byte)

來分析一下,x 總共有 256 種可能, y 也有 256 種可能,x 為 0 的時候 y 的範圍是 0-255 ,x 為 1 的時候也是,所以一直推到 x 為 255 ,全部的可能性就是 256 * 256 ,也是乘法!換句話說,任何有兩個參數的類別,其實都是跟 Pair 等價的,有三個參數的類別呢,是跟 Tuple 等價。這些乘法的關係,就是 Algebraic Data Type 中的 product type。以下再舉幾個例子:

data class Position(val point: Point, val z: Byte) //256 * 256 * 256

// 可以發現到在 Pair 當中使用 Unit 是沒什麼意義的
Pair<Unit, Light>                             => 1 * 3 = 3
Tuple<Boolean, Byte, Light>                   => 2 * 256 * 3

小結

今天介紹了 sum type 與 product type ,還有在轉換資料型別成為代數時,利用數學中的結合律,竟然推導出了另一個可替代的資料型別(本篇中的 Tuple),這正是 Algebraic Data Type 好玩的地方,在下一篇中,你將會看到更多 Algebraic Data Type 的數學轉換!


上一篇
Introduce Functor
下一篇
Algebraic Data Type II
系列文
Functional Programming in Kotlin30

尚未有邦友留言

立即登入留言