第8章 函數(shù)式編程（FP）
《Kotlin極簡教程》正式上架：
點(diǎn)擊這里 > 去京東商城購買閱讀
點(diǎn)擊這里 > 去天貓商城購買閱讀
非常感謝您親愛的讀者苫拍，大家請多支持Ｇ椭洹Ｊブ簟！有任何問題合溺，歡迎隨時與我交流~
值就是函數(shù)卒密，函數(shù)就是值。所有函數(shù)都消費(fèi)函數(shù)辫愉，所有函數(shù)都生產(chǎn)函數(shù)栅受。
"函數(shù)式編程", 又稱泛函編程, 是一種"編程范式"（programming paradigm），也就是如何編寫程序的方法論恭朗。它的基礎(chǔ)是 λ 演算（lambda calculus）屏镊。λ演算可以接受函數(shù)當(dāng)作輸入（參數(shù)）和輸出（返回值）。
和指令式編程相比痰腮，函數(shù)式編程的思維方式更加注重函數(shù)的計(jì)算而芥。它的主要思想是把問題的解決方案寫成一系列嵌套的函數(shù)調(diào)用。
就像在OOP中膀值，一切皆是對象棍丐，編程的是由對象交合創(chuàng)造的世界；
在FP中沧踏，一切皆是函數(shù)歌逢，編程的世界是由函數(shù)交合創(chuàng)造的世界。
函數(shù)式編程中最古老的例子莫過于1958年被創(chuàng)造出來的Lisp了翘狱。Lisp由約翰·麥卡錫（John McCarthy秘案，1927-2011）在1958年基于λ演算所創(chuàng)造，采用抽象數(shù)據(jù)列表與遞歸作符號演算來衍生人工智能潦匈。較現(xiàn)代的例子包括Haskell阱高、ML、Erlang等〔缢酰現(xiàn)代的編程語言對函數(shù)式編程都做了不同程度的支持赤惊，例如：JavaScript, Coffee Script，PHP凰锡，Perl未舟，Python, Ruby, C# , Java 等等（這將是一個不斷增長的列表）圈暗。
函數(shù)式語言在Java 虛擬機(jī)（JVM）平臺上也迅速地嶄露頭角，例如Scala 处面、Clojure 厂置； .NET 平臺也不例外，例如：F# 魂角。
函數(shù)作為Kotlin中的一等公民，可以像其他對象一樣作為函數(shù)的輸入與輸出智绸。關(guān)于對函數(shù)式編程的支持野揪，相對于Scala的學(xué)院派風(fēng)格，Kotlin則是純的的工程派：實(shí)用性瞧栗、簡潔性上都要比Scala要好斯稳。
本章我們來一起學(xué)習(xí)函數(shù)式編程以及在Kotlin中使用函數(shù)式編程的相關(guān)內(nèi)容。
8.1 函數(shù)式編程概述
函數(shù)式編程思想是一個非常古老的思想迹恐。我們簡述如下：
我們就從1900 年 David Hilbert 的第 10 問題（能否通過有限步驟來判定不定方程是否存在有理整數(shù)解挣惰？） 開始說起吧。
1920殴边，Sch?nfinkel憎茂，組合子邏輯(combinatory logic)。直到 Curry Haskell 1927 在普林斯頓大學(xué)當(dāng)講師時重新發(fā)現(xiàn)了 Moses Sch?nfinkel 關(guān)于組合子邏輯的成果锤岸。Moses Sch?nfinkel的成果預(yù)言了很多 Curry 在做的研究竖幔，于是他就跑去哥廷根大學(xué)與熟悉Moses Sch?nfinkel工作的Heinrich Behmann、Paul Bernays兩人一起工作是偷，并于 1930 年以一篇組合子邏輯的論文拿到了博士學(xué)位拳氢。Curry Brooks Haskell 整個職業(yè)生涯都在研究組合子，實(shí)際開創(chuàng)了這個研究領(lǐng)域蛋铆，λ演算中用單參數(shù)函數(shù)來表示多個參數(shù)函數(shù)的方法被稱為 Currying (柯里化)馋评，雖然 Curry 同學(xué)多次指出這個其實(shí)是 Sch?nfinkel 已經(jīng)搞出來的，不過其他人都是因?yàn)樗昧瞬胖来汤玻赃@名字就這定下來了留特；并且有三門編程語言以他的名字命名，分別是：Curry, Brooks, Haskell洪燥。Curry 在 1928 開始開發(fā)類型系統(tǒng)磕秤，他搞的是基于組合子的 polymorphic，Church 則建立了基于函數(shù)的簡單類型系統(tǒng)捧韵。
1929, 哥德爾(Kurt G?del )完備性定理市咆。G?del 首先證明了一個形式系統(tǒng)中的所有公式都可以表示為自然數(shù)，并可以從一自然數(shù)反過來得出相應(yīng)的公式再来。這對于今天的程序員都來說蒙兰，數(shù)字編碼磷瘤、程序即數(shù)據(jù)計(jì)算機(jī)原理最核心、最基本的常識搜变，在那個時代卻腦洞大開的創(chuàng)見采缚。
1933，λ 演算挠他。 Church 在 1933 年搞出來一套以純λ演算為基礎(chǔ)的邏輯扳抽，以期對數(shù)學(xué)進(jìn)行形式化描述。 λ 演算和遞歸函數(shù)理論就是函數(shù)式編程的基礎(chǔ)殖侵。
-
1936贸呢，確定性問題（decision problem，德文 Entscheidungsproblem (發(fā)音 [?nt??a??d??sp?o?ble?m]）拢军。 Alan Turing 和 Alonzo Church楞陷，兩人在同在1936年獨(dú)立給出了否定答案。
1935-1936這個時間段上茉唉，我們有了三個有效計(jì)算模型：通用圖靈機(jī)固蛾、通用遞歸函數(shù)、λ可定義度陆。Rosser 1939 年正式確認(rèn)這三個模型是等效的艾凯。
1953-1957，F(xiàn)ORTRAN (FORmula TRANslating )坚芜，John Backus览芳。1952 年 Halcombe Laning 提出了直接輸入數(shù)學(xué)公式的設(shè)想，并制作了 GEORGE編譯器演示該想法鸿竖。受這個想法啟發(fā)沧竟，1953 年 IBM 的 John Backus 團(tuán)隊(duì)給 IBM 704 主機(jī)研發(fā)數(shù)學(xué)公式翻譯系統(tǒng)。第一個 FORTRAN (FORmula TRANslating 的縮寫)編譯器 1957.4 正式發(fā)行缚忧。FORTRAN 程序的代碼行數(shù)比匯編少20倍悟泵。FORTRAN 的成功警没，讓很多人認(rèn)識到直接把代數(shù)公式輸入進(jìn)電腦是可行的谦去，并開始渴望能用某種形式語言直接把自己的研究內(nèi)容輸入到電腦里進(jìn)行運(yùn)算胳搞。John Backus 在1970年代搞了 FP 語言茵休，1977 年發(fā)表。雖然這門語言并不是最早的函數(shù)式編程語言臊岸，但他是 Functional Programming 這個詞兒的創(chuàng)造者梗脾， 1977 年他的圖靈獎演講題為[“Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs”]
1956尽楔， LISP持钉， John McCarthy衡招。John McCarthy 1956年在 Dartmouth一臺 IBM 704 上搞人工智能研究時，就想到要一個代數(shù)列表處理(algebraic list processing)語言每强。他的項(xiàng)目需要用某種形式語言來編寫語句始腾，以記錄關(guān)于世界的信息州刽，而他感覺列表結(jié)構(gòu)這種形式挺合適，既方便編寫浪箭，也方便推演穗椅。于是就創(chuàng)造了LISP。正因?yàn)槭窃?IBM 704 上開搞的奶栖，所以 LISP 的表處理函數(shù)才會有奇葩的名字： car/cdr 什么的匹表。其實(shí)是取 IBM704 機(jī)器字的不同部分，c=content of驼抹，r=register number, a=address part, d=decrement part 桑孩。
8.1.1 面向?qū)ο缶幊蹋∣OP）與面向函數(shù)編程（FOP）
面向?qū)ο缶幊蹋∣OP）
在OOP中，一切皆是對象框冀。
在面向?qū)ο蟮拿钍剑╥mperative）編程語言里面，構(gòu)建整個世界的基礎(chǔ)是類和類之間溝通用的消息敏簿，這些都可以用類圖（class diagram）來表述明也。《設(shè)計(jì)模式：可復(fù)用面向?qū)ο筌浖幕A(chǔ)》（Design Patterns: Elements of Reusable Object-Oriented Software惯裕，作者ErichGamma温数、Richard Helm、Ralph Johnson蜻势、John Vlissides）一書中撑刺，在每一個模式的說明里都附上了至少一幅類圖。
OOP 的世界提倡開發(fā)者針對具體問題建立專門的數(shù)據(jù)結(jié)構(gòu)握玛，相關(guān)的專門操作行為以“方法”的形式附加在數(shù)據(jù)結(jié)構(gòu)上够傍，自頂向下地來構(gòu)建其編程世界。
OOP追求的是萬事萬物皆對象的理念挠铲，自然地弱化了函數(shù)冕屯。例如：函數(shù)無法作為普通數(shù)據(jù)那樣來傳遞（OOP在函數(shù)指針上的約束），所以在OOP中有各種各樣的拂苹、五花八門的設(shè)計(jì)模式安聘。
GoF所著的《設(shè)計(jì)模式-可復(fù)用面向?qū)ο筌浖幕A(chǔ)》從面向?qū)ο笤O(shè)計(jì)的角度出發(fā)的，通過對封裝瓢棒、繼承浴韭、多態(tài)、組合等技術(shù)的反復(fù)使用脯宿，提煉出一些可重復(fù)使用的面向?qū)ο笤O(shè)計(jì)技巧念颈。而多態(tài)在其中又是重中之重。
多態(tài)嗅绰、面向接口編程舍肠、依賴反轉(zhuǎn)等術(shù)語搀继，描述的思想其實(shí)是相同的。這種反轉(zhuǎn)模式實(shí)現(xiàn)了模塊與模塊之間的解耦翠语。這樣的架構(gòu)是健壯的, 而為了實(shí)現(xiàn)這樣的健壯系統(tǒng)叽躯，在系統(tǒng)架構(gòu)中基本都需要使用多態(tài)性。
絕大部分設(shè)計(jì)模式的實(shí)現(xiàn)都離不開多態(tài)性的思想肌括。換一種說法就是点骑，這些設(shè)計(jì)模式背后的本質(zhì)其實(shí)就是OOP的多態(tài)性，而OOP中的多態(tài)本質(zhì)上又是受約束的函數(shù)指針谍夭。
引用Charlie Calverts對多態(tài)的描述: “多態(tài)性是允許你將父對象設(shè)置成為和一個或更多的他的子對象相等的技術(shù)黑滴，賦值之后，父對象就可以根據(jù)當(dāng)前賦值給它的子對象的特性以不同的方式運(yùn)作紧索≡玻”
簡單的說，就是一句話：允許將子類類型的指針賦值給父類類型的指針珠漂。而我們在OOP中的那么多的設(shè)計(jì)模式晚缩，其實(shí)就是在OOP的多態(tài)性的約束規(guī)則下，對這些函數(shù)指針的調(diào)用模式的總結(jié)媳危。
很多設(shè)計(jì)模式荞彼，在函數(shù)式編程中都可以用高階函數(shù)來代替實(shí)現(xiàn)：
面向函數(shù)編程（FOP）
在FP中，一切皆是函數(shù)待笑。
函數(shù)式編程（FP）是關(guān)于不變性和函數(shù)組合的一種編程范式鸣皂。
函數(shù)式編程語言實(shí)現(xiàn)重用的思路很不一樣。函數(shù)式語言提倡在有限的幾種關(guān)鍵數(shù)據(jù)結(jié)構(gòu)（如list暮蹂、set寞缝、map）上 ， 運(yùn)用函數(shù)的組合 ( 高階函數(shù)) 操作椎侠，自底向上地來構(gòu)建世界第租。
當(dāng)然，我們在工程實(shí)踐中我纪，是不能極端地追求純函數(shù)式的編程的慎宾。一個簡單的原因就是：性能和效率。例如：對于有狀態(tài)的操作浅悉，命令式操作通常會比聲明式操作更有效率趟据。純函數(shù)式編程是解決某些問題的偉大工具，但是在另外的一些問題場景中术健，并不適用汹碱。因?yàn)楦弊饔每偸钦鎸?shí)存在。
OOP喜歡自頂向下架構(gòu)層層分解（解構(gòu)）荞估，F(xiàn)P喜歡自底向上層層組合（復(fù)合）咳促。 而實(shí)際上稚新，編程的本質(zhì)就是次化分解與復(fù)合的過程。通過這樣的過程跪腹，創(chuàng)造一個美妙的邏輯之塔世界褂删。
我們經(jīng)常說一些代碼片段是優(yōu)雅的或美觀的，實(shí)際上意味著它們更容易被人類有限的思維所處理冲茸。
對于程序的復(fù)合而言屯阀，好的代碼是它的表面積要比體積增長的慢。
代碼塊的“表面積”是是我們復(fù)合代碼塊時所需要的信息（接口API協(xié)議定義）轴术。代碼塊的“體積”就是接口內(nèi)部的實(shí)現(xiàn)邏輯（API內(nèi)部的實(shí)現(xiàn)代碼）难衰。
在OOP中，一個理想的對象應(yīng)該是只暴露它的抽象接口（純表面逗栽， 無體積）盖袭，其方法則扮演箭頭的角色。如果為了理解一個對象如何與其他對象進(jìn)行復(fù)合彼宠，當(dāng)你發(fā)現(xiàn)不得不深入挖掘?qū)ο蟮膶?shí)現(xiàn)之時苍凛，此時你所用的編程范式的原本優(yōu)勢就蕩然無存了。
FP通過函數(shù)組合來構(gòu)造其邏輯系統(tǒng)兵志。FP傾向于把軟件分解為其需要執(zhí)行的行為或操作,而且通常采用自底向上的方法。函數(shù)式編程也提供了非常強(qiáng)大的對事物進(jìn)行抽象和組合的能力宣肚。
在FP里面想罕，函數(shù)是“一類公民”（first-class）。它們可以像1, 2, "hello"霉涨，true按价，對象…… 之類的“值”一樣，在任意位置誕生笙瑟，通過變量楼镐，參數(shù)和數(shù)據(jù)結(jié)構(gòu)傳遞到其它地方，可以在任何位置被調(diào)用往枷。
而在OOP中框产，很多所謂面向?qū)ο笤O(shè)計(jì)模式（design pattern），都是因?yàn)槊嫦驅(qū)ο笳Z言沒有first-class function（對應(yīng)的是多態(tài)性）错洁，所以導(dǎo)致了每個函數(shù)必須被包在一個對象里面（受約束的函數(shù)指針）才能傳遞到其它地方秉宿。
勻稱的數(shù)據(jù)結(jié)構(gòu) + 勻稱的算法
在面向?qū)ο笫降木幊讨校磺薪允菍ο螅ㄆ財(cái)?shù)據(jù)結(jié)構(gòu)屯碴、數(shù)據(jù)抽象描睦，輕算法）。我們把它叫做：胖?jǐn)?shù)據(jù)結(jié)構(gòu)-瘦算法（FDS-TA）导而。
在面向函數(shù)式的編程中忱叭，一切皆是函數(shù)（偏重算法隔崎，輕數(shù)據(jù)結(jié)構(gòu)）。我們把它叫做：瘦數(shù)據(jù)結(jié)構(gòu)-胖算法（TDS-FA）韵丑。
可是爵卒，這個世界很復(fù)雜，你怎么能說一切皆是啥呢埂息？真實(shí)的編程世界技潘，自然是勻稱的數(shù)據(jù)結(jié)構(gòu)結(jié)合勻稱的算法（SDS-SA）來創(chuàng)造的。
我們在編程中千康，不可能使用純的對象（對象的行為方法其實(shí)就是函數(shù)）享幽，或者純的函數(shù)（調(diào)用函數(shù)的對象、函數(shù)操作的數(shù)據(jù)其實(shí)就是數(shù)據(jù)結(jié)構(gòu)）來創(chuàng)造一個完整的世界拾弃。如果數(shù)據(jù)結(jié)構(gòu)是陰值桩，算法是陽，那么在解決實(shí)際問題中豪椿，往往是陰陽交合而成世界奔坟。還是那句經(jīng)典的：
程序 = 勻稱的數(shù)據(jù)結(jié)構(gòu) + 勻稱的算法
我們用一幅圖來簡單說明：
函數(shù)與映射
一切皆是映射。函數(shù)式編程的代碼主要就是“對映射的描述”搭盾。我們說組合是編程的本質(zhì)咳秉，其實(shí)，組合就是建立映射關(guān)系鸯隅。
一個函數(shù)無非就是從輸入到輸出的映射澜建，寫成數(shù)學(xué)表達(dá)式就是：
f: X -> Y
p:Y -> Z
p(f) : X ->Z
用編程語言表達(dá)就是：
fun f(x:X) : Y{}
fun p(y:Y) : Z{}
fun fp(f: (X)->Y, p: (Y)->Z) : Z {
return {x -> p(f(x))}
}
8.1.2 函數(shù)式編程基本特性
在經(jīng)常被引用的論文 “Why Functional Programming Matters” 中，作者 John Hughes 說明了模塊化是成功編程的關(guān)鍵蝌以，而函數(shù)編程可以極大地改進(jìn)模塊化炕舵。
在函數(shù)編程中，我們有一個內(nèi)置的框架來開發(fā)更小的跟畅、更簡單的和更一般化的模塊咽筋， 然后將它們組合在一起。
函數(shù)編程的一些基本特點(diǎn)包括：
- 函數(shù)是"第一等公民"徊件。
- 閉包（Closure）和高階函數(shù)（Higher Order Function）奸攻。
- Lambda演算與函數(shù)柯里化（Currying）。
- 懶惰計(jì)算（lazy evaluation）庇忌。
- 使用遞歸作為控制流程的機(jī)制舞箍。
- 引用透明性。
- 沒有副作用皆疹。
8.1.3 組合與范疇
函數(shù)式編程的本質(zhì)是函數(shù)的組合疏橄，組合的本質(zhì)是范疇（Category）。
和搞編程的一樣，數(shù)學(xué)家喜歡將問題不斷加以抽象從而將本質(zhì)問題抽取出來加以論證解決捎迫，范疇論就是這樣一門以抽象的方法來處理數(shù)學(xué)概念的學(xué)科晃酒，主要用于研究一些數(shù)學(xué)結(jié)構(gòu)之間的映射關(guān)系（函數(shù)）。
在范疇論里窄绒，一個范疇(category)由三部分組成：
- 對象(object).
- 態(tài)射(morphism).
- 組合(composition)操作符贝次，
范疇的對象
這里的對象可以看成是一類東西，例如數(shù)學(xué)上的群彰导，環(huán)蛔翅，以及有理數(shù)，無理數(shù)等都可以歸為一個對象位谋。對應(yīng)到編程語言里山析，可以理解為一個類型，比如說整型掏父，布爾型等笋轨。
態(tài)射
態(tài)射指的是一種映射關(guān)系，簡單理解赊淑，態(tài)射的作用就是把一個對象 A 里的值 a 映射為 另一個對象 B 里的值 b = f(a)爵政，這就是映射的概念。
態(tài)射的存在反映了對象內(nèi)部的結(jié)構(gòu)陶缺，這是范疇論用來研究對象的主要手法：對象內(nèi)部的結(jié)構(gòu)特性是通過與別的對象的映射關(guān)系反映出來的钾挟，動靜是相對的，范疇論通過研究映射關(guān)系來達(dá)到探知對象的內(nèi)部結(jié)構(gòu)的目的饱岸。
組合操作符
組合操作符等龙，用點(diǎn)(.)表示，用于將態(tài)射進(jìn)行組合伶贰。組合操作符的作用是將兩個態(tài)射進(jìn)行組合，例如罐栈，假設(shè)存在態(tài)射 f: A -> B, g: B -> C黍衙， 則 g.f : A -> C.
一個結(jié)構(gòu)要想成為一個范疇, 除了必須包含上述三樣?xùn)|西，它還要滿足以下三個限制:
結(jié)合律： f.(g.h) = (f.g).h 荠诬。
封閉律：如果存在態(tài)射 f, g琅翻，則必然存在 h = f.g 。
同一律：對結(jié)構(gòu)中的每一個對象 A, 必須存在一個單位態(tài)射 Ia: A -> A柑贞， 對于單位態(tài)射方椎，顯然，對任意其它態(tài)射 f, 有 f.I = f钧嘶。
在范疇論里另外研究的重點(diǎn)是范疇與范疇之間的關(guān)系棠众，就正如對象與對象之間有態(tài)射一樣，范疇與范疇之間也存在映射關(guān)系，從而可以將一個范疇映射為另一個范疇闸拿，這種映射在范疇論中叫作函子(functor）空盼，具體來說，對于給定的兩個范疇 A 和 B, 函子的作用有兩個:
- 將范疇 A 中的對象映射到范疇 B 中的對象新荤。
- 將范疇 A 中的態(tài)射映射到范疇 B 中的態(tài)射揽趾。
顯然，函子反映了不同的范疇之間的內(nèi)在聯(lián)系苛骨。跟函數(shù)和泛函數(shù)的思想是相同的篱瞎。
而我們的函數(shù)式編程探究的問題與思想理念可以說是跟范疇論完全吻合。如果把函數(shù)式編程的整個的世界看做一個對象痒芝，那么FP真正搞的事情就是建立通過函數(shù)之間的映射關(guān)系渗饮，來構(gòu)建這樣一個美麗的編程世界。
很多問題的解決（證明）其實(shí)都不涉及具體的（數(shù)據(jù)）結(jié)構(gòu)拔稳，而完全可以只依賴映射之間的組合運(yùn)算(composition)來搞定诡宗。這就是函數(shù)式編程的核心思想。
如果我們把程序看做圖論里面的一張圖G瞳步，數(shù)據(jù)結(jié)構(gòu)當(dāng)作是圖G的節(jié)點(diǎn)Node（數(shù)據(jù)結(jié)構(gòu)闷哆，存儲狀態(tài)）， 而算法邏輯就是這些節(jié)點(diǎn)Node之間的Edge (數(shù)據(jù)映射单起，Mapping)抱怔， 那么這整幅圖 G(N,E) 就是一幅美妙的抽象邏輯之塔的 映射圖 ， 也就是我們編程創(chuàng)造的世界：
函數(shù)是"第一等公民"
函數(shù)式編程（FP）中嘀倒，函數(shù)是"第一等公民"屈留。
所謂"第一等公民"（first class），有時稱為 閉包或者 仿函數(shù)（functor）對象测蘑，
指的是函數(shù)與其他數(shù)據(jù)類型一樣灌危，處于平等地位，可以賦值給其他變量碳胳，也可以作為參數(shù)勇蝙，傳入另一個函數(shù)，或者作為別的函數(shù)的返回值挨约。這個以函數(shù)為參數(shù)的概念味混，跟C語言中的函數(shù)指針類似。
舉例來說诫惭，下面代碼中的print變量就是一個函數(shù)（沒有函數(shù)名）翁锡，可以作為另一個函數(shù)的參數(shù):
>>> val print = fun(x:Any){println(x)}
>>> listOf(1,2,3).forEach(print)
1
2
3
高階函數(shù)（Higher order Function）
FP 語言支持高階函數(shù)，高階函數(shù)就是多階映射夕土。高階函數(shù)用另一個函數(shù)作為其輸入?yún)?shù)馆衔，也可以返回一個函數(shù)作為輸出。
代碼示例：
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]
}
這個compose函數(shù)，其實(shí)就是數(shù)學(xué)中的復(fù)合函數(shù)的概念哈踱，這是一個高階函數(shù)的例子：傳入的兩個參數(shù)f , g都是函數(shù)荒适，其返回值也是函數(shù)。
圖示如下：
這里的
fun <A, B, C> compose(f: (B) -> C, g: (A) -> B): (A) -> C
中類型參數(shù)對應(yīng)：
fun <String, Int, Boolean> compose(f: (Int) -> Boolean, g: (String) -> Int): (String) -> Boolean
這里的(Int) -> Boolean 开镣、(String) -> Int刀诬、 (String) -> Boolean 都是函數(shù)類型。
其實(shí)邪财，從映射的角度看陕壹，就是二階映射。對[a, ab, abc] 中每個元素 x 先映射成長度g(x) = 1, 2, 3 树埠， 再進(jìn)行第二次映射：f(g(x)) %2 != 0 , 長度是奇數(shù)糠馆？返回值是true的被過濾出來。
有了高階函數(shù)怎憋，我們可以用優(yōu)雅的方式進(jìn)行模塊化編程又碌。
另外，高階函數(shù)滿足結(jié)合律：
λ演算 （Lambda calculus 或者 λ-calculus）
?? 演算是函數(shù)式語言的基礎(chǔ)绊袋。在λ-演算的基礎(chǔ)上毕匀，發(fā)展起來的π-演算、χ-演算癌别，成為近年來的并發(fā)程序的理論工具之一皂岔，許多經(jīng)典的并發(fā)程序模型就是以π-演算為框架的。λ 演算神奇之處在于展姐，通過最基本的函數(shù)抽象和函數(shù)應(yīng)用法則躁垛，配套以適當(dāng)?shù)募记桑隳軌驑?gòu)造出任意復(fù)雜的可計(jì)算函數(shù)圾笨。
λ演算是一套用于研究函數(shù)定義教馆、函數(shù)應(yīng)用和遞歸的形式系統(tǒng)。它由 阿隆佐·丘奇（Alonzo Church擂达，1903~1995）和 Stephen Cole Kleene 在 20 世紀(jì)三十年代引入活玲。當(dāng)時的背景是解決函數(shù)可計(jì)算的本質(zhì)性問題，初期λ演算成功的解決了在可計(jì)算理論中的判定性問題谍婉，后來根據(jù)Church–Turing thesis，證明了λ演算與圖靈機(jī)是等價(jià)的镀钓。
λ 演算可以被稱為最小的通用程序設(shè)計(jì)語言穗熬。它包括一條變換規(guī)則 (變量替換) 和一條函數(shù)定義方式，λ演算之通用在于丁溅，任何一個可計(jì)算函數(shù)都能用這種形式來表達(dá)和求值唤蔗。
λ演算強(qiáng)調(diào)的是變換規(guī)則的運(yùn)用，這里的變換規(guī)則本質(zhì)上就是函數(shù)映射。
Lambda 表達(dá)式（Lambda Expression） 是 λ演算 的一部分妓柜。
λ演算中一切皆函數(shù)箱季，全體λ表達(dá)式構(gòu)成Λ空間，λ表達(dá)式為Λ空間到Λ空間的函數(shù)棍掐。
例如藏雏，在 lambda 演算中有許多方式都可以定義自然數(shù)，最常見的是Church 整數(shù)作煌，定義如下：
0 = λ f. λ x. x
1 = λ f. λ x. f x
2 = λ f. λ x. f (f x)
3 = λ f. λ x. f (f (f x))
...
數(shù)學(xué)家們都崇尚簡潔掘殴，只用一個關(guān)鍵字 'λ' 來表示對函數(shù)的抽象。
其中的λ f. λ x.粟誓，λ f 是抽象出來的函數(shù), λ x是輸入?yún)?shù)奏寨， . 語法用來分割參數(shù)表和函數(shù)體。 為了更簡潔鹰服，我們簡記為F, 那么上面的Church 整數(shù)定義簡寫為：
0 = F x
1 = F f x
2 = F f (f x)
3 = F f (f (f x))
...
使用λ演算定義布爾值：
TRUE = λ x. λ y. x
FALSE = λ x. λ y. y
用圖示如下：
在λ演算中只有函數(shù)病瞳，一門編程語言中的數(shù)據(jù)類型，比如boolean悲酷、number套菜、list等，都可以使用純λ演算來實(shí)現(xiàn)舔涎。我們不用去關(guān)心數(shù)據(jù)的值是什么笼踩，重點(diǎn)是我們能對這個值做什么操作（apply function）。
使用λ演算定義一個恒等函數(shù)I ：
I = λ x . x
使用Kotlin代碼來寫亡嫌，如下：
>>> val I = {x:Int -> x}
>>> I(0)
0
>>> I(1)
1
>>> I(100)
100
對 I 而言任何一個 x 都是它的不動點(diǎn)(即對某個函數(shù) f(x) 存在這樣的一個輸入 x嚎于，使得函數(shù)的輸出仍舊等于輸入的 x 。形式化的表示即為 f(x) = x )挟冠。
再例如于购，下面的 λ 表達(dá)式表示將x映射為 x+1 :
λ x . x + 1
測試代碼：
( λ x . x + 1) 5
將輸出6 。
這樣的表達(dá)式知染，在Kotlin中, 如果使用Lambda表達(dá)式我們這樣寫：
>>> val addOneLambda = {
... x: Int ->
... x + 1
... }
>>> addOneLambda(1)
2
如果使用匿名函數(shù)肋僧，這樣寫：
>>> val addOneAnonymouse = (fun(x: Int): Int {
... return x + 1
... })
>>> addOneAnonymouse(1)
2
在一些古老的編程語言中，lambda表達(dá)式還是比較接近lambda演算的表達(dá)式的控淡。在現(xiàn)代程序語言中的lambda表達(dá)式嫌吠，只是取名自lambda演算，已經(jīng)與原始的lambda演算有很大差別了掺炭。例如：
在Javascript里沒有任何語法專門代表lambda, 只寫成這樣的嵌套函數(shù)function{ return function{...} }辫诅。
函數(shù)柯里化（Currying）
很多基于 lambda calculus 的程序語言，比如 ML 和 Haskell涧狮，都習(xí)慣用currying 的手法來表示函數(shù)炕矮。比如么夫，如果你在 Haskell 里面這樣寫一個函數(shù)：
f x y = x + y
然后你就可以這樣把鏈表里的每個元素加上 2：
map (f 2) [1, 2, 3]
它會輸出 [3, 4, 5]。
Currying 用一元函數(shù)肤视，來組合成多元函數(shù)档痪。比如，上面的函數(shù) f 的定義在 Scheme 里面相當(dāng)于：
(define f (lambda (x) (lambda (y) (+ x y))))
它是說邢滑，函數(shù) f腐螟，接受一個參數(shù) x，返回另一個函數(shù)（沒有名字）殊鞭。這個匿名函數(shù)遭垛，如果再接受一個參數(shù) y，就會返回 x + y操灿。所以上面的例子里面锯仪，(f 2) 返回的是一個匿名函數(shù)，它會把 2 加到自己的參數(shù)上面返回趾盐。所以把它 map 到 [1, 2, 3]庶喜，我們就得到了 [3, 4, 5]。
我們再使用Kotlin中的函數(shù)式編程來舉例說明救鲤。
首先久窟，我們看下普通的二元函數(shù)的寫法：
fun add(x: Int, y: Int): Int {
return x + y
}
add(1, 2) // 輸出3
這種寫法最簡單，只有一層映射本缠。
柯里化的寫法：
fun curryAdd(x: Int): (Int) -> Int {
return { y -> x + y }
}
curryAdd(1)(2)// 輸出3
我們先傳入?yún)?shù)x = 1斥扛， 返回函數(shù) curryAdd(1) = 1 + y；
然后傳入?yún)?shù) y = 2, 返回最終的值 curryAdd(1)(2) = 3丹锹。
當(dāng)然稀颁，我們也有 λ 表達(dá)式的寫法：
val lambdaCurryAdd = {
x: Int ->
{
y: Int ->
x + y
}
}
lambdaCurryAdd(1)(2) // 輸出 3
這個做法其實(shí)來源于最早的 lambda calculus 的設(shè)計(jì)。因?yàn)?lambda calculus 的函數(shù)都只有一個參數(shù)楣黍，所以為了能夠表示多參數(shù)的函數(shù)匾灶， Haskell Curry （數(shù)學(xué)家和邏輯學(xué)家），發(fā)明了這個方法租漂。
不過在編碼實(shí)踐中阶女，Currying 的工程實(shí)用性、簡潔性上不是那么的友好哩治。大量使用 Currying秃踩，會導(dǎo)致代碼可讀性降低，復(fù)雜性增加业筏，并且還可能因此引起意想不到的錯誤憔杨。 所以在我們的講求工程實(shí)踐性能的Kotlin語言中，
古老而美麗的理論驾孔，也許能夠給我?guī)硭枷氲膯⒌仙指眩窃诠こ虒?shí)踐中未必那么理想。
閉包（Closure）
閉包簡單講就是一個代碼塊翠勉，用{ }包起來妖啥。此時，程序代碼也就成了數(shù)據(jù)对碌，可以被一個變量所引用（與C語言的函數(shù)指針比較類似）荆虱。閉包的最典型的應(yīng)用是實(shí)現(xiàn)回調(diào)函數(shù)（callback）。
閉包包含以下兩個組成部分：
- 要執(zhí)行的代碼塊（由于自由變量被包含在代碼塊中朽们，這些自由變量以及它們引用的對象沒有被釋放）
- 自由變量的作用域
在PHP怀读、Scala、Scheme骑脱、Common Lisp菜枷、Smalltalk、Groovy叁丧、JavaScript啤誊、Ruby、 Python拥娄、Go蚊锹、Lua、objective c稚瘾、swift 以及Java（Java8及以上）等語言中都能找到對閉包不同程度的支持牡昆。
Lambda表達(dá)式可以表示閉包。
惰性計(jì)算
除了高階函數(shù)摊欠、閉包丢烘、Lambda表達(dá)式的概念，F(xiàn)P 還引入了惰性計(jì)算的概念凄硼。惰性計(jì)算（盡可能延遲表達(dá)式求值）是許多函數(shù)式編程語言的特性铅协。惰性集合在需要時提供其元素，無需預(yù)先計(jì)算它們摊沉，這帶來了一些好處狐史。首先，您可以將耗時的計(jì)算推遲到絕對需要的時候说墨。其次骏全，您可以創(chuàng)造無限個集合，只要它們繼續(xù)收到請求尼斧，就會繼續(xù)提供元素姜贡。第三，map 和 filter 等函數(shù)的惰性使用讓您能夠得到更高效的代碼（請參閱 參考資料 中的鏈接棺棵，加入由 Brian Goetz 組織的相關(guān)討論）楼咳。
在惰性計(jì)算中熄捍，表達(dá)式不是在綁定到變量時立即計(jì)算，而是在求值程序需要產(chǎn)生表達(dá)式的值時進(jìn)行計(jì)算母怜。
一個惰性計(jì)算的例子是生成無窮 Fibonacci 列表的函數(shù)余耽，但是對 第 n 個Fibonacci 數(shù)的計(jì)算相當(dāng)于只是從可能的無窮列表中提取一項(xiàng)。
遞歸函數(shù)
遞歸指的是一個函數(shù)在其定義中直接或間接調(diào)用自身的一種方法, 它通常把一個大型的復(fù)雜的問題轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來解決（復(fù)用函數(shù)自身）, 這樣可以極大的減少代碼量苹熏。遞歸分為兩個階段:
1.遞推:把復(fù)雜的問題的求解推到比原問題簡單一些的問題的求解;
2.回歸:當(dāng)獲得最簡單的情況后,逐步返回,依次得到復(fù)雜的解碟贾。
遞歸的能力在于用有限的語句來定義對象的無限集合。
使用遞歸要注意的有兩點(diǎn):
（1）遞歸就是在過程或函數(shù)里面調(diào)用自身;
（2）在使用遞歸時,必須有一個明確的遞歸結(jié)束條件,稱為遞歸出口轨域。
下面我們舉例說明袱耽。
階乘函數(shù) fact(n) 一般這樣遞歸地定義：
fact(n) = if n=0 then 1 else n * fact(n-1)
我們使用Kotlin代碼實(shí)現(xiàn)這個函數(shù)如下：
fun factorial(n: Int): Int {
println("factorial() called! n=$n")
if (n == 0) return 1;
return n * factorial(n - 1);
}
測試代碼：
@Test
fun testFactorial() {
Assert.assertTrue(factorial(0) == 1)
Assert.assertTrue(factorial(1) == 1)
Assert.assertTrue(factorial(3) == 6)
Assert.assertTrue(factorial(10) == 3628800)
}
輸出：
factorial() called! n=0
factorial() called! n=1
factorial() called! n=0
factorial() called! n=3
factorial() called! n=2
factorial() called! n=1
factorial() called! n=0
factorial() called! n=10
factorial() called! n=9
factorial() called! n=8
factorial() called! n=7
factorial() called! n=6
factorial() called! n=5
factorial() called! n=4
factorial() called! n=3
factorial() called! n=2
factorial() called! n=1
factorial() called! n=0
BUILD SUCCESSFUL in 24s
6 actionable tasks: 5 executed, 1 up-to-date
我們可以看到在factorial計(jì)算的過程中，函數(shù)不斷的調(diào)用自身干发，然后不斷的展開朱巨，直到最后到達(dá)了終止的n==0，這是遞歸的原則之一铐然，就是在遞歸的過程中蔬崩，傳遞的參數(shù)一定要不斷的接近終止條件，在上面的例子中就是n的值不斷減少搀暑，直至最后為0沥阳。
再舉個Fibonacci數(shù)列的例子。
Fibonacci數(shù)列用數(shù)學(xué)中的數(shù)列的遞歸表達(dá)式定義如下：
fibonacci (0) = 0
fibonacci (1) = 1
fibonacci (n) = fibonacci (n - 1) + fibonacci (n - 2)
我們使用Kotlin代碼實(shí)現(xiàn)它：
fun fibonacci(n: Int): Int {
if (n == 1 || n == 2) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
測試代碼：
@Test
fun testFibonacci() {
Assert.assertTrue(fibonacci(1) == 1)
Assert.assertTrue(fibonacci(2) == 1)
Assert.assertTrue(fibonacci(3) == 2)
Assert.assertTrue(fibonacci(4) == 3)
Assert.assertTrue(fibonacci(5) == 5)
Assert.assertTrue(fibonacci(6) == 8)
}
外篇： Scheme中的遞歸寫法
因?yàn)镾cheme 程序中充滿了一對對嵌套的小括號自点，這些嵌套的符號體現(xiàn)了最基本的數(shù)學(xué)思想——遞歸桐罕。所以，為了多維度的來理解遞歸桂敛，我們給出Scheme中的遞歸寫法：
(define factorial
(lambda (n)
(if (= n 0)
1
(* n (factorial (- n 1))))))
(define fibonacci
(lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))))
其中關(guān)鍵字lambda, 表明我們定義的(即任何封閉的開括號立即離開λ及其相應(yīng)的關(guān)閉括號)是一個函數(shù)功炮。
Lambda演算和函數(shù)式語言的計(jì)算模型天生較為接近，Lambda表達(dá)式一般是這些語言必備的基本特性术唬。
Scheme是Lisp方言薪伏，遵循極簡主義哲學(xué)，有著獨(dú)特的魅力粗仓。Scheme的一個主要特性是可以像操作數(shù)據(jù)一樣操作函數(shù)調(diào)用嫁怀。
Y組合子(Y - Combinator)
在現(xiàn)代編程語言中，函數(shù)都是具名的借浊，而在傳統(tǒng)的Lambda Calculus中塘淑，函數(shù)都是沒有名字的。這樣就出現(xiàn)了一個問題 —— 如何在Lambda Calculus中實(shí)現(xiàn)遞歸函數(shù)蚂斤，即匿名遞歸函數(shù)存捺。Haskell B. Curry （編程語言 Haskell 就是以此人命名的）發(fā)現(xiàn)了一種不動點(diǎn)組合子 —— Y Combinator，用于解決匿名遞歸函數(shù)實(shí)現(xiàn)的問題曙蒸。Y 組合子(Y Combinator)捌治，其定義是：
Y = λf.(λx.f (x x)) (λx.f (x x))
對于任意函數(shù) g岗钩，可以通過推導(dǎo)得到Y g = g (Y g) (（高階）函數(shù)的不動點(diǎn) )，從而證明 λ演算 是 圖靈完備 的肖油。 Y 組合子 的重要性由此可見一斑凹嘲。
她讓人絞盡腦汁，也琢磨不定构韵！她讓人心力憔悴，又百般回味趋艘！
她疲恢，看似平淡，卻深藏玄機(jī)瓷胧！她显拳，貌不驚人，卻天下無敵搓萧！
她是誰杂数？她就是 Y 組合子：Y = λf.(λx.f (x x)) (λx.f (x x))，不動點(diǎn)組合子中最著名的一個瘸洛。
Y 組合子讓我們可以定義匿名的遞歸函數(shù)揍移。Y組合子是Lambda演算的一部分升略，也是函數(shù)式編程的理論基礎(chǔ)黍图。僅僅通過Lambda表達(dá)式這個最基本的 原子 實(shí)現(xiàn)循環(huán)迭代。Y 組合子本身是函數(shù)应又，其輸入也是函數(shù)（在 Lisp 中連程序都是函數(shù)）石蔗。
頗有道生一罕邀、一生二、二生三养距、三生萬物的韻味诉探。
舉個例子說明： 我們先使用類C語言中較為熟悉的JavaScript來實(shí)現(xiàn)一個Y組合子函數(shù)， 因?yàn)镴avaScript語言的動態(tài)特性棍厌，使得該實(shí)現(xiàn)相比許多需要聲明各種類型的語言要簡潔許多：
function Y(f) {
return (function (g) {
return g(g);
})(function (g) {
return f(function (x) {
return g(g)(x);
});
});
}
var fact = Y(function (rec) {
return function (n) {
return n == 0 ? 1 : n * rec(n - 1);
};
});
我們使用了Y函數(shù)組合一段匿名函數(shù)代碼肾胯，實(shí)現(xiàn)了一個匿名的遞歸階乘函數(shù)。
直接將這兩個函數(shù)放到瀏覽器的Console中去執(zhí)行定铜，我們將看到如下輸出：
fact(10)
3628800
這個Y函數(shù)相當(dāng)繞腦阳液。要是在Clojure（JVM上的Lisp方言）中，這個Y函數(shù)實(shí)現(xiàn)如下：
(defn Y [r]
((fn [f] (f f))
(fn [f]
(r (fn [x] ((f f) x))))))
使用Scheme語言來表達(dá)：
(define Y
(lambda (f)
((lambda (x) (f (lambda (y) ((x x) y))))
(lambda (x) (f (lambda (y) ((x x) y)))))))
我們可以看出揣炕，使用Scheme語言表達(dá)的Y組合子跟 原生的 λ演算 表達(dá)式基本一樣帘皿。
用CoffeeScript實(shí)現(xiàn)一個 Y combinator就長這樣：
coffee> Y = (f) -> ((x) -> (x x)) ((x) -> (f ((y) -> ((x x) y))))
[Function]
這個看起就相當(dāng)簡潔優(yōu)雅了。我們使用這個 Y combinator 實(shí)現(xiàn)一個匿名遞歸的Fibonacci函數(shù)：
coffee> fib = Y (f) -> (n) -> if n < 2 then n else f(n-1) + f(n-2)
[Function]
coffee> index = [0..10]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
coffee> index.map(fib)
[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]
實(shí)現(xiàn)一個匿名遞歸階乘函數(shù)：
coffee> fact = Y (f) ->(n) -> if n==0 then 1 else n*f(n-1)
[Function]
coffee> fact(10)
3628800
上面的Coffee代碼的命令行REPL運(yùn)行環(huán)境搭建非常簡單：
$ npm install -g coffee-script
$ coffee
coffee>
對CoffeeScript感興趣的讀者畸陡，可以參考：http://coffee-script.org/鹰溜。
但是虽填，這個Y組合子 要是 使用 OOP 語言編程范式， 就要顯得復(fù)雜許多曹动。為了更加深刻地認(rèn)識OOP 與 FP編程范式斋日，我們使用Java 8 以及 Kotlin 的實(shí)例來說明。這里使用Java給出示例的原因墓陈，是為了給出Kotlin與Java語言上的對比恶守，在下一章節(jié)中，我們將要學(xué)習(xí)Kotlin與Java的互操作贡必。
首先我們使用Java的匿名內(nèi)部類實(shí)現(xiàn)Y組合子 ：
package com.easy.kotlin;
/**
* Created by jack on 2017/7/9.
*/
public class YCombinator {
public static Lambda<Lambda> yCombinator(final Lambda<Lambda> f) {
return new Lambda<Lambda>() {
@Override
public Lambda call(Object input) {
final Lambda<Lambda> u = (Lambda<Lambda>)input;
return u.call(u);
}
}.call(new Lambda<Lambda>() {
@Override
public Lambda call(Object input) {
final Lambda<Lambda> x = (Lambda<Lambda>)input;
return f.call(new Lambda<Object>() {
@Override
public Object call(Object input) {
return x.call(x).call(input);
}
});
}
});
}
public static void main(String[] args) {
Lambda<Lambda> y = yCombinator(new Lambda<Lambda>() {
@Override
public Lambda call(Object input) {
final Lambda<Integer> fab = (Lambda<Integer>)input;
return new Lambda<Integer>() {
@Override
public Integer call(Object input) {
Integer n = Integer.parseInt(input.toString());
if (n < 2) {
return Integer.valueOf(1);
} else {
return n * fab.call(n - 1);
}
}
};
}
});
System.out.println(y.call(10));//輸出： 3628800
}
interface Lambda<E> {
E call(Object input);
}
}
這里定義了一個Lambda<E>類型兔港， 然后通過E call(Object input)方法實(shí)現(xiàn)自調(diào)用，方法實(shí)現(xiàn)里有多處轉(zhuǎn)型以及嵌套調(diào)用仔拟。邏輯比較繞衫樊，代碼可讀性也比較差。當(dāng)然利花，這個問題本身也比較復(fù)雜科侈。
我們使用Java 8的Lambda表達(dá)式來改寫下匿名內(nèi)部類：
package com.easy.kotlin;
/**
* Created by jack on 2017/7/9.
*/
public class YCombinator2 {
public static Lambda<Lambda> yCombinator2(final Lambda<Lambda> f) {
return ((Lambda<Lambda>)(Object input) -> {
final Lambda<Lambda> u = (Lambda<Lambda>)input;
return u.call(u);
}).call(
((Lambda<Lambda>)(Object input) -> {
final Lambda<Lambda> v = (Lambda<Lambda>)input;
return f.call((Lambda<Object>)(Object p) -> {
return v.call(v).call(p);
});
})
);
}
public static void main(String[] args) {
Lambda<Lambda> y2 = yCombinator2(
(Lambda<Lambda>)(Object input) -> {
Lambda<Integer> fab = (Lambda<Integer>)input;
return (Lambda<Integer>)(Object p) -> {
Integer n = Integer.parseInt(p.toString());
if (n < 2) {
return Integer.valueOf(1);
} else {
return n * fab.call(n - 1);
}
};
});
System.out.println(y2.call(10));//輸出： 3628800
}
interface Lambda<E> {
E call(Object input);
}
}
最后，我們使用Kotlin的對象表達(dá)式（順便復(fù)習(xí)回顧一下上一章節(jié)的相關(guān)內(nèi)容）實(shí)現(xiàn)Y組合子：
package com.easy.kotlin
/**
* Created by jack on 2017/7/9.
*
* lambda f. (lambda x. (f(x x)) lambda x. (f(x x)))
*
* OOP YCombinator
*
*/
object YCombinatorKt {
fun yCombinator(f: Lambda<Lambda<*>>): Lambda<Lambda<*>> {
return object : Lambda<Lambda<*>> {
override fun call(n: Any): Lambda<*> {
val u = n as Lambda<Lambda<*>>
return u.call(u)
}
}.call(object : Lambda<Lambda<*>> {
override fun call(n: Any): Lambda<*> {
val x = n as Lambda<Lambda<*>>
return f.call(object : Lambda<Any> {
override fun call(n: Any): Any {
return x.call(x).call(n)!!
}
})
}
}) as Lambda<Lambda<*>>
}
@JvmStatic fun main(args: Array<String>) {
val y = yCombinator(object : Lambda<Lambda<*>> {
override fun call(n: Any): Lambda<*> {
val fab = n as Lambda<Int>
return object : Lambda<Int> {
override fun call(n: Any): Int {
val n = Integer.parseInt(n.toString())
if (n < 2) {
return Integer.valueOf(1)
} else {
return n * fab.call(n - 1)
}
}
}
}
})
println(y.call(10)) //輸出： 3628800
}
interface Lambda<E> {
fun call(n: Any): E
}
}
使用 Kotlin FP 實(shí)現(xiàn) Y 組合子（Y-Combinator）
我們可以使用 Kotlin FP (Lambda, function) 寫一個 Y-combinator 函數(shù)嗎?
Y = λf.(λx.f (x x)) (λx.f (x x))
當(dāng)然炒事，對于函數(shù)式編程也完全支持的 Kotlin 也有 FP 風(fēng)格的Y 組合子實(shí)現(xiàn)：
/**
* Created by jack on 2017/7/9.
*
* lambda f. (lambda x. (f(x x)) lambda x. (f(x x)))
*
* FP YCombinator
*/
// 為了方便易懂臀栈，使用 X 用做函數(shù) (X)->Int 的別名
typealias X = (Int) -> Int
// G 遞歸引用 G 自己
interface G : Function1<G, X>
// create a fun G from lazy blocking
fun G(block: (G) -> X) = object : G {
// 調(diào)用函數(shù)自身 `block(g)` like as `g(g)`
override fun invoke(g: G) = block(g)
}
typealias F = Function1<X, X>
fun Y(f: F) = (fun(g: G) = g(g))(G { g -> f({ x -> g(g)(x) }) })
val fact = Y {
rec ->
{
n ->
if (n == 0) 1 else n * rec(n - 1)
}
}
val fib = Y { f ->
{
n ->
if (n == 1 || n == 2) 1 else f(n - 1) + f(n - 2)
}
}
fun main(args: Array<String>) {
println(fact(10))
println(fib(10))
for (i in 1..10) {
println("$i!= ${fact(i)}")
}
for (i in 1..10) {
println("fib($i) = ${fib(i)}")
}
}
其中，在接口 G 繼承了Function1<G, X>接口：
interface G : Function1<G, X>
這個Function1 接口是繼承自kotlin.Function 接口：
public interface Function<out R>
Function1 有一個抽象算子函數(shù)invoke 挠乳， 用來調(diào)用入?yún)? p1 ：
public interface Function1<in P1, out R> : kotlin.Function<R> {
public abstract operator fun invoke(p1: P1): R
}
我們定義的 G 函數(shù)挂脑，入?yún)⑹莃lock函數(shù) (G) -> X , block函數(shù)的入?yún)⒂质?G 類型，通過 invoke 函數(shù)來實(shí)現(xiàn) 調(diào)用自身：
fun G(block: (G) -> X) = object : G {
// 調(diào)用函數(shù)自身 `block(g)` like as `g(g)`
override fun invoke(g: G) = block(g)
}
這樣欲侮，我們就可以實(shí)現(xiàn)一個 Y 組合子函數(shù)了：
typealias F = Function1<X, X>
fun Y(f: F) = (fun(g: G) = g(g))(G { g -> f({ x -> g(g)(x) }) })
我們通過 Y 組合子定義階乘遞歸函數(shù)和 Fibonacci 數(shù)列函數(shù)：
val fact = Y {
rec ->
{
n ->
if (n == 0) 1 else n * rec(n - 1)
}
}
val fib = Y { f ->
{
n ->
if (n == 1 || n == 2) 1 else f(n - 1) + f(n - 2)
}
}
測試代碼：
fun main(args: Array<String>) {
val square: X = { x -> x * x }
println(square(9))
println(fact(10))
println(fib(10))
for (i in 1..10) {
println("$i!= ${fact(i)}")
}
for (i in 1..10) {
println("fib($i) = ${fib(i)}")
}
}
【 Github 源碼工程： https://github.com/EasyKotlin/chapter8_fp 】
關(guān)于Y combinator的更多實(shí)現(xiàn)崭闲，可以參考：https://gist.github.com/Jason-Chen-2017/88e13b63fa5b7c612fddf999739964b0 ； 另外威蕉，關(guān)于Y combinator的原理介紹刁俭，推薦看《The Little Schemer 》這本書。
從上面的例子韧涨，我們可以看出OOP中的對接口以及多態(tài)類型牍戚，跟FP中的函數(shù)的思想表達(dá)的，本質(zhì)上是一個東西虑粥，這個東西到底是什么呢如孝？我們姑且稱之為“編程之道”罷！
Y combinator 給我們提供了一種方法娩贷，讓我們在一個只支持first-class函數(shù)第晰，但是沒有內(nèi)建遞歸的編程語言里完成遞歸。所以Y combinator給我們展示了一個語言完全可以定義遞歸函數(shù)，即使這個語言的定義一點(diǎn)也沒提到遞歸茁瘦。它給我們展示了一件美妙的事：僅僅函數(shù)式編程自己品抽，就可以讓我們做到我們從來不認(rèn)為可以做到的事（而且還不止這一個例子）。
嚴(yán)謹(jǐn)而精巧的lambda演算體系甜熔，從最基本的概念“函數(shù)”入手圆恤，創(chuàng)造出一個絢爛而宏偉的世界，這不能不說是人類思維的驕傲腔稀。
沒有"副作用"
所謂"副作用"（side effect）盆昙，指的是函數(shù)內(nèi)部與外部互動（最典型的情況，就是修改全局變量的值）焊虏，產(chǎn)生運(yùn)算以外的其他結(jié)果弱左。
函數(shù)式編程強(qiáng)調(diào)沒有"副作用"，意味著函數(shù)要保持獨(dú)立炕淮，所有功能就是返回一個新的值，沒有其他行為跳夭，尤其是不得修改外部變量的值涂圆。
函數(shù)式編程的動機(jī)，一開始就是為了處理運(yùn)算（computation）币叹，不考慮系統(tǒng)的讀寫（I/O）润歉。"語句"屬于對系統(tǒng)的讀寫操作，所以就被排斥在外颈抚。
當(dāng)然踩衩，實(shí)際應(yīng)用中，不做I/O是不可能的贩汉。因此驱富，編程過程中，函數(shù)式編程只要求把I/O限制到最小匹舞，不要有不必要的讀寫行為褐鸥，保持計(jì)算過程的單純性。
函數(shù)式編程只是返回新的值赐稽，不修改系統(tǒng)變量叫榕。因此，不修改變量姊舵，也是它的一個重要特點(diǎn)晰绎。
在其他類型的語言中，變量往往用來保存"狀態(tài)"（state）括丁。不修改變量荞下，意味著狀態(tài)不能保存在變量中。函數(shù)式編程使用參數(shù)保存狀態(tài)，最好的例子就是遞歸锄弱。
引用透明性
函數(shù)程序通常還加強(qiáng)引用透明性考蕾，即如果提供同樣的輸入，那么函數(shù)總是返回同樣的結(jié)果会宪。就是說肖卧，表達(dá)式的值不依賴于可以改變值的全局狀態(tài)。這樣我們就可以從形式上邏輯推斷程序行為掸鹅。因?yàn)楸磉_(dá)式的意義只取決于其子表達(dá)式而不是計(jì)算順序或者其他表達(dá)式的副作用塞帐。這有助于我們來驗(yàn)證代碼正確性、簡化算法巍沙，有助于找出優(yōu)化它的方法葵姥。
Kotlin 開發(fā)者社區(qū)
國內(nèi)第一Kotlin 開發(fā)者社區(qū)公眾號，主要分享句携、交流 Kotlin 編程語言榔幸、Spring Boot、Android矮嫉、React.js/Node.js削咆、函數(shù)式編程、編程思想等相關(guān)主題蠢笋。
