Android開發中的函數式編程應用：高階類型详情 - android,函數式編程,kotlin,rxjava,知識 Yumenokanata 日志

1. Monoid
  - 1.1 什麼是Monoid
  - 1.2 一些monoid
  - 1.3 使用Monoid來摺疊列表
  - 1.4 monoid的組合
1. 高階類型
  - 2.1 什麼是高階類型
  - 2.2 Haskell的高階類型
  - 2.3 Java/Kotlin類型系統下的高階類型實現
1. Monad
  - 3.1 定義
  - 3.2 一些例子
1. 類型
  - 4.1 再談類型
  - 4.2 代數數據類型
  - 4.3 模式匹配
  - 4.4 屬性測試（Property Testing）
1. 實例

1. Monoid

1.1 什麼是Monoid

比如對於字符串拼接操作而言，我們可以將三個字符串相加 a + b + c
而在這個操作中，無論我們是先加a和b再加c、還是先加b和c再在前面加a,他們的結果都是一致的：

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

那麼這個操作就是可結合的。

另外，如果用一個空字符串""去和任何字符串相拼接，也都是這個字符串本身

s = s+"" = ""+s

那麼空字符串“”就是一個“單位元”

像這樣符合：

結合律（Associativity）
對於任意 a, b, c，有：
(a + b) + c == a + (b + c)
存在單位元（Identity Element）
存在一個特殊元素 e，使得：
a + e == e + a == a

符合這兩個條件的法則就被稱為monoid法則。
用Kotlin來描述就是：

interface Monoid<A> {
    /**
     * A zero value for this A
     */
    fun empty(): A

    /**
     * Combine two [A] values.
     */
    fun combine(a: A, b: A): A
}

1.2 一些monoid

很多操作都是符合monoid法則的，他們可以構建出monoid對象：

val stringMonoid = object : Monoid<String> {
    override fun empty(): String  = ""
    override fun combine(a: String, b: String): String = a + b
}

fun <A> listMonoid(): Monoid<List<A>> = object : Monoid<List<A>> {
    override fun empty(): List<A> = emptyList()
    override fun combine(a: List<A>, b: List<A>): List<A> = a + b
}

可以試試實現下面的monoid：
val intAddition: Monoid<Int>
val intMultiplication: Monoid<Int>
val booleanOr: Monoid<Boolean>
val booleanAnd: monoid<Boolean>

1.3 使用Monoid來摺疊列表

List有個“摺疊”操作：fold和foldRight

fun <T, R> Iterable<T>.fold(initial: R, operation: (acc: R, T) -> R): R

fun <T, R> List<T>.foldRight(initial: R, operation: (T, acc: R) -> R): R

它們會對列表“從左到右”和“從右到左”進行摺疊（聚合）。
他們的兩個參數和monoid的兩個部分是完全符合的，所以我們可以這樣：

listOf("a", "b", "c")
    .foldRight(stringMonoid.empty(), stringMonoid::combine)

listOf("a", "b", "c")
    .fold(stringMonoid.empty(), stringMonoid::combine)

提問：兩個方法執行的結果是否一致？為什麼？

1.4 monoid的組合

monoid本身的抽象並不是它強大的唯一，真正強大的是它是可以相互組合的

比如：類型A和類型B是符合monoid法則的，則Pair<A, B>也是符合monoid法則的

fun <A, B> productMonoid(a: Monoid<A>, b: Monoid<B>): Monoid<Pair<A, B>>

再比如，我們可以組合出更為複雜的Monoid：

mapMergeMonoid

fun <K, V> mapMergeMonoid(v: Monoid<V>): Monoid<Map<K, V>> =
        object : Monoid<Map<K, V>> {
            override fun empty(): Map<K, V> = emptyMap()

            override fun combine(a: Map<K, V>, b: Map<K, V>): Map<K, V> =
                    (a.keys + b.keys).fold(empty()) { acc, k ->
                        acc + (k to v.combine(
                                a.getOrDefault(k, v.empty()),
                                b.getOrDefault(k, v.empty())
                        ))
                    }
        }

比如

val m1: Monoid<Map<String, Map<String, Int>>> =
        mapMergeMonoid(mapMergeMonoid(intAddition))

本章主要是讓你習慣和更抽象的結構去打交道。monoid是最簡單的純代數抽象，可以以它為起始探索自己開發可能也存在的大量monoid結構。

2. 高階類型

2.1 什麼是高階類型

正如上面演示的，在函數式編程中我們會大量提取共通的操作符，除了展示的monoid，fold、map、flatMap、filter、flatten等等都是很多類型中常見的操作符。

但是我們在提取某些操作符的時候就會出現一些問題，比如：

fun <A> List<A>.map(f: (A) -> B): List<B>
fun <A> Set<A>.map(f: (A) -> B): Set<B>
fun <A> Flow<A>.map(f: (A) -> B): Flow<B>
fun <A> Option<A>.map(f: (A) -> B): Option<B>

我們會發現，在Java/Kotlin的類型系統中是無法提取一個接口來描述這個方法的。這是因為我們無法描述一個“附帶一個泛型的類型”，比如：

fun <F, A> F<A>.map(f: (A) -> B): F<B>

這種比普通泛型更上層的、描述“可以接受泛型類型參數的泛型”就是高階類型（Higher-Kinded Types， HKT）

2.2 Haskell的高階類型

Haskell是原生支持高階類型的，也被叫做類型構造器（Type Constructor），意思就是可以構造新類型的類型構造器

普通類型：

λ> :kind Int
Int :: *

一階類型（ Maybe[_] ）：

λ> :kind Maybe
Maybe :: * -> *

高階類型（函子 Functor[F[_]] ）：

λ> :kind Functor
Functor :: (* -> *) -> Constraint

Functor 函子就是haskell中對map方法的抽象：

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Maybe可以實現Functor：

instance Functor Maybe where
    fmap f (Just x) = Just (f x)
    fmap f Nothing  = Nothing

2.3 Java/Kotlin類型系統下的高階類型實現

但Java/Kotlin類型系統中是沒有高階類型的，所以我們就無法實現高階類型了嗎？
也不是一定不行，只要稍微做出一點妥協，還是可以實現高階類型的功能：

比如我們要創建一個Option類型：

sealed interface Option<out A> {
    data class Some<A>(val a: A): Option<A>
    data object None: Option<Nothing>
}

首先待描述的類型本身是無法使用的了（kotlin中你無法在泛型參數的地方直接寫高階類型，比如 Maybe<List>）。所以我們首先要構建一個假的一階類型來指代Option類型構造器：

class ForOption private constructor() { companion object }

因為我們只會使用到它的類型，所以它並不會也不能被實例化。

接着構造一個通用類型Kind, 用於將F<A>改為Kind<F, A>的形式：

interface Kind<out F, out A>

Kind2、3、4也可以依次構造出來：

// F<A<B>>
typealias Kind2<F, A, B> = Kind<Kind<F, A>, B>
// F<A<B<C>>>
typealias Kind3<F, A, B, C> = Kind<Kind2<F, A, B>, C>
// F<A<B<C<D>>>>
typealias Kind4<F, A, B, C, D> = Kind<Kind3<F, A, B, C>, D>

於是我們可以聲明出Option的高階類型：

typealias OptionOf<A> = Kind<ForOption, A>

最後讓Option類型繼承（等價）於這個類型聲明就完成了：

sealed interface Option<out A>: OptionOf<A> {
    data class Some<A>(val a: A): Option<A>
    data object None: Option<Nothing>
}

使用上，為了方便還可以寫一個輔助函數：高階類型轉原始類型：

inline fun <A> OptionOf<A>.fix(): Option<A> =
  this as Option<A>

提問：如何保證上面的函數一定能成功？

這是對於新類型而言，而對於已有、無法修改的類型如何實現它的高階類型呢？
簡單，包裝一個類型就可以了，比如RxJava中Flowable：

class ForFlowableK private constructor() {
  companion object
}
typealias FlowableKOf<A> = arrow.Kind<ForFlowableK, A>

inline fun <A> FlowableKOf<A>.fix(): FlowableK<A> =
  this as FlowableK<A>

fun <A> Flowable<A>.k(): FlowableK<A> = FlowableK(this)

fun <A> FlowableKOf<A>.value(): Flowable<A> = fix().flowable as Flowable<A>

data class FlowableK<out A>(val flowable: Flowable<out A>) : FlowableKOf<A>

3. Monad

3.1 定義

只有接觸函數式編程，或多或少都會聽説Monad。概念上很簡單：自函子範疇上的幺半羣。
但解釋起來需要逐個詞來理解：
https://segmentfault.com/a/1190000003954370

函子：範疇之間的映射，並且映射後保留了範疇的結構
自函子：從一個範疇映射到自身的函子

Functor f => (a -> b) -> f a -> f b

haskell中，函數是默認柯里化了的，結合部份施用
簡單點説就是map函數

幺半羣（Monoid）： Monad滿足monoid,所以必須存在“幺元”，而二元運算就是flatMap
flatMap :: Monad m => m a -> (a -> m b) -> m b
flatMap是Monad的核心變換規則，它滿足結合律，提供了monoid結構；而且提供了內部展開Monad結構的方法、為後續計算提供了可能。

所以對於一個Monad來説，三個部分缺一不可：

幺元
半羣
自函子

List是一個非常常見的Monad結構：

emptyList()
List<A>.flatMap(f: (A) -> List<B>): List<B>
List<A>.map(f: (A) -> B): List<B>

相似的，我們可以在日常開發中找到大量的Monad結構。我們也可以自己創建Monad結構。但正如上面理論所説，雖然只需要實現這三個方法，但方法實現本身需要符合法則。

x.flatMap(f).flatMap(g) == x.flatMap(a -> f(a).flatMap(g))

我們常見的結構幾乎都是Monad：List、Set、Observable、Single、Maybe、Flow等等。正因如此，它們有着很相似的結構和操作。

提問： 1. Complatable是Monad嗎？ 2. LiveData是Monad嗎？

3.2 一些例子

interface Kind<out F, out A>

typealias Kind2<F, A, B> = Kind<Kind<F, A>, B>
typealias Kind3<F, A, B, C> = Kind<Kind2<F, A, B>, C>

interface Monad<F> {
    fun <A> pure(a: A): Kind<F, A>
    fun <A, B> Kind<F, A>.flatMap(f: (A) -> Kind<F, B>): Kind<F, B>
}

// Reader Monad
class ForReader private constructor() { companion object }
typealias ReaderOf<R, A> = Kind<Kind<ForReader, R>, A>

class Reader<R, A>(val run: (R) -> A) : ReaderOf<R, A> {
    companion object {
        fun <R, A> just(a: A): Reader<R, A> = Reader { a }
    }

    fun <B> flatMap(f: (A) -> Reader<R, B>): Reader<R, B> =
        Reader { r -> f(run(r)).run(r) }
}

fun <R, A> ReaderOf<R, A>.fix(): Reader<R, A> = this as Reader<R, A>

object ReaderMonad<R> : Monad<Kind<ForReader, R>> {
    override fun <A> pure(a: A): Kind<Kind<ForReader, R>, A> = Reader.just(a)
    override fun <A, B> Kind<Kind<ForReader, R>, A>.flatMap(f: (A) -> Kind<Kind<ForReader, R>, B>): Kind<Kind<ForReader, R>, B> =
        fix().flatMap { f(it).fix() }
}

// State Monad
class ForState private constructor() { companion object }
typealias StateOf<S, A> = Kind<Kind<ForState, S>, A>

data class State<S, A>(val run: (S) -> Pair<A, S>) : StateOf<S, A> {
    companion object {
        fun <S, A> just(a: A): State<S, A> = State { s -> a to s }
    }

    fun <B> flatMap(f: (A) -> State<S, B>): State<S, B> =
        State { s ->
            val (a, newState) = run(s)
            f(a).run(newState)
        }
}

fun <S, A> StateOf<S, A>.fix(): State<S, A> = this as State<S, A>

object StateMonad<S> : Monad<Kind<ForState, S>> {
    override fun <A> pure(a: A): Kind<Kind<ForState, S>, A> = State.just(a)
    override fun <A, B> Kind<Kind<ForState, S>, A>.flatMap(f: (A) -> Kind<Kind<ForState, S>, B>): Kind<Kind<ForState, S>, B> =
        fix().flatMap { f(it).fix() }
}

提問：為什麼State類型一定要有一個A泛型參數，可以去掉嗎？

基於這些基礎操作符，也可以推導出其他的操作符： flatten、ap、map2、zip等

包括Monad本身也只是高階類型能抽象的其中一個常用的類型，Traverse、Zip、Bifoldable等等還有很多Typeclass

4. 類型

4.1 再談類型

當學習了上面的知識後，我們在回頭看我們熟悉而又陌生的一個概念：類型。
這在函數式編程的基礎理論“範疇論”中，則應該叫做“範疇”。
“範疇”可以看作是一些有相似性質的對象的集合，這裏的對象包括數據和函數。
而函數在範疇論中對應的是“態射”，指的是一個範疇映射到另一個範疇的映射或關係。

換句話説，我們在編寫一個函數的時候，實際是在進行一個範疇到另一個範疇的映射。
參數就是起始範疇、返回值就是目的範疇、函數本身就是中間的映射。

那麼什麼是聲明明確的態射（或者説嚴謹的態射），那就是對於第一個範疇中所有對象都進行了完整映射到第二個範疇的態射。

回到編程的語言來説，就是我們編寫的函數，在參數所有可能的情況下都能正確返回對應的返回值的函數。

這裏其實包含幾個含義：

我們編寫的函數，參數一定是精準表明我們所能處理的所有對象集合
函數內部能對所有的參數集合中的對象都能進行正確處理並返回值
返回值能精準覆蓋我們可能返回的所有對象的集合

而類型就是用來描述這種“集合”的。換句話説，“類型”就是“可能的所有對象的集合”
我們的函數聲明中，參數和返回值都是需要用類型來限制的，所以我們聲明函數的時候一定要儘量精準地描述類型。

4.2 代數數據類型

為了適應上面所説的集合描述，函數式編程中通常都是使用代數數據類型（Algebraic Data Type，簡稱ADT）來表述數據結構。
它由兩種基本類型組成：和類型（Sum Type）和積類型（Product Type）

和類型（Sum Type）：和類型表示的是多個可能性中的一個。比如，對於Option,可能是Some也可能是None。
沒錯，sealed class/interface就是和類型的實現：

sealed class Result {
    data class Success(val data: String) : Result()  // 成功，包含數據
    data class Failure(val error: String) : Result() // 失敗，包含錯誤信息
}

積類型（Product Type）：積類型表示的是多個元素的組合。
data class就是積類型的實現（Person類型就是String和Int兩個類型的積）：

data class Person(val name: String, val age: Int)

兩種類型也可以相互組合，成為更為複雜的類型：

sealed class ApiResponse {
    data class Success(val user: Person) : ApiResponse()  // 成功，包含用户信息
    data class Failure(val error: String) : ApiResponse() // 失敗，包含錯誤信息
}

函數數據類型的示例：

sealed class Option<out T> {
    object None : Option<Nothing>()  // 沒有值
    data class Some<out T>(val value: T) : Option<T>()  // 有值
}

sealed class MyList<out T> {
    object Empty : MyList<Nothing>()  // 空列表
    data class Cons<out T>(val head: T, val tail: MyList<T>) : MyList<T>() // 包含元素的列表
}

sealed class MyMap<out K, out V> {
    object Empty : MyMap<Nothing, Nothing>() // 空 Map
    data class Entry<out K, out V>(val key: K, val value: V) : MyMap<K, V>() // 鍵值對
    data class NonEmpty<out K, out V>(val entry: Entry<K, V>, val rest: MyMap<K, V>) : MyMap<K, V>() // 包含元素的 Map
}

4.3 模式匹配

因為函數式編程中，所有的類型都是通過上述兩種類型組合而成，所以語法上也會有對應的優化。
比如：模式匹配。實際就是為能夠更好處理“和類型”而出現的語法：

val response = fetchUserData(true)
when (response) {
    is ApiResponse.Success -> println("User: ${response.user.name}")
    is ApiResponse.Failure -> println("Error: ${response.error}")
}

Haskell中有更為強大的模式匹配能力：

sumOfSquaresOfEvens :: [Int] -> Int
sumOfSquaresOfEvens [] = 0  -- 如果列表為空，返回0
sumOfSquaresOfEvens (x:xs)
  | even x    = x^2 + sumOfSquaresOfEvens xs  -- 如果x是偶數，計算平方並遞歸處理剩餘部分
  | otherwise = sumOfSquaresOfEvens xs        -- 如果x不是偶數，跳過它並遞歸處理剩餘部分

借鑑於函數式編程中模式匹配的常見和強大，目前的一些語言也開始融入更強大的模式匹配能力，比如Java的 JEP 440

4.4 屬性測試（Property Testing）

基於上面所提到的關於函數對於參數和返回類型的精準描述，函數式編程中有一種特別的測試方法：屬性測試。
它是一種自動化測試方法，會自動生成符合參數類型描述的大量輸入數據，以驗證程序在所有可能的輸入範圍內是否都能滿足預期。

kotlin的第三方庫 kotest（https://github.com/kotest/kotest）就實現了屬性測試的相關工具。

它的基礎類型是Gen<A>，核心方法就是生成對應數據類型下的數據集：

public abstract fun random(): kotlin.sequences.Sequence<T>

庫內有提供生成基本數據類型的Gen,比如stringGen, intGen等。但它的最強大的地方在於其組合性，你可以使用基礎類型和一些操作符來定義出自己的複雜對象的Gen（下面是最新版本的例子）。

Gen也是一個Monad類型

data class Address(val street: String, val city: String, val zipCode: String)
data class User(val name: String, val age: Int, val address: Address)

// 生成 Address 類型
val addressGen: Gen<Address> = arbitrary {
    Address(
        street = it.generate(Arb.string(10..20)),  // 生成長度為10-20的街道名稱
        city = it.generate(Arb.string(5..15)),     // 生成長度為5-15的城市名稱
        zipCode = it.generate(Arb.string(5..5))    // 生成5位數字的郵政編碼
    )
}

// 生成 User 類型
val userGen: Gen<User> = arbitrary {
    User(
        name = it.generate(Arb.string(5..10)),  // 生成長度為5-10的名字
        age = it.generate(Arb.int(18..100)),    // 生成18到100之間的年齡
        address = it.generate(addressGen)       // 生成地址，使用之前定義的 addressGen
    )
}

eg: N002_02_DataDetailFragmentTest （這裏使用的是老版本）

同時，屬性測試還有個很強大的能力：shrinker。

如果真的是完全隨機，一方面測試量會很大，二是一旦失敗很難定位錯誤用例。
所以，當發生失敗時，屬性測試會使用shrinker方式來進一步縮小失敗案例。
具體來説，當發生失敗時，屬性測試不會立刻結束，而是根據失敗的用例，生成一系列相關的用例，然後進一步縮小測試範圍，直到不再失敗，從而定位出失敗用例的區間。

class ShrinkerTest : StringSpec({
    // 生成一個整數
    val intGen: Gen<Int> = Arb.int()

    // 一個簡單的加法函數，我們測試它是否總是滿足 x + y >= x
    fun add(x: Int, y: Int): Int = x + y

    "add(x, y) should always be >= x" {
        forAll(intGen, intGen) { x, y ->
            // 檢查加法是否符合預期
            add(x, y) >= x
        }
    }

    // 自定義 shrinker，簡化失敗的案例
    val shrinkedAddGen: Gen<Pair<Int, Int>> = intGen.zip(intGen).shrink { (x, y) ->
        // 將負數的情況簡化為0
        if (x + y < 0) {
            sequenceOf(0 to 0)
        } else {
            sequenceOf(x to y)
        }
    }

    "add(x, y) with shrinker should always be >= x" {
        forAll(shrinkedAddGen) { (x, y) ->
            // 測試加法，檢查是否滿足條件
            add(x, y) >= x
        }
    }
})

測試結果：

Falsifying property: add(x, y) should always be >= x

Generated values:
  x = -1, y = -1
  shrinked to: (0, 0)

演示2：

"整數收縮演示" {

// 用一個簡單的整數例子展示shrinker的效果
// 當測試失敗時，shrinker會嘗試找到最小的失敗用例
checkAll<Int> { n ->
    // 這個條件會在n > 100時失敗
    (n <= 100) shouldBe true
}
// 失敗時會收縮到最簡單的失敗案例，如101或接近101的值

}

--------------------------------------------------------------------------------
整數收縮演示:
--------------------------------------------------------------------------------
Falsified after 26 attempts

Seed: 7189940126606442941

Caused by: Property failed after 1 attempts

Smallest failing case: 101
  Generation at index 0 invalid: 101
  Sample arguments: 101

The following properties failed:
    - Property {n <= 100 shouldBe true} with error: expected: true but was: false

5. 實例

3.1 ErrorLaw

在實際項目中，對於異常的處理往往會非常複雜，比如：

在API返回403的時候（用户token過期）：

首先嚐試使用refresh token刷新token，如果成功，使用新token刷新用户的基礎info，並重試返回403的API
如果刷新或者重試API失敗了3次，則彈出Dialog，詢問用户是否想要重新登錄
- 如果用户選擇“不登錄”，則執行登出的流程（調用登出API、清空當前用户數據等）
- 如果用户選擇“登錄”，則跳轉到登錄畫面
  - 如果用户登錄失敗，則執行登出的流程（調用登出API、清空當前用户數據等）
  - 如果用户登錄成功，則使用新token刷新用户的基礎info，並重試返回403的API

這只是其中一個例子，如何用類型組合的能力使得處理這種複雜程度的異常成為可能，下面舉個實際項目中的例子：

// 定義兩個基礎類型
data class DealErrorContext<F>(val activity: Eval<Context>, val MR: MonadRx<F>, val AC: Async<F>, val retryTimes: Int)

typealias ErrorLaw<F, A> = DealErrorContext<F>.(Throwable) -> Single<Option<Kind<F, A>>>

// 定義基礎操作符
operator fun <F, A> ErrorLaw<F, A>.plus(law2: ErrorLaw<F, A>): ErrorLaw<F, A> = { tha ->
    this@plus(tha).flatMap {
        when (it) {
            is Some -> Single.just(it)
            is None -> law2(tha)
        }
    }
}

// 嘗試編寫幾個異常處理的規則
// 規則：只是靜默處理異常
fun <F, A> silentErrorLaw(): ErrorLaw<F, A> = justLaw {
    MR.raiseError<A>(it).some()
}

// 規則：符合特定http code的情況下，使用Dialog顯示錯誤信息
fun <F, A> showErrorMessageLaw(vararg code: Int): ErrorLaw<F, A> = justLaw just@{ tha ->
    if (code.isEmpty() || code.any { tha.checkHttpCode(it) }) {
        val errorModel = tha.getServerErrorModel()
        if (errorModel != null) MR.run {
            return@just DialogBuilderUtil.buildAlterDialog(activity.value())
                    .setMessage(errorModel.serverError.errorMessage)
                    .setCancelable(false)
                    .enableOkBtn(MR, lang = En)
                    .dismissWhenClickBtn(MR)
                    .autoShowAndGet(MR)
                    .flatMap { MR.raiseError<A>(tha) }
                    .some()
        }
    }
    none()
}

// 也可以組合多個異常處理規則
fun <F, A> newDefaultAllErrorLaw(
        specialLaw: ErrorLaw<F, A> = justLaw { none() },
        otherLaw: ErrorLaw<F, A> = justLaw { none() },
): ErrorLaw<F, A> =
        specialLaw + ignoreErrorLaw() + dealJsonParseErrorLaw() + networkErrorLaw<F, A>() +
                localUnauthErrorLaw() + common401ReloginErrorLaw() + common409WithdrawnErrorLaw() +
                newDefaultErrorLaw() + getSummariesSpecialLaw() + otherLaw +
                dealErrorByDefault()

使用上只需要compose進流即可，所有的異常處理邏輯只需要一行代碼即可引入當前流：

val result = authorizationPresenter.getTokenModelOrError()
        .flatMap { tokenModel ->
            personalService.updateWatchListGroup(
                    tokenModel.token.toApiToken(),
                    WatchListGroupUpdate = updateListParam
            )
        }
        .compose(RxUtil.switchThread())
        .compose(DialogBuilderUtil.composeNetProgressDialog(lazyContextUnsafe()))
        .compose(DealErrorUtil.retrySingle<WatchListGroupUpdateResultModel>(lazyContextUnsafe())) // 只需要在這裏將ErrorLaw compose進流即可
        .await()