Cats（三）：高階型別
我們已經知道函式式是一種更加抽象的程式設計思維方式，它所做的事情就是高度抽象業務物件，然後對其進行組合。
談及抽象，你在 Java 中會經常接觸到一階的引數多型，這也是我們所熟悉的泛型。利用泛型多型，在很大程度上可以減少大量相同的程式碼。然而，當我們需要更高階的抽象的時候，泛型也避免不了程式碼冗餘。如你所知，標準庫中的List
、Set
等都實現了Iterable
介面，它們都有相同的方法如filter
、remove
。
現在我們來嘗試通過泛型設計Iterable
：
trait Iterable[T]{
def filter(p: T ⇒ Boolean): Iterable[T]
def remove(p: T ⇒ Boolean): Iterable[T] = filter (x ⇒ !p(x))
}
當我們用List
去實現Iterable
時，由於filter
、remove
方法需要返回具體的容器型別，你需要重新實現這些方法：
trait List[T]extends Iterable[T]{
def filter(p: T ⇒ Boolean): List[T]
override def remove(p: T ⇒ Boolean): List[T] = filter (x ⇒ !p(x))
}
相同的道理，Set
也需要重新實現filter
和remove
方法：
trait Set[T]extends Iterable[T]{
def filter(p: T ⇒ Boolean): Set[T]
override def remove(p: T ⇒ Boolean): Set[T] = filter (x ⇒ !p(x))
}
如上所示，這種利用一階引數多型的技術依舊存在程式碼冗餘。現在我們停下來想一想，假使型別也能像函式一樣支援高階，也就是可以通過型別來創造新的型別，那麼多階型別就可以上升到更高的抽象，從而進一步消除冗餘的程式碼—這便是我們接下來要談論的高階型別（higher-order kind）。
高階型別：用型別構造新型別
要理解高階型別，我們需要先了解什麼是「型別構造器（type constructor）」。探討到構造器，你應該非常熟悉所謂的「值構造器（value constructor）」。
很多情況下，值構造器可以是一個函式，我們可以給一個函式傳遞一個值引數，從而構造出一個新的值。就像這樣子：
(x: Int) => x
作為比較，型別構造器就可以為傳遞一個型別變數，然後構造出一個新的型別。比如List[T]
，當我們傳入Int時，就可以產出List[Int]
型別。
在上述例子中，值建構函式的返回結果x是具體的值，List[T]
傳入型別變數後，也是具體的型別（如List[Int]
）。當我們討論「一階」概念的時候，具體的值或資訊就是構造的結果。
因此，我們可以進一步推導：
- 一階值構造器 ：通過傳入一個具體的值，然後構造出另一個具體的值；
- 一階型別構造器 ：通過傳入一個具體的型別變數，然而構造出另一個具體的型別。
在理解了上述的概念之後，我們就更好地理解高階函數了。它突破了一階值構造器，可以支援傳入一個值構造器，或者返回另一個值構造器。如：
{ (x: Int => Int) => x(1) }
{ x: Int => {y: Int => x + y} }
同樣的道理，高階型別就可以支援傳入構造器變數，或是構造出另一個型別構造器。我們可以定義一種型別構造器Container
，然後將其作為另一個型別構造器Iterable的型別變數：
trait Iterable[T,Container[X]]
然後，我們再用這種假設的語言特性重新實現下List
、Set
，會驚喜地發現冗餘的程式碼消失了：
trait Iterable[T,Container[X]]{
def filter(p: T ⇒ Boolean): Container[T]
def remove(p: T ⇒ Boolean): Container[T] = filter (x ⇒ !p(x))
}
trait List[T]extends Iterable[T,List]
trait Set[T]extends Iterable[T,Set]
這樣就可以寫出更加抽象和強大的程式碼。
高階型別和Typeclass
相信你已經有點感覺到高階型別的強大之處，那麼它有哪些具體應用呢？
事實上，在Haskell中高階型別特性天然了催生了這門語言中一項非常強大的語言特性—Typeclass。接下來我們用Scala這門語言，來實現一個很常見的Typeclass例子—Functor（函子）。
關於什麼是Typeclass可以閱讀ping-vs-typeclasses-2/" rel="nofollow,noindex" target="_blank">https://scala.cool/2017/09/subtyping-vs-typeclasses-2/
函子：高階型別之間的對映
當你第一次接觸到“函子”這個概念的時候，可能會有點怵，因為函數語言程式設計非常近似數學，更準確地說，函數語言程式設計思想的背後理論，是一套被叫做範疇論的學科。
範疇論是抽象地處理數學結構以及結構之間聯絡的一門數學理論,以抽象的方法來處理數學概念,將這些概念形式化成一組組的「物件」及「態射」。
然而，你千萬不要被這些術語嚇到。因為本質上他們是非常容易理解的東西。我們先來看看上面提到的“對映”，你肯定在學習集合論的時候遇到過它。在程式設計中，函式其實就可以看成是具體型別之間的對映關係。那麼，當我們來理解函子的時候，其實只要將其看成是高階型別的引數型別之間的對映，就很容易理解了。
下面我們來用Scala定義一個高階型別Functor：
trait Functor[F[_]]{
def fmap[A, B](fa: F[A], f: A => B): F[B]
}
現在來分析下Functor的實現：
-
Functor支援傳入型別變數F，這也是一個高階型別；
-
Functor中實現了一個fmap方法，它接收一個型別為
F[A]的引數變數fa，以及一個函式f，通過它我們可以把fa中的元素型別A對映為B，即fmap方法返回的結果型別為F[B]。
如果你仔細思考，會發現Functor的應用非常廣泛。舉個例子，我們希望將一個List[Int]
中的元素都轉化為字串，下面我們就來看看在Scala中，如何讓List[T]
整合Functor的功能：
implicit val ListFunctor = new Functor[List] {
def fmap[A,B](f:A=>B): List[A] => List[B] = list =>list map f
}
在Kotlin中用擴充套件方法實現Typeclass
現在我們打算做個挑戰——實現一個Kotlin版本的Functor。然而Kotlin不支援高階型別，像前文例子Functor[F[_]]
中的F[_]
在Kotlin中並沒有與之對應概念。
慶幸的是Jeremy Yallop和Leo White曾經在論文《Lightweight higher-kinded polymorphism》 中闡述了一種模擬高階型別的方法。
我們以Functor為例來看看這種方法是如何模擬出高階型別的。
interface Kind<out F, out A>
interface Functor<F>{
fun <A, B>Kind<F, A>.map(f: (A) -> B): Kind<F, B>
}
首先我們定義了型別 Kind
接下來我們看看這個高階型別如何應用到具體型別中，為此我們自定義了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>()
List
有兩個狀態構成，一個是Nil
代表空的列表，另一個Cons
表示由head
和tail
連線而成的列表。
注意到List實現了Kind<List.K, A>
，代入上面Kind的定義，我們得到List<A>
是型別構造器List.K
應用型別引數A
之後得到的型別。由此我們就可以用List.K
代表List
這個高階型別。
回到Functor的例子，我們很容易設計List
的Functor例項：
@Suppress("UNCHECKED_CAST","NOTHING_TO_INLINE")
inline fun <A>Kind<List.K, A>.unwrap(): List<A> =
this as List<A>
object ListFunctor: Functor<List.K> {
override def 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
}
}
}
如上面例子所示，我們就構造出了List
型別的Functor例項。現在還差最後的關鍵一步：如何使用這個例項。
眾所周知，Kotlin無法將object內部的擴充套件方法直接import進來，也就是說以下的程式碼是不行的：
import ListFunctor.*
Cons(1, Nil).map{ it + 1}
我們沒法將定義在object裡的擴充套件方法直接import，慶幸的是Kotlin中的receiver機制可以將object中的成員引入作用域，所以我們只需要使用run
函式，就可以使用這個例項。
ListFunctor.run {
Cons(1, Nil).map { it + 1 }
}