函数式通用结构设计

介绍一个非常让人恶心的专业术语，Monad。(单子)
Monad 无非就是个自函子范畴上的幺半群（Monoid）

百科上说： 在范畴论中，函子（functor）是范畴间的一类映射，通俗地说，是范畴间的同态。

我前面文章说，理解函子可以理解，高阶类型的参数之间的映射。

百科上说： 幺半群，是指在抽象代数此一数学分支中，幺半群是指一个带有可结合二元运算和单位元的代数结构。

简单Kotlin里理解：一方面是一个简单的Typeclass；另一方面，Monoid 用来描述一种代数，遵循了Monoid法则，即结合律和同一律。

说了这么多，解释一下数学专业属于，其实还是，有点含糊，不理它，但是不影响我们理解。

1. 什么是Monoid

• 一个抽象类型A
• 一个满足结合律的二元操作，（接受任何两个A类型的参数，返回一个A类型的结果）
• 一个单元zero，同样也是一A类型的一个值
• 结合律。append(a,append(b,c))==append(append(a,b),c),等式对于任何A类型的值（a,b,c）均成立
• 同一律。append（a,zero）== a ,append(zero,a) == a,单元zero与任何A类型的值（a）的append操作，结果都等于a。

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

我们Monoid做什么，举个小例子，字符串拼接操作

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

• 抽象类型A具体话String
• 任何三个字符串拼接满足结合律。如：（“起灵” + “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>()

扩展一个sum方法，支持指定的一种二元操作，对列表元素操作。和上个文章说的ListFodable，这也是一个典型的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（十七）函数式编程<2>” 相关内容

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> 类型参数ma。Monoid抽象结构非常适合fold操作。回顾下Kotlin里面fold在标准库定义

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

stringConcatMonoid 来写个测试

println(
                Cons(
                    "Dive ",
                    Cons(
                        "into ",
                        Cons("Kotlin", Nil)
                    )
                ).sum(stringConcatMonoid)
            )
结果：Dive into Kotlin

这里只是理论基础概念，复杂业务还需要好好考虑。

3. Monad

用Monoid<A>,Monoid<B>组合出一个新的Monoid<C>,这个新的Monoid依旧遵循Monoid法则，及满足同一律和结合律。
好处，我们遵循数学定理一样组合，无需关心过程的具体类型（A，B）最终导出的结果依旧遵循正确法则，省去了测试的工作。

（1） 函子定律

定义类型Kind<F,A>定义map操作，返回另一个类型Kind<F,B>.回顾Functor实现

// 模拟高阶类型
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，代表一个列表容器，实际上F可以是其他的类型构造器，如

• 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>
...
}

同一律法则。
假设有一个identify函数，接受A类型参数，返回结果还是a

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

(2) 用map进行组合满足结合律。
函数f进行map的结果，应用函数g进行map，这个操作最终得到的结果与直接函子实例用两个函数组合的新函数进行map的结果相同

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)
            }
结果：true

我们把告诫类型看做一个管道Kind<F,A>,Functor 提供了可能，支持管道内状态进行转化操作，简化表示为map操作，

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

新的管道规格保持不变，旧的容器依旧保持不变，利用递归思想（类似Pair构建出List),类似贪吃蛇可以创造出无尽的列表，用函数支持

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

实际业务副作用不可避免，如果我们把副作用限制在管道容器内，管道看做一个拥有原子性整体，那么依旧符合引用透明性。我们可以将相同容器内的副作用利用函数f组合，尽量推迟到最后执行，就是典型函数式编程。

（3）flatMap 实现复杂的组合

map2操作，会得到一个嵌套容器的结构。Kind<F,A>进行map，应用一个返回Kind<F,B>的函数，那么结果Kind<F,Kind<F,B>>.我们需要一个flattern的操作把嵌套容器的F提取出来，转化为Kind<F,B>

Kotlin 支持flatten操作的flatMap可以看成map与flatten的结合操作。可行思路就是给我们之前的高阶类型扩展一个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) }
    }
}

我们引入一个pure方法，也就是一个unit方法，作用将A类型参数转化为Kind<F,A>类型，map方法同样可以用flatMap实现。

这期是就是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>
}

构建一个Monad的ListMonad 实例

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实现map。那么所有的Monad其实就是Functor，定义Monad<F>时候，直接实现Functor<F>

我们定义一个具体Applicative<F>

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

//Applicative 结构
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> 直接实现Functor<F>，在内部高阶类型扩展ap方法，ap接受一个高阶类型，Kind<F,(A) -> (B)>参数然后返回Kind<A,B>

//重新定义Monad<F> 及时Applicative<F> 也是 Functor<F> 同时定义了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操作，创建一个代表输入输出类型StdIO<A>,实现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>()

我们创建单利对象ReadLine，数据类WriteLine读写操作，以及Pure类接受A类型参数，表示StdIO<A>实例。我在其中半生对象实现read，write，pure。我们实现StdIOMonad

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

//StdIOMonad 实现
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 实现了 Monad<StdIO.K>为Kind<StdIO.K,A>扩展flatMap方法，接着就用StdIO和StdIOMonad实现具体的读写业务例子。

//StdIOMonad 实例，读取两个数字进行加法操作，然后输出结果
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())
        }
    }
}

测试调用：

 perform(io.unwrap())