函數(shù)式通用結(jié)構(gòu)設(shè)計(jì)

介紹一個(gè)非常讓人惡心的專業(yè)術(shù)語，Monad。(單子)
Monad 無非就是個(gè)自函子范疇上的幺半群（Monoid）

百科上說： 在范疇論中，函子（functor）是范疇間的一類映射，通俗地說，是范疇間的同態(tài)。

我前面文章說，理解函子可以理解，高階類型的參數(shù)之間的映射。

百科上說： 幺半群，是指在抽象代數(shù)此一數(shù)學(xué)分支中，幺半群是指一個(gè)帶有可結(jié)合二元運(yùn)算和單位元的代數(shù)結(jié)構(gòu)。

簡(jiǎn)單Kotlin里理解：一方面是一個(gè)簡(jiǎn)單的Typeclass；另一方面，Monoid 用來描述一種代數(shù)，遵循了Monoid法則，即結(jié)合律和同一律。

說了這么多，解釋一下數(shù)學(xué)專業(yè)屬于，其實(shí)還是，有點(diǎn)含糊，不理它，但是不影響我們理解。

1. 什么是Monoid

• 一個(gè)抽象類型A
• 一個(gè)滿足結(jié)合律的二元操作，（接受任何兩個(gè)A類型的參數(shù)，返回一個(gè)A類型的結(jié)果）
• 一個(gè)單元zero，同樣也是一A類型的一個(gè)值
• 結(jié)合律。append(a,append(b,c))==append(append(a,b),c),等式對(duì)于任何A類型的值（a,b,c）均成立
• 同一律。append（a,zero）== a ,append(zero,a) == a,單元zero與任何A類型的值（a）的append操作，結(jié)果都等于a。

interface Monoid<A> {
    fun zero(): A
    fun A.append(b: A): A
}

我們Monoid做什么，舉個(gè)小例子，字符串拼接操作

object stringConcatMonoid : Monoid<String> {
    override fun zero(): String = ""
    override fun String.append(b: String): String = this + b
}

• 抽象類型A具體話String
• 任何三個(gè)字符串拼接滿足結(jié)合律。如：（“起靈” + “zcwfeng”）+“Kotlin” == “起靈” + （“zcwfeng” + “Kotlin”）
• 單元zero為空字符串，zero=“”

2. Monoid 和 折疊列表

回顧，上篇文章的List定義

sealed class List<out A> : Kind<List.K, A> {
  object K
}
object Nil : List<Nothing>()
data class Cons<A>(val head: A, val tail: List<A>) : List<A>()

擴(kuò)展一個(gè)sum方法，支持指定的一種二元操作，對(duì)列表元素操作。和上個(gè)文章說的ListFodable，這也是一個(gè)典型的fold操作

interface Foldable<F> {
  fun <A, B> Kind<F, A>.fold(init: B): ((B, A) -> B) -> B
}

object ListFoldable : Foldable<List.K> {
  override fun <A, B> Kind<List.K, A>.fold(init: B): ((B, A) -> B) -> B = { f ->
    fun fold0(l: List<A>, v: B): B {
      return when (l) {
        is Cons -> {
          fold0(l.tail, f(v, l.head))
        }
        else -> v
      }
    }
    fold0(this.unwrap(), init)
  }
}

查看前“Kotlin（十七）函數(shù)式編程<2>” 相關(guān)內(nèi)容

fun <A> List<A>.sum(ma: Monoid<A>): A {
  val fa = this
  return ListFoldable.run {
    fa.fold(ma.zero())({ s, i ->
      ma.run {
        s.append(i)
      }
    })
  }
}

sum方法接受Monoid<A> 類型參數(shù)ma。Monoid抽象結(jié)構(gòu)非常適合fold操作?；仡櫹翶otlin里面fold在標(biāo)準(zhǔn)庫(kù)定義

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

stringConcatMonoid 來寫個(gè)測(cè)試

println(
                Cons(
                    "Dive ",
                    Cons(
                        "into ",
                        Cons("Kotlin", Nil)
                    )
                ).sum(stringConcatMonoid)
            )
結(jié)果：Dive into Kotlin

這里只是理論基礎(chǔ)概念，復(fù)雜業(yè)務(wù)還需要好好考慮。

3. Monad

用Monoid<A>,Monoid<B>組合出一個(gè)新的Monoid<C>,這個(gè)新的Monoid依舊遵循Monoid法則，及滿足同一律和結(jié)合律。
好處，我們遵循數(shù)學(xué)定理一樣組合，無需關(guān)心過程的具體類型（A，B）最終導(dǎo)出的結(jié)果依舊遵循正確法則，省去了測(cè)試的工作。

（1） 函子定律

定義類型Kind<F,A>定義map操作，返回另一個(gè)類型Kind<F,B>.回顧Functor實(shí)現(xiàn)

// 模擬高階類型
interface Kind<out F, out A>

interface Functor<F> {
    fun <A, B> Kind<F, A>.map(f: (A) -> B): Kind<F, B>
}

這里的類型List.K 替代F，代表一個(gè)列表容器，實(shí)際上F可以是其他的類型構(gòu)造器，如

• Kint<Option.K,A> 可空或者存在的高階類型
• Kind<Effect.k,A>擁有副作用的高階類型
• Kind<Parser.K,A>代表解析器的高階類型

object ParserFunctor:Functor<Parser.K>{
  override def fun<A,B> Kind<Parser.K,A>.map(f:(A) -> B):Kind<Parser.K,B>
...
}

同一律法則。
假設(shè)有一個(gè)identify函數(shù)，接受A類型參數(shù)，返回結(jié)果還是a

fun identify<A>(a:A) = a
ListFunctor.fun{
  println(Cons(1,Nil).map{identity(it)})
}

(2) 用map進(jìn)行組合滿足結(jié)合律。
函數(shù)f進(jìn)行map的結(jié)果，應(yīng)用函數(shù)g進(jìn)行map，這個(gè)操作最終得到的結(jié)果與直接函子實(shí)例用兩個(gè)函數(shù)組合的新函數(shù)進(jìn)行map的結(jié)果相同

fun f(a: Int) = a + 1
            fun g(a: Int) = a * 2
            ListFunctor.run {
                val r1 = Cons(1, Nil)
                    .map { f(it) }.map { g(it) }

                var r2 = Cons(1, Nil).map { g(f(it)) }
                println(r1 == r2)
            }
結(jié)果：true

我們把告誡類型看做一個(gè)管道Kind<F,A>,Functor 提供了可能，支持管道內(nèi)狀態(tài)進(jìn)行轉(zhuǎn)化操作，簡(jiǎn)化表示為map操作，

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

新的管道規(guī)格保持不變，舊的容器依舊保持不變，利用遞歸思想（類似Pair構(gòu)建出List),類似貪吃蛇可以創(chuàng)造出無盡的列表，用函數(shù)支持

fun <A, B, C> map2(fa: Kind<F, A>, fb: Kind<F, B>, f: (A, B) -> C): Kind<F, C>

實(shí)際業(yè)務(wù)副作用不可避免，如果我們把副作用限制在管道容器內(nèi)，管道看做一個(gè)擁有原子性整體，那么依舊符合引用透明性。我們可以將相同容器內(nèi)的副作用利用函數(shù)f組合，盡量推遲到最后執(zhí)行，就是典型函數(shù)式編程。

（3）flatMap 實(shí)現(xiàn)復(fù)雜的組合

map2操作，會(huì)得到一個(gè)嵌套容器的結(jié)構(gòu)。Kind<F,A>進(jìn)行map，應(yīng)用一個(gè)返回Kind<F,B>的函數(shù)，那么結(jié)果Kind<F,Kind<F,B>>.我們需要一個(gè)flattern的操作把嵌套容器的F提取出來，轉(zhuǎn)化為Kind<F,B>

Kotlin 支持flatten操作的flatMap可以看成map與flatten的結(jié)合操作?？尚兴悸肪褪墙o我們之前的高階類型擴(kuò)展一個(gè)flatMap方法。

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

有了flatMap我們可以寫出偽代碼

    fun <A, B, C> map2(fa: Kind<F, A>, fb: Kind<F, B>, f: (A, B) -> C): Kind<F, C> {
        fa.flatMap { a =>fb.map(b=>f(a, b) }
    }
}

我們引入一個(gè)pure方法，也就是一個(gè)unit方法，作用將A類型參數(shù)轉(zhuǎn)化為Kind<F,A>類型，map方法同樣可以用flatMap實(shí)現(xiàn)。

這期是就是Monad。

（4）什么是 Monad

//-------------Monad  pure+flatMap-->map
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>
}

構(gòu)建一個(gè)Monad的ListMonad 實(shí)例

object ListMonad : Monad<List.K> {
    private fun <A> append(fa: Kind<List.K, A>, fb: Kind<List.K, A>): Kind<List.K, A> {
        return if (fa is Cons) {
            Cons(fa.head, append(fa.tail, fb).unwrap())
        } else {
            fb
        }
    }

    override fun <A> pure(a: A): Kind<List.K, A> {
        return Cons(a, Nil)
    }


    override fun <A, B> Kind<List.K, A>.flatMap(f: (A) -> Kind<List.K, B>)
            : Kind<List.K, B> {

        val fa = this
        val empty: Kind<List.K, B> = Nil
        return ListFoldable.run {
            fa.fold(empty)({ r, l ->
                append(r, f(l))
            })
        }
    }

}

5. Applicative 重新定義Monad

用pure和flatMap實(shí)現(xiàn)map。那么所有的Monad其實(shí)就是Functor，定義Monad<F>時(shí)候，直接實(shí)現(xiàn)Functor<F>

我們定義一個(gè)具體Applicative<F>

interface Functor<F> {
    fun <A, B> Kind<F, A>.map(f: (A) -> B): Kind<F, B>
}

//Applicative 結(jié)構(gòu)
interface Applicative<F> : Functor<F> {
    fun <A> pure(a: A): Kind<F, A>
    fun <A, B> Kind<F, A>.ap(f: Kind<F, (A) -> B>): Kind<F, B>
    override fun <A, B> Kind<F, A>.map(f: (A) -> B): Kind<F, B> {
        return ap(pure(f))
    }
}

Applicative<F> 直接實(shí)現(xiàn)Functor<F>，在內(nèi)部高階類型擴(kuò)展ap方法，ap接受一個(gè)高階類型，Kind<F,(A) -> (B)>參數(shù)然后返回Kind<A,B>

//重新定義Monad<F> 及時(shí)Applicative<F> 也是 Functor<F> 同時(shí)定義了map和ap方法
interface Monad2<F> : Applicative<F> {
    fun <A, B> Kind<F, A>.flatMap(f: (A) -> Kind<F, B>): Kind<F, B>
    override fun <A, B> Kind<F, A>.ap(f: Kind<F, (A) -> B>): Kind<F, B> {
        return f.flatMap { fn ->
            this.flatMap { a ->
                pure(fn(a))
            }
        }
    }
}

Monad 組合副作用

最常見IO操作，創(chuàng)建一個(gè)代表輸入輸出類型StdIO<A>,實(shí)現(xiàn)Kind<StdIO.A>

//----------Monad 副作用組合

sealed class StdIO<A> : Kind<StdIO.K, A> {
    object K
    companion object {
        fun read(): StdIO<String> {
            return ReadLine
        }

        fun write(l: String): StdIO<Unit> {
            return WriteLine(l)
        }

        fun <A> pure(a: A): StdIO<A> {
            return Pure(a)
        }
    }
}

object ReadLine : StdIO<String>()
data class WriteLine(val line: String) : StdIO<Unit>()
data class Pure<A>(val a: A) : StdIO<A>()

我們創(chuàng)建單利對(duì)象ReadLine，數(shù)據(jù)類WriteLine讀寫操作，以及Pure類接受A類型參數(shù)，表示StdIO<A>實(shí)例。我在其中半生對(duì)象實(shí)現(xiàn)read，write，pure。我們實(shí)現(xiàn)StdIOMonad

inline fun <A> Kind<StdIO.K, A>.unwrap(): StdIO<A> = this as StdIO<A>

//StdIOMonad 實(shí)現(xiàn)
data class FlatMap<A, B>(val fa: StdIO<A>, val f: (A) -> StdIO<B>) : StdIO<B>()
object StdIOMonad : Monad<StdIO.K> {
    override fun <A> pure(a: A): Kind<StdIO.K, A> {
        return Pure(a)
    }

    override fun <A, B> Kind<StdIO.K, A>.flatMap(f: (A) -> Kind<StdIO.K, B>)
            : Kind<StdIO.K, B> {
        return FlatMap<A, B>(this.unwrap(), ({ a ->
            f(a).unwrap()
        }))
    }
}

StdIOMonad 實(shí)現(xiàn)了 Monad<StdIO.K>為Kind<StdIO.K,A>擴(kuò)展flatMap方法，接著就用StdIO和StdIOMonad實(shí)現(xiàn)具體的讀寫業(yè)務(wù)例子。

//StdIOMonad 實(shí)例，讀取兩個(gè)數(shù)字進(jìn)行加法操作，然后輸出結(jié)果
fun <A> perform(stdIO: StdIO<A>): A {
    fun <C, D> runFlatMap(fm: FlatMap<C, D>) {
        perform(fm.f(perform(fm.fa)))
    }

    return when (stdIO) {
        is ReadLine -> readLine() as A
        is Pure<A> -> stdIO.a
        is FlatMap<*, A> -> runFlatMap(stdIO) as A
        is WriteLine -> println(stdIO.line) as A
    }
}

val io = StdIOMonad.run {
    StdIO.read().flatMap { a ->
        StdIO.read().flatMap { b ->
            StdIO.write((a.toInt() + b.toInt()).toString())
        }
    }
}

測(cè)試調(diào)用：

 perform(io.unwrap())