iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 14
1

上一篇的解答:

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

    fun <C> mapLeft(transform: (A) -> C): Either<C, B> {
        return when(this) {
            is Left -> Left(transform(value))
            is Right -> Right(value)
        }
    }

    fun <C> mapRight(transform: (B) -> C): Either<A, C> {
        return when(this) {
            is Left -> Left(value)
            is Right -> Right(transform(value))
        }
    }

    fun <R> fold(left: (A) -> R, right: (B) -> R): R {
        return when(this) {
            is Left -> left(value)
            is Right -> right(value)
        }
    }
}

開始越講越玄了,Monoid 在維基百科尚有一個非常抽象的中文翻譯:么半群。由於么半群完全不會幫助我們有更好地理解,還是稱他為 Monoid 吧。

Definition

Monoid 就是一個集合,而且我們幾乎每天都用到他,只是我們使用的不是這個抽象,而是其他衍伸的實作,例如 String 及 List。那怎樣的集合能夠說是一個 Monoid 呢?首先,這集合裡面有一個二元運算子,這個二元運算子是保持其型別的。例如這個集合是一個整數集合,其運算子為加法,經過了這個二元運算子後,輸出也必須還是整數,如下:

val a: Int = 1
val b: Int = 2
val op: (Int, Int) -> Int = { first, second -> first + second }
val c: Int = op(a, b)

現在再更抽象一點,Monoid 就是一個 T 的集合,搭配上一個 op 為 (T, T) -> T ,或是更貼近數學點, T op T => T。除此之外, Monoid 還必須有單位元與結合律如下:

ID       => Identity in this Monoid
a, b, c  => elements in the Monoid
op       => binary operation for this Monoid

a op ID = a                                   // 1  右單位元
ID op a = a                                   // 2  左單位元
(a op b) op c = a op (b op c) = a op b op c   // 3  結合律

好吧,我知道有點太抽象了,那把這 Monoid 取代為 String 會是什麼樣子呢?

""             => Identity in this Monoid
"a", "b", "c"  => elements in the Monoid
+              => binary operation for this Monoid

"a" + "" = "a"                                            // 1  右單位元
"" + "a" = "a"                                            // 2  左單位元
("a" + "b") + "c" = "a" + ("b" + "c") = "a" + "b" + "c"   // 3  結合律

一但把實際的例子舉出來就直覺多了,對吧!仔細想想,將 String 與 String 連結起來的話,怎樣的 String 能讓另外一邊的 String 保持原樣呢?答案很簡單的就是空字串,所以空字串就是這 Monoid 的單位元。那換成整數跟乘法呢?

1              => Identity in this Monoid
2, 3, 4        => elements in the Monoid
*              => binary operation for this Monoid

2 * 1 = 2                                      // 1  右單位元
1 * 2 = 2                                      // 2  左單位元
(2 * 3) * 4 = 2 * (3 * 4) = 2 * 3 * 4          // 3  結合律

對於乘法來說單位元就是 1,不管誰跟 1 做相乘,都會得到原來的數字。

觀察:

首先,二元運算子為什麼要這樣規定呢?難道我不能定義 op 為 (T, T) -> R 嗎?讓型別有更多的彈性不是很好嗎?如果這樣規定了,這個 op 就不太能夠重用了,由於型別不同,也無法因此有結合律,保持一致又簡單的介面是人的天性。那又為什麼要有右單位元跟左單位元呢?一樣的原因,單位元放在左邊跟單位元放在右邊卻得到不同的結果,這不是很奇怪嗎? 2 * 1 = 2, 1 * 2 = 1 這樣?很奇怪對吧!另一方面,不是單位元卻得到不同的結果是可以接受的,例如 "a" + "b" = "ab", "b" + "a" = "ba"

Monoid in Programming

由上述的觀察來看,Monoid 其實是一個很直覺的觀念,應用這個概念,可以設計出直覺的,符合常識的資料以及其運算,大家都希望看到的所有東西都是直覺而且符合邏輯的。但是我們應該都很常遇到吧,看到其他人寫的程式碼,邊看邊罵,這到底是什麼爛設計,一點都不好用,原本預期的產出是 A ,結果給我 B, C, D ,害我浪費了這麼多時間。

我知道很多人一開始都會覺得 functional programming 很不直覺(包括我),但是他背後的理論,卻是大家最習以為常的邏輯,這真是有點矛盾,對吧XD。這些理論都是抽象過後的成果,我們完全沒必要硬要使用一個叫做 Monoid 或是 Functor 的類別,直接使用實作即可,像以往一樣,使用 List, String, Observable 等等。

既然說到了 Functor ,不覺得 Monoid 跟 Functor 的規則有點像嗎?讓我們回頭過來看 Maybe :

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

    fun <R> map(transform: (T) -> R): Maybe<R> {
        return when(this) {
            is Some -> Some(transform(value))
            is None -> None()
        }
    }

    // 這邊的實作會是什麼?
    fun op(another: Maybe<T>): Maybe<T> = ?
}

這邊有幾個問題,Maybe 的單位元是什麼?Maybe 也符合 Monoid 的這幾條規則嗎?那 op 又是什麼?

Maybe 的 Identity

有什麼 Identity 可以讓 Maybe 保持原樣?先從簡單的 Some 開始,如果原本就已經是 Some 了,不管跟怎樣的 Maybe 做結合,都不希望有任何的改變。所以 Identity 也是一個 Some 的話,很難就這樣不做任何事,最好是一個 None ,這樣的話 Some(A) op None 還是保持 Some(A) 其實是蠻合理的。另一方面,放左邊的話 None op Some(A) ,直接忽略左邊的 Maybe 也是合情合理。

Maybe 的 Associativity

剛剛都是一個 Some 配上一個 None 的案例,那如果兩個都是 Some 呢?要怎樣做才能讓 Some(A) op Some(B) 符合結合律呢?看起來我們只有兩個選擇,不是選擇前面就是後面,讓我們先選擇前面看看吧!

Some(A) op Some(B) => Some(A)
(Some(A) op Some(B)) op Some(C) => Some(A) op Some(C) => Some(A)
Some(A) op (Some(B) op Some(C)) => Some(A) op Some(B) => Some(A)

恩,看起來選擇前面是對的,有符合結合律,我們找到了一個 Monoid,那如果是後面呢?

Some(A) op Some(B) => Some(B)
(Some(A) op Some(B)) op Some(C) => Some(B) op Some(C) => Some(C)
Some(A) op (Some(B) op Some(C)) => Some(A) op Some(C) => Some(C)

選擇後面竟然也符合結合律!結果是兩個方案都可行!那我們就稱第一種 op 為 first ,第二種 op 為 last 吧!以下是實作:

fun first(other: Maybe<T>): Maybe<T> {
    return when(this) {
        is Some -> this
        is None -> other
    }
}

fun last(other: Maybe<T>): Maybe<T> {
    return when(other) {
        is Some -> other
        is None -> this
    }
}

仔細想想,這兩個 function 對我們來說都很有用不是嗎?當我們要合併兩個 Maybe 的時候,總是得考慮要留下哪一個,與其強迫大家只能留哪一邊,不如提供一個選項給大家選,更棒的是,因為這是 Monoid ,所以不用擔心有非預期的狀況發生!

小結

今天介紹了什麼是 Monoid ,以及在程式中的 Monoid 是什麼樣子的。另外,其實 Monoid 就是一種 Functor ,而且還是 Endofunctor!今天沒有做詳細說明,這些解釋會留在之後。看了這些之後,可以回去想想, List 中有那些 op 可以符合 Monoid 的特性呢?對於 Either, Observable 來說又是什麼呢?

References:

https://stackoverflow.com/questions/58582928/what-is-the-relationship-between-a-monoid-and-a-functor

http://learnyouahaskell.com/functors-applicative-functors-and-monoids


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

1 則留言

0
hannahpun
iT邦新手 5 級 ‧ 2020-09-27 00:21:32

想請教 Monoid 跟 Monad 有什麼不一樣啊? (可以鐵人賽結束在回答我 哈哈)

簡單的來說 Monad 是一種 Monoid ,但是有一些額外的限制,Monoid 的定義比較廣, Monad 的定義比較狹窄一點。狹窄在什麼地方呢,就是 Monad 的“對象”是 EndoFunctor,Monoid 則不限制“對象”,然後這些“對象”就是這篇所說的 List, String 還有 Maybe 。我相信這回答還是很抽象XDD,大概在第 24 篇會有詳細一點的解釋,敬請期待。

hannahpun iT邦新手 5 級 ‧ 2020-09-27 01:10:19 檢舉

謝謝你的解釋,而且我還看到好多不同的 Monad 例如 Either Monad, Task Monad 等,真的太多要學的了啊

我要留言

立即登入留言