概論

在過去的近十年的時間里动猬，面向?qū)ο缶幊檀笮衅涞馈Ｒ灾劣谠诖髮W的教育里涝影，老師也只會教給我們兩種編程模型枣察，面向過程和面向?qū)ο蟆?/p>

孰不知，在面向?qū)ο螽a(chǎn)生之前燃逻，在面向?qū)ο笏枷氘a(chǎn)生之前序目，函數(shù)式編程已經(jīng)有了數(shù)十年的歷史。

那么伯襟，接下來猿涨，就讓我們回顧這個古老又現(xiàn)代的編程模型，讓我們看看究竟是什么魔力將這個概念姆怪，將這個古老的概念叛赚，在21世紀的今天再次拉入了我們的視野。

什么是函數(shù)式編程

在維基百科中稽揭，已經(jīng)對函數(shù)式編程有了很詳細的介紹俺附。

那我們就來摘取一下Wiki上對Functional Programming的定義：

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data.

簡單地翻譯一下，也就是說函數(shù)式編程是一種編程模型溪掀，他將計算機運算看做是數(shù)學中函數(shù)的計算事镣，并且避免了狀態(tài)以及變量的概念。

接下來揪胃，我們就來剖析下函數(shù)式編程的一些特征璃哟。

從并發(fā)說開來

說來慚愧，我第一個真正接觸到函數(shù)式編程喊递，要追溯到兩年以前的《Erlang程序設計》随闪，我們知道Erlang是一個支持高并發(fā)，有著強大容錯性的函數(shù)式編程語言骚勘。

因為時間太久了铐伴，而且一直沒有過真正地應用，所以對Erlang也只是停留在一些感性認識上。在我眼里盛杰，Erlang對高并發(fā)的支持體現(xiàn)在兩方面挽荡，第一藐石，Erlang對輕量級進程的支持（請注意此處進程并不等于操作系統(tǒng)的進程即供，而只是Erlang內(nèi)部的一個單位單元），第二于微，就是變量的不變性逗嫡。

變量的不變性

在《Erlang程序設計》一書中，對變量的不變性是這樣說的株依，Erlang是目前唯一變量不變性的語言驱证。具體的話我記不清了，我不知道是老爺子就是這么寫的恋腕，還是譯者的問題抹锄。我在給這本書寫書評的時候吹毛求疵地說：

我對這句話有異議，切不說曾經(jīng)的Lisp荠藤，再到如今的F#都對賦值操作另眼相看伙单，低人一等。單說如今的Java和C#哈肖，提供的final和readonly一樣可以支持變量的不變性吻育，而這個唯一未免顯得有點太孤傲了些。

讓我們先來看兩段程序淤井，首先是我們常見的一種包含賦值的程序：

class Account:
def init(self,balance):
self.balance = balance
def desposit(self,amount):
self.balance = self.balance + amount
return self.balance
def despositTwice(self):
self.balance = self.balance * 2
return self.balance

if name == 'main':
account = Account(100)
print(account.desposit(10))
print(account.despositTwice())

這段程序本身是沒有問題的布疼，但是我們考慮這樣一種情況，現(xiàn)在有多個進程在同時跑這一個程序，那么程序就會被先desposit 還是先 despositTwice所影響。

但是如果我們采用這樣的方式：

def makeAccount(balance):
global desposit
global despositTwice
def desposit(amount):
result = balance + amount
return result
def despositTwice():
result = balance * 2
return result
def dispatch(method):
return eval(method)
return dispatch

if name == 'main':
handler = makeAccount(100)
print(handler('desposit')(10))
print(handler('despositTwice')())

這時我們就會發(fā)現(xiàn)搔啊，無論多少個進程在跑返敬，因為我們本身沒有賦值操作，所以都不會影響到我們的最終結果连霉。

但是這樣也像大家看到的一樣，采用這樣的方式?jīng)]有辦法保持狀態(tài)。

這也就是我們在之前概念中看到的無狀態(tài)性轰坊。

再看函數(shù)式編程的崛起

既然已經(jīng)看完了函數(shù)式編程的基本特征，那就讓我們來想想數(shù)十年后函數(shù)式編程再次崛起的幕后原因祟印。

一直以來肴沫，作為函數(shù)式編程代表的Lisp，還是Haskell蕴忆，更多地都是在大學中颤芬，在實驗室中應用，而很少真的應用到真實的生產(chǎn)環(huán)境。

先讓我們再來回顧一下偉大的摩爾定律：

1站蝠、集成電路芯片上所集成的電路的數(shù)目汰具，每隔18個月就翻一番。

2菱魔、微處理器的性能每隔18個月提高一倍留荔，而價格下降一半。

3澜倦、用一個美元所能買到的電腦性能聚蝶，每隔18個月翻兩番。

一如摩爾的預測藻治，整個信息產(chǎn)業(yè)就這樣飛速地向前發(fā)展著碘勉，但是在近年，我們卻可以發(fā)現(xiàn)摩爾定律逐漸地失效了桩卵，芯片上元件的尺寸是不可能無限地縮小的验靡，這就意味著芯片上所能集成的電子元件的數(shù)量一定會在某個時刻達到一個極限。那么當技術達到這個極限時雏节，我們又該如何適應日益增長的計算需求胜嗓，電子元件廠商給出了答案，就是多核矾屯。

多核并行程序設計就這樣被推到了前線兼蕊，而命令式編程天生的缺陷卻使并行編程模型變得非常復雜，無論是信號量件蚕，還是鎖的概念孙技，都使程序員不堪其重。

就這樣排作，函數(shù)式編程終于在數(shù)十年后牵啦，終于走出實驗室，來到了真實的生產(chǎn)環(huán)境中妄痪，無論是冷門的Haskell哈雏，Erlang，還是Scala衫生，F(xiàn)#裳瘪，都是函數(shù)式編程成功的典型。

函數(shù)式編程的第一型

我們知道罪针，對象是面向?qū)ο蟮牡谝恍团砀敲春瘮?shù)式編程也是一樣，函數(shù)是函數(shù)式編程的第一型泪酱。

我們在函數(shù)式編程中努力用函數(shù)來表達所有的概念派殷，完成所有的操作还最。

在面向?qū)ο缶幊讨校覀儼褜ο髠鱽韨魅フ毕В窃诤瘮?shù)式編程中拓轻，我們要做的是把函數(shù)傳來傳去，而這個经伙，說成術語扶叉，我們把他叫做高階函數(shù)。

那我們就來看一個高階函數(shù)的應用橱乱，熟悉js的同學應該對下面的代碼很熟悉辜梳，讓哦我們來寫一個在電子電路中常用的濾波器的示例代碼粱甫。

def Filt(arr,func):
result = []
for item in arr:
result.append(func(item))
return result

def MyFilter(ele):
if ele < 0 :
return 0
return ele

if name == 'main':
arr = [-5,3,5,11,-45,32]
print('%s' % (Filt(arr,MyFilter)))

哦泳叠，之前忘記了說，什么叫做高階函數(shù)茶宵，我們給出定義：

在數(shù)學和計算機科學中危纫，高階函數(shù)是至少滿足下列一個條件的函數(shù):

• 接受一個或多個函數(shù)作為輸入
• 輸出一個函數(shù)

那么，毫無疑問上面的濾波器乌庶，就是高階函數(shù)的一種應用种蝶。

在函數(shù)式編程中，函數(shù)是基本單位瞒大，是第一型螃征，他幾乎被用作一切，包括最簡單的計算透敌，甚至連變量都被計算所取代盯滚。在函數(shù)式編程中，變量只是一個名稱酗电，而不是一個存儲單元魄藕，這是函數(shù)式編程與傳統(tǒng)的命令式編程最典型的不同之處。

讓我們看看撵术，變量只是一個名稱背率，在上面的代碼中，我們可以這樣重寫主函數(shù)：

if name == 'main':
arr = [-5,3,5,11,-45,32]
func = MyFilter
print('%s' % (Filt(arr,func)))

當然嫩与，我們還可以把程序更精簡一些寝姿，利用函數(shù)式編程中的利器，map,filter和reduce :

if name == 'main':
arr = [-5,3,5,11,-45,32]
print('%s' % (map(lambda x : 0 if x<0 else x ,arr)))

這樣看上去是不是更賞心悅目呢划滋？

這樣我們就看到了饵筑，函數(shù)是我們編程的基本單位。

函數(shù)式編程的數(shù)學本質(zhì)

忘了是誰說過：一切問題古毛，歸根結底到最后都是數(shù)學問題翻翩。

編程從來都不是難事兒都许，無非是細心，加上一些函數(shù)類庫的熟悉程度嫂冻，加上經(jīng)驗的堆積胶征，而真正困難的，是如何把一個實際問題桨仿，轉(zhuǎn)換成一個數(shù)學模型睛低。這也是為什么微軟，Google之類的公司重視算法服傍，這也是為什么數(shù)學建模大賽在大學計算機系如此被看重的原因钱雷。

先假設我們已經(jīng)憑借我們良好的數(shù)學思維和邏輯思維建立好了數(shù)學模型，那么接下來要做的是如何把數(shù)學語言來表達成計算機能看懂的程序語言吹零。

這里我們再看在第四節(jié)中罩抗，我們提到的賦值模型，同一個函數(shù)灿椅，同一個參數(shù)套蒂，卻會在不同的場景下計算出不同的結果，這是在數(shù)學函數(shù)中完全不可能出現(xiàn)的情況茫蛹，f(x) = y 操刀，那么這個函數(shù)無論在什么場景下，都會得到同樣的結果婴洼，這個我們稱之為函數(shù)的確定性骨坑。

這也是賦值模型與數(shù)學模型的不兼容之處。而函數(shù)式編程取消了賦值模型柬采，則使數(shù)學模型與編程模型完美地達成了統(tǒng)一欢唾。

函數(shù)式編程的抽象本質(zhì)

相信每個程序員都對抽象這個概念不陌生。

在面向?qū)ο缶幊讨芯唬覀冋f匈辱，類是現(xiàn)實事物的一種抽象表示。那么抽象的最大作用在我看來就在于抽象事物的重用性杀迹，一個事物越具體亡脸，那么他的可重用性就越低，因此树酪，我們再打造可重用性代碼浅碾，類，類庫時续语，其實在做的本質(zhì)工作就在于提高代碼的抽象性垂谢。而再往大了說開來，程序員做的工作疮茄，就是把一系列過程抽象開來滥朱，反映成一個通用過程根暑，然后用代碼表示出來。

在面向?qū)ο笾嗅懔冢覀儼咽挛锍橄笈畔印６诤瘮?shù)式編程中，我們則是在將函數(shù)方法抽象缰犁，第六節(jié)的濾波器已經(jīng)讓我們知道淳地，函數(shù)一樣是可重用，可置換的抽象單位帅容。

那么我們說函數(shù)式編程的抽象本質(zhì)則是將函數(shù)也作為一個抽象單位颇象，而反映成代碼形式，則是高階函數(shù)并徘。

狀態(tài)到底怎么辦

我們說了一大堆函數(shù)式編程的特點遣钳，但是我們忽略了，這些都是在理想的層面饮亏，我們回頭想想第四節(jié)的變量不變性耍贾，確實，我們說路幸，函數(shù)式編程是無狀態(tài)的，可是在我們現(xiàn)實情況中付翁，狀態(tài)不可能一直保持不變简肴，而狀態(tài)必然需要改變，傳遞百侧，那么我們在函數(shù)式編程中的則是將其保存在函數(shù)的參數(shù)中砰识，作為函數(shù)的附屬品來傳遞。

ps：在Erlang中佣渴，進程之間的交互傳遞變量是靠“信箱”的收發(fā)信件來實現(xiàn)辫狼，其實我們想一想，從本質(zhì)而言辛润，也是將變量作為一個附屬品來傳遞么膨处！

我們來看個例子，我們在這里舉一個求x的n次方的例子砂竖，我們用傳統(tǒng)的命令式編程來寫一下：

def expr(x,n):
result = 1
for i in range(1,n+1):
result = result * x
return result

if name == 'main':
print(expr(2,5))

這里真椿，我們一直在對result變量賦值，但是我們知道乎澄，在函數(shù)式編程中的變量是具有不變性的突硝，那么我們?yōu)榱吮３謗esult的狀態(tài)，就需要將result作為函數(shù)參數(shù)來傳遞以保持狀態(tài)：

def expr(num,n):
if n==0:
return 1
return num*expr(num,n-1)

if name == 'main':
print(expr(2,5))

呦置济，這不是遞歸么解恰！

函數(shù)式編程和遞歸

遞歸是函數(shù)式編程的一個重要的概念锋八，循環(huán)可以沒有，但是遞歸對于函數(shù)式編程卻是不可或缺的护盈。

在這里查库，我得承認，我確實不知道我該怎么解釋遞歸為什么對函數(shù)式編程那么重要黄琼。我能想到的只是遞歸充分地發(fā)揮了函數(shù)的威力樊销，也解決了函數(shù)式編程無狀態(tài)的問題。（如果大家有其他的意見脏款，請賜教）

遞歸其實就是將大問題無限地分解围苫，直到問題足夠小。

而遞歸與循環(huán)在編程模型和思維模型上最大的區(qū)別則在于：

循環(huán)是在描述我們該如何地去解決問題撤师。

遞歸是在描述這個問題的定義剂府。

那么就讓我們以斐波那契數(shù)列為例來看下這兩種編程模型。

先說我們最常見的遞歸模型剃盾，這里腺占，我不采用動態(tài)規(guī)劃來做臨時狀態(tài)的緩存，只是說這種思路：

def Fib(a):
if a==0 or a==1:
return 1
else:
return Fib(a-2)+Fib(a-1)

遞歸是在描述什么是斐波那契數(shù)列痒谴，這個數(shù)列的定義就是一個數(shù)等于他的前兩項的和衰伯，并且已知Fib(0)和Fib(1)等于1。而程序則是用計算機語言來把這個定義重新描述了一次积蔚。

那接下來意鲸，我們看下循環(huán)模型：

def Fib(n):
a=1
b=1
n = n - 1
while n>0:
temp=a
a=a+b
b=temp
n = n-1
return b

這里則是在描述我們該如何求解斐波那契數(shù)列，應該先怎么樣再怎么樣尽爆。

而我們明顯可以看到怎顾，遞歸相比于循環(huán)，具有著更加良好的可讀性漱贱。

但是槐雾，我們也不能忽略，遞歸而產(chǎn)生的StackOverflow幅狮，而賦值模型呢募强？我們懂的，函數(shù)式編程不能賦值彪笼，那么怎么辦钻注？

尾遞歸，偽遞歸

我們之前說到了遞歸和循環(huán)各自的問題配猫，那怎么來解決這個問題幅恋，函數(shù)式編程為我們拋出了答案，尾遞歸泵肄。

什么是尾遞歸捆交，用最通俗的話說：就是在最后一部單純地去調(diào)用遞歸函數(shù)淑翼，這里我們要注意“單純”這個字眼。

那么我們說下尾遞歸的原理品追，其實尾遞歸就是不要保持當前遞歸函數(shù)的狀態(tài)玄括，而把需要保持的東西全部用參數(shù)給傳到下一個函數(shù)里，這樣就可以自動清空本次調(diào)用的椚馔撸空間遭京。這樣的話，占用的椗⒗颍空間就是常數(shù)階的了哪雕。

在看尾遞歸代碼之前，我們還是先來明確一下遞歸的分類鲫趁，我們將遞歸分成“樹形遞歸”和“尾遞歸”斯嚎，什么是樹形遞歸，就是把計算過程逐一展開挨厚，最后形成的是一棵樹狀的結構堡僻，比如之前的斐波那契數(shù)列的遞歸解法。

那么我們來看下斐波那契尾遞歸的寫法：

def Fib(a,b,n):
if n==0:
return b
else:
return Fib(b,a+b,n-1)

這里看上去有些難以理解疫剃，我們來解釋一下：傳入的a和b分別是前兩個數(shù)钉疫，那么每次我都推進一位，那么b就變成了第一個數(shù)慌申，而a+b就變成的第二個數(shù)陌选。

這就是尾遞歸。其實我們想一想蹄溉，這不是在描述問題，而是在尋找一種問題的解決方案您炉，和上面的循環(huán)有什么區(qū)別呢柒爵？我們來做一個從尾遞歸到循環(huán)的轉(zhuǎn)換把！

最后返回b是把赚爵，那我就先聲明了棉胀，b=0

要傳入a是把，我也聲明了冀膝，a=1

要計算到n==0是把唁奢，還是循環(huán)while n!=0

每一次都要做一個那樣的計算是吧，我用臨時變量交換一下窝剖。temp=b ; b=a+b;a=temp麻掸。

那么按照這個思路一步步轉(zhuǎn)換下去，是不是就是我們在上面寫的那段循環(huán)代碼呢赐纱？

那么這個尾遞歸脊奋，其實本質(zhì)上就是個“偽遞歸”熬北，您說呢？

既然我們可以優(yōu)化诚隙，對于大多數(shù)的函數(shù)式編程語言的編譯器來說讶隐，他們對尾遞歸同樣提供了優(yōu)化，使尾遞歸可以優(yōu)化成循環(huán)迭代的形式久又，使其不會造成堆棧溢出的情況巫延。

惰性求值與并行

第一次接觸到惰性求值這個概念應該是在Haskell語言中，看一個最簡單的惰性求值地消，我覺得也是最經(jīng)典的例子：

在Haskell里炉峰，有個repeat關鍵字，他的作用是返回一個無限長的List犯建，那么我們來看下：

take 10 (repeat 1)

就是這句代碼讲冠，如果沒有了惰性求值，我想這個進程一定會死在那里适瓦，可是結果卻是很正常竿开，返回了長度為10的List，List里的值都是1玻熙。這就是惰性求值的典型案例否彩。

我們看這樣一段簡單的代碼：

def getResult():
a = getA() //Take a long time
b = getB() //Take a long time
c = a + b

這段代碼本身很簡單，在命令式程序設計中嗦随，編譯器（或解釋器）會做的就是逐一解釋代碼列荔，按順序求出a和b的值，然后再求出c枚尼。

可是我們從并行的角度考慮贴浙，求a的值是不是可以和求b的值并行呢？也就是說署恍，直到執(zhí)行到a+b的時候我們編譯器才意識到a和b直到現(xiàn)在才需要崎溃，那么我們雙核處理器就自然去發(fā)揮去最大的功效去計算了呢！

這才是惰性求值的最大威力盯质。

當然袁串，惰性求值有著這樣的優(yōu)點也必然有著缺點，我記得我看過一個例子是最經(jīng)典的：

def Test():
print('Please enter a number:')
a = raw_input()

可是這段代碼如果惰性求值的話呼巷，第一句話就不見得會在第二句話之前執(zhí)行了囱修。

函數(shù)式編程總覽

我們看完了函數(shù)式編程的特點，我們想想函數(shù)式編程的應用場合王悍。

數(shù)學推理

并行程序

那么我們總體地說破镰，其實函數(shù)式編程最適合地還是解決局部性的數(shù)學小問題，要讓函數(shù)式編程來做CRUD，來做我們傳統(tǒng)的邏輯性很強的Web編程啤咽，就有些免為其難了晋辆。

就像如果要用Scala完全取代今天的Java的工作，我想恐怕效果會很糟糕宇整。而讓Scala來負責底層服務的編寫瓶佳，恐怕再合適不過了。

而在一種語言中融入多種語言范式鳞青，最典型的C#霸饲。在C# 3.0中引入Lambda表達式，在C# 4.0中引入聲明式編程臂拓，我們某些人在嘲笑C#越來越臃腫的同時厚脉，卻忽略了，這樣的語法糖胶惰，帶給我們的不僅僅是代碼書寫上的遍歷傻工，更重要的是編程思維的一種進步。

好吧孵滞，那就讓我們忘記那些C#中Lambda背后的實現(xiàn)機制中捆，在C#中，還是在那些更純粹地支持函數(shù)式編程的語言中坊饶，盡情地去體驗函數(shù)式編程帶給我們的快樂把泄伪！

總結

又翻閱了數(shù)學和計算機科學分別對函數(shù)和高階函數(shù)的定義，還有并行計算的map,reduce,結合最近翻看python的裝飾器匿级，講的真是不錯蟋滴。python的靈活性弱類型，真的非常適合學習和理解函數(shù)式痘绎。java理解起來是真的費勁津函。原因就在于高階函數(shù)的定義。函數(shù)式是把變量替換成函數(shù)計算孤页。變量在面向過程和對象編程思想中用來做存儲單元球散，保存狀態(tài)。函數(shù)式完全就是無狀態(tài)的散庶，就是沒有變量概念。因為變量就是計算凌净，就是函數(shù)悲龟，換句話說，形參變成了函數(shù)冰寻！java可以把形參须教，比如完全傳一個方法嗎？不可以。那怎么間接實現(xiàn)函數(shù)式轻腺，滿足高級函數(shù)定義呢乐疆？很簡單。傳類的實例贬养，因為我們可以把方法定義在類里面挤土。這樣也就相當于傳進去了方法。只不過方法在java中無法單獨以對象形式出現(xiàn)误算。但python可以仰美。python是純粹的OOP，任何東西都是對象儿礼。因此python來寫函數(shù)式咖杂，理解函數(shù)式真的是通俗易懂。不用看rxjava源碼蚊夫，一定是我剛才說的诉字，無法把一個類的方法直接當做參數(shù)傳給某個方法，只能間接用對象啊知纷，用類（反射）去實現(xiàn)方法的調(diào)用壤圃。在數(shù)學和計算機科學中，高階函數(shù)是至少滿足下列一個條件的函數(shù):
接受一個或多個函數(shù)作為輸入
輸出一個函數(shù)
在函數(shù)式編程中屈扎，函數(shù)是基本單位埃唯，是第一型，他幾乎被用作一切鹰晨，包括最簡單的計算墨叛，甚至連變量都被計算所取代。在函數(shù)式編程中模蜡，變量只是一個名稱漠趁，而不是一個存儲單元，這是函數(shù)式編程與傳統(tǒng)的命令式編程最典型的不同之處忍疾。