Kotlin基础——Typeclass

高阶类型

如在Iterable新增泛型方法时

interface Iterable<T> {
    fun filter(p: (T) -> Boolean): Iterable<T>
    fun remove(p: (T) -> Boolean): Iterable<T> = filter { x -> !p(x) }
}

对应的List、Set实现上述方法时仍需要返回具体的类型

interface List<T> : Iterable<T> {
    fun filter(p: (T) -> Boolean): List<T>
    fun remove(p: (T) -> Boolean): List<T> = filter { x -> !p(x) }
}

interface Set<T> : Iterable<T> {
    fun filter(p: (T) -> Boolean): Set<T>
    fun remove(p: (T) -> Boolean): Set<T> = filter { x -> !p(x) }
}

使用高阶类型可以解决上述问题，高阶类型指的是用类型构造新类型，Kotlin可以通过扩展实现高阶类型（下面例子都是根据这个来实现）

interface Kind<out F, out A>

sealed class List<out A> : Kind<List.K, A> {
    object K
}

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

object Nil : List<Nothing>()
data class Cons<A>(val head: A, val tail: List<A>) : List<A>()

Kind<out F, out A>表示类型构造器F应用类型参数A产生的新类型，F实际上不能携带类型参数
List.K是List的高阶类型，也就是说传入不同的A，根据List.K会有不同类型
unwrap()将Kind<List.K, A>类型转为List<A>进行操作
Nil为空列表用作尾部，Cons由元素head和及其指向tail构成的链表

Functor

Functor的map()：通过f()方法将Kind<F, A>类型转为Kind<F, B>类型

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

object ListFunctor : Functor<List.K> {
    override fun <A, B> Kind<List.K, A>.map(f: (A) -> B): Kind<List.K, B> {
        return when (this) {
            is Cons -> {
                val t = (this.tail.map(f)).unwrap()
                Cons<B>(f(this.head), t)
            }
            else -> Nil
        }
    }
}

使用方法如下，将Con<Int>转为了Con<String>

val cons: Cons<Int> = Cons(1, Nil)
println(cons.head::class)
println(cons.tail)
ListFunctor.run {
    val cons2: Cons<String> = cons.map { it.toString() } as Cons<String>
    println(cons2.head::class)
    println(cons2.tail)
}

打印如下

class kotlin.Int
com.demo.demo1.Nil@5361555
class kotlin.String
com.demo.demo1.Nil@5361555

Eq和ListEq

Eq

Eq根据传入的类型参数，对其制定比较规则

interface Eq<F> {
    fun F.eq(that: F): Boolean
}

object IntEq : Eq<Int> {
    override fun Int.eq(that: Int): Boolean {
        return this == that
    }
}

如上，对于Int，判断值是否相等，使用方法如下

IntEq.run {
    val a = 1
    println(a.eq(1))
    println(a.eq(2))
}

打印如下

true
false

ListEq

ListEq可根据指定类型参数的比较规则，实现对两个List比较

abstract class ListEq<A>(val a: Eq<A>) : Eq<Kind<List.K, A>> {
    override fun Kind<List.K, A>.eq(that: Kind<List.K, A>): Boolean {
        val curr = this
        return if (curr is Cons && that is Cons) {
            val headEq = a.run {
                curr.head.eq(that.head)
            }
            if (headEq) curr.tail.eq(that.tail) else false
        } else curr is Nil && that is Nil
    }
}

object IntListEq : ListEq<Int>(IntEq)

如上，实现IntListEq，使用方法如下

IntListEq.run {
    val a = Cons(1, Cons(2, Nil))
    val b = Cons(1, Cons(2, Nil))
    val c = Cons(1, Nil)
    println(a.eq(b))
    println(a.eq(c))
}

打印如下

true
false

show和Foldable

Show

show根据传入的类型参数，对其制定输出规则

interface Show<F> {
    fun F.show(): String
}

class Book(val name: String)
object BookShow : Show<Book> {
    override fun Book.show(): String = this.name
}

如上，对于Book，输出name属性，调用方法如下

BookShow.run {
    println(Book("Dive into Kotlin").show())
}

打印如下

Dive into Kotlin

Foldable

Foldable根据传入的类型参数，对其进行拼接（不太能理解这个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)
    }
}

ListShow

abstract class ListShow<A>(val a: Show<A>) : Show<Kind<List.K, A>> {
    override fun Kind<List.K, A>.show(): String {
        val fa = this
        return "[" + ListFoldable.run {
            fa.fold(listOf<String>())({ r, i ->
                r + a.run { i.show() }
            }).joinToString() + "]"
        }
    }
}
object BookListShow : ListShow<Book>(BookShow)

调用方法如下

BookListShow.run {
    println(
        Cons(
            Book("Dive into Kotlin"),
            Cons(Book("Thinking in Java"), Nil)
        ).show()
    )
}

打印如下

[Dive into Kotlin, Thinking in Java]

Monoid

Monoid满足结合律和同一律

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

如对于字符串Monoid

结合律：(“A”+“B”)+“C” == “A”+(“B”+“C”)
同一律：“A”+“” == “A”

object StringConcatMonoid : Monoid<String> {
    override fun zero(): String = ""

    override fun String.append(b: String): String = this + b
}

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

使用方式如下

println(
    Cons(
        "Dive ",
        Cons(
            "into ",
            Cons("Kotlin", Nil)
        )
    ).sum(StringConcatMonoid)
)

打印如下

Dive into Kotlin

Monad

Monad包含了最小的原始操作集合pure()和flatMap()，通过这两个组合，我们可以实现更复杂的数据转换操作

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

如下实现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))
            })
        }
    }
}

Applicative

数学上3中代数结构关系如下Functor -> Applicative -> Monad

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

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

interface Monad<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))
            }
        }
    }
}