[TOC] ### 組合與范疇 **函數式編程的本質是函數的組合，組合的本質是范疇（Category）**。 和搞編程的一樣，數學家喜歡將問題不斷加以抽象從而將本質問題抽取出來加以論證解決，范疇論就是這樣一門以抽象的方法來處理數學概念的學科，主要用于研究一些數學結構之間的映射關系（函數）。 在范疇論里，一個范疇(category)由三部分組成： * 對象(object). * 態射(morphism). * 組合(composition)操作符， #### 范疇的對象 這里的對象可以看成是一類東西，例如數學上的群，環，以及有理數，無理數等都可以歸為一個對象。**對應到編程語言里，可以理解為一個類型，比如說整型，布爾型等**。 #### [態射](https://github.com/EasyKotlin/chapter8_fp#態射) **態射指的是一種映射關系，簡單理解，態射的作用就是把一個對象 A 里的值 a 映射為 另一個對象 B 里的值 b = f(a)，這就是映射的概念**。 態射的存在反映了對象內部的結構，這是范疇論用來研究對象的主要手法：對象內部的結構特性是通過與別的對象的映射關系反映出來的，動靜是相對的，**范疇論通過研究映射關系來達到探知對象的內部結構的目的。** #### [組合操作符](https://github.com/EasyKotlin/chapter8_fp#組合操作符) **組合操作符，用點(.)表示，用于將態射進行組合**。**組合操作符的作用是將兩個態射進行組合**，例如，假設存在態射` f: A -> B, g: B -> C`， 則 `g.f : A -> C.` **一個結構要想成為一個范疇, 除了必須包含上述三樣東西，它還要滿足以下三個限制**: * **結合律**： `f.(g.h) = (f.g).h` 。 * **封閉律**：如果存在態射 f, g，則必然存在` h = f.g` 。 * **同一律**：對結構中的每一個對象 A， 必須存在一個單位態射 Ia: A -> A， 對于單位態射，顯然，對任意其它態射 f, 有` f.I = f`。 在范疇論里另外研究的重點是**范疇與范疇之間的關系**，就正如對象與對象之間有態射一樣，**范疇與范疇之間也存在映射關系，從而可以將一個范疇映射為另一個范疇，這種映射在范疇論中叫作函子(functor）**，具體來說，對于給定的兩個范疇 A 和 B，函子的作用有兩個: * 將范疇 A 中的對象映射到范疇 B 中的對象。 * 將范疇 A 中的態射映射到范疇 B 中的態射。 顯然，**函子反映了不同的范疇之間的內在聯系。跟函數和泛函數的思想是相同的**。 而我們的函數式編程探究的問題與思想理念可以說是跟范疇論完全吻合。**如果把函數式編程的整個的世界看做一個對象，那么FP真正搞的事情就是建立通過函數之間的映射關系，來構建這樣一個美麗的編程世界。** 很多問題的解決（證明）其實都不涉及具體的（數據）結構，而完全可以只依賴映射之間的組合運算(composition)來搞定。這就是函數式編程的核心思想。 如果我們把`程序`看做圖論里面的一張圖G，`數據結構`當作是圖G的節點Node（數據結構，存儲狀態）， 而`算法`邏輯就是這些節點Node之間的Edge (數據映射，Mapping)， 那么這整幅圖`G(N,E)`就是一幅美妙的抽象邏輯之塔的`映射圖`， 也就是我們編程創造的世界：  #### 函數是"第一等公民" 函數式編程（FP）中，函數是"第一等公民"。 所謂"第一等公民"（first class），有時稱為 閉包或者 仿函數（functor）對象， 指的是**函數與其他數據類型一樣，處于平等地位，可以賦值給其他變量，也可以作為參數，傳入另一個函數，或者作為別的函數的返回值。這個以函數為參數的概念，跟C語言中的函數指針類似。** 舉例來說，下面代碼中的print變量就是一個函數（沒有函數名），可以作為另一個函數的參數: ~~~ val print = fun(x:Any){println(x)} listOf(1,2,3).forEach(print) ~~~ #### 高階函數（Higher order Function） **FP 語言支持高階函數，高階函數就是多階映射。高階函數用另一個函數作為其輸入參數，也可以返回一個函數作為輸出。** 代碼示例： ~~~ fun isOdd(x: Int) = x % 2 != 0 fun length(s: String) = s.length fun <A, B, C> compose(f: (B) -> C, g: (A) -> B): (A) -> C { return { x -> f(g(x)) } } ~~~ 測試代碼： ~~~ fun main(args: Array<String>) { val oddLength = compose(::isOdd, ::length) val strings = listOf("a", "ab", "abc") println(strings.filter(oddLength)) // [a, abc] } ~~~ 輸出結果 ``` [a, abc] Process finished with exit code 0 ``` 這個compose函數，其實就是數學中的復合函數的概念，這是一個高階函數的例子：傳入的兩個參數f , g都是函數，其返回值也是函數。 圖示如下：  即下面的關系 ``` B=g(A)，C=f(B) C=f(B)=f(g(A)) ``` 這里的 ~~~ fun <A, B, C> compose(f: (B) -> C, g: (A) -> B): (A) -> C ~~~ 中類型參數對應： ~~~ fun <String, Int, Boolean> compose(f: (Int) -> Boolean, g: (String) -> Int): (String) -> Boolean ~~~ 這里的`(Int) -> Boolean`、`(String) -> Int`、`(String) -> Boolean`都是函數類型。 其實，**從映射的角度看，就是二階映射。對[a, ab, abc] 中每個元素 x 先映射成長度g(x) = 1, 2, 3 ， 再進行第二次映射：f(g(x)) %2 != 0 , 長度是奇數？返回值是true的被過濾出來**。 有了高階函數，我們可以用優雅的方式進行模塊化編程。 另外，高階函數滿足結合律：  #### 閉包（Closure） 閉包簡單講就是一個代碼塊，用`{ }`包起來。此時，程序代碼也就成了數據，可以被一個變量所引用（與C語言的函數指針比較類似）。**閉包的最典型的應用是實現回調函數（callback）**。 閉包包含以下兩個組成部分： * 要執行的代碼塊（由于自由變量被包含在代碼塊中，這些自由變量以及它們引用的對象沒有被釋放） * 自由變量的作用域 在PHP、Scala、Scheme、Common Lisp、Smalltalk、Groovy、JavaScript、Ruby、 Python、Go、Lua、objective c、swift 以及Java（Java8及以上）等語言中都能找到對閉包不同程度的支持。 **Lambda表達式可以表示閉包**。 #### [惰性計算](https://github.com/EasyKotlin/chapter8_fp#惰性計算) 除了高階函數、閉包、Lambda表達式的概念，**FP 還引入了惰性計算的概念**。惰性計算（盡可能延遲表達式求值）是許多函數式編程語言的特性。 惰性集合**在需要時提供其元素，無需預先計算它們**，這帶來了一些好處。 * 首先，您可以將耗時的計算推遲到絕對需要的時候。 * 其次，您可以創造無限個集合，只要它們繼續收到請求，就會繼續提供元素。 * 第三，map 和 filter 等函數的惰性使用讓您能夠得到更高效的代碼（請參閱 參考資料 中的鏈接，加入由 Brian Goetz 組織的相關討論）。 在惰性計算中，表達式不是在綁定到變量時立即計算，而是在求值程序需要產生表達式的值時進行計算。 一個惰性計算的例子是生成無窮 Fibonacci 列表的函數，但是對 第 n 個Fibonacci 數的計算相當于只是從可能的無窮列表中提取一項。 #### [遞歸函數](https://github.com/EasyKotlin/chapter8_fp#遞歸函數) 遞歸指的是一個函數在其定義中直接或間接調用自身的一種方法，它通常把一個大型的復雜的問題轉化為一個與原問題相似的規模較小的問題來解決（復用函數自身）, 這樣可以極大的減少代碼量。遞歸分為兩個階段: 1、遞推：把復雜的問題的求解推到比原問題簡單一些的問題的求解; 2、回歸：當獲得最簡單的情況后，逐步返回，依次得到復雜的解。 遞歸的能力在于用有限的語句來定義對象的無限集合。 使用遞歸要注意的有兩點: （1）遞歸就是在過程或函數里面調用自身; （2）在使用遞歸時，必須有一個明確的遞歸結束條件，稱為遞歸出口。 **PS**：除此之外·，FP還有λ演算、函數柯里化（Currying）、Y組合子(Y - Combinator)、沒有"副作用"、引用透明性等特點，詳情，可參考極簡教程[第八章第一節8.1.3組合與范疇](https://github.com/EasyKotlin/chapter8_fp#813-組合與范疇)