為什麼要學習函數式編程？因為如果你手裡只有鎚子，看什麼都像釘子
來自專欄 我是程序員
摘要：函數式編程是一種「編程範式」，也就是如何編寫程序的方法論，其主要思想是把運算過程盡量寫成一系列嵌套的函數調用。那麼在函數式編程比較火爆的今天，我們為什麼要學習它呢？學習函數式編程究竟能為我們帶來什麼呢？本文或許能給你一點啟發。
視頻回顧地址：http://click.aliyun.com/m/49209/
PPT下載地址：http://click.aliyun.com/m/49210/演講嘉賓簡介
陶雲峰，阿里雲高級技術專家，上海交通大學理論計算機科學博士，專註數據存儲、分散式系統與計算等領域，寫了20多年程序。2000年參加ACM/ICPC大賽，實現亞洲隊伍進World Final前十的突破。以下內容根據演講視頻以及PPT整理而成。
首先實現一個sum函數，在sum函數中傳入一個vector<int>，sum所做的工作就是將vector<int>裡面的int通過累加器加到一起並返回。
可以看到上述所做的累加器、累乘器以及字元串拼接函數都具有相同的結構，那麼需要思考如何將其抽象出來。從面向對象的角度來講，這就是一個策略模式，需要將策略和執行策略的上下文分離開，從函數式編程的角度來講，可以通過reduce函數來抽象代碼結構。
在下列示例代碼中定義了一個樹形結構，每個樹節點上面都有整數值mPayload，並且還有零到若干個子樹可以放到vector裡面。現在想要將這顆樹上所有節點的值全部加到一起，根據上述的做法可以知道，在實現時可以使用一個reduceTree。reduceTree同樣接受三個參數，reduce用的函數、初始值和樹的根節點。整個過程大致就是將累積變數定義好，將根節點的mPayload作用上去，然後將每個子樹reduce好的結果作用到累積器上。此時想要實現樹上節點的值全部加在一起的sum可以通過在累積函數參數上傳遞一個加法，初始值傳遞一個0即可。
牛頓-拉夫森迭代
平方根有很多種演算法，其中一種就是牛頓-拉夫森迭代，這種方法是一種非常高效的迭代方法。其大致就是如果想要對於x求平方根，那麼可以根據迭代的前一項使用這個公式演算法來得到後一項。如下代碼所實現的就是牛頓-拉夫森迭代，所傳入的兩個參數分別是所要求平方根的數值和所要誤差。在代碼中首先定義一個初始值，每次使用牛頓-拉夫森公式計算下一個值，如果前後兩個值的偏差小於傳入的要求誤差就可以返回當前值，否則當前值就變成下一個值繼續進行下一次迭代。
求導數其實就是不停地求斜率，當h逼近0的時候，斜率也就逼近f(x)的導數了。在代碼實現中，參數分別是需要求導的函數、函數求導的位置以及誤差。h從1.0開始，每一次都會折半，比較當前的斜率和下一次的斜率，如果前後兩個斜率誤差足夠小，結果就可以返回了，否則就繼續執行。
這樣大家就會發現求導數和牛頓-拉夫森迭代演算法都有相同的結構，總體而言，就是都有一個循環迭代，另外循環的終止條件都是由誤差決定的。兩者的細微差別就是牛頓-拉夫森迭代演算法的迭代變數最終返回的結果就是給用戶看到的結果，而求導數的迭代變數是h，最終看到是使用h計算出的斜率，而不是h本身。那麼如何抽象上述兩個演算法呢？
方案一
下面定義了within1函數，其參數分別是誤差和所要傳遞的表觀函數和狀態轉移函數。每一次迭代中，狀態轉移函數負責將當前這個狀態變成下一個狀態，而表觀函數則負責將狀態轉化成用戶需要看到的值，最後利用用戶需要看到的前後兩個值的差來判斷其誤差，如果誤差足夠小就返回，否則就繼續迭代。
對於牛頓-拉夫森迭代來講，其狀態轉移函數就直接使用牛頓-拉夫森函數即可，其表觀函數實際上則不需要，這裡可以放置一個恆等函數，輸入什麼就輸出返回什麼。
對於求導數而言，狀態轉移函數就是每次取半，表觀函數就是求斜率。這裡的示例代碼中之所以使用的"sin_"是因為sin()函數是一個重載的函數，其有多重重載方案，所以如果在調用時直接寫"sin"，編譯器無法知道重載哪一個版本，這也是重載函數不如模板特化函數的一點，所以重載函數需要做一個lambda表達式將其包進裡面，通過輸入的類型為double的x告訴編譯器要使用double版本的sin()函數。
從面相對象的角度來講，方案一的within1函數實際上是一個strategy pattern，配合轉移和表觀兩個strategy。其可以有一些擴展，比如內部狀態不一定是double，在設計模式中有一個叫做memento pattern，當然對於C++而言可以使用模板。如果狀態轉移和表觀這兩件事情緊耦合，可以使用抽象工廠模式，如果狀態轉移和表觀是松耦合的，則可以使用原型模式。那麼是不是這樣就足夠好了呢？其實並不是的，可以看到無論哪些模式用上去都是比較複雜的，沒有within1函數這麼簡潔。而within1函數簡潔的核心之處就在於其使用了高階函數。那麼是不是within1就是最好的方法呢？也不是的，函數式編程又提供了另外一種思考的角度。
方案二
在函數式編程中，可以將牛頓-拉夫森迭代視作一個無限長的序列，再截斷不需要的尾巴。而問題是計算機資源是有限的，不可能計算出一個無限長的序列，所以需要Lazy sequence。Lazy sequence邏輯上是一個無限長的序列，但是其元素只有需要的時候才會實際產生出來。在函數式編程中，Lazy sequence就是一個有狀態但是無參數的函數，每一次調用都會返回當前的狀態並將自己的狀態遷移到下一個。下列代碼中使用了值捕獲，產生一個內部狀態，並且加上mutable使得內部狀態可以被改變。
此外還需要進行截斷，需要遍歷Lazy sequence，並在遍歷過程中截斷，這也是下列代碼中within2所做的事情，每次迭代都會取一個值，當前一個值和後一個值的誤差足夠小之後就結束。
牛頓-拉夫森迭代演算法就可以變成如下代碼的形式，函數傳遞一個x並傳遞一個誤差值，每次向下走的時候就是牛頓-拉夫森迭代，這裡捕獲的就是x，然後產生一個無限長的序列，把序列和誤差精度傳入到within2函數中去。
在這樣的方案中應該如何計算導數呢？大家可以重新看一下求導數的公式，這裡的limit記號所代表的是有一個h接近0無限序列，對這個序列求出了一個斜率的序列，當h逼近0的時候，斜率也會逼近一個值，也就是所需要的導函數。從實現的角度而言，將極限逼近的過程視作一個無限長的序列。將一個無限長序列變換到另一個無限長的序列，也就是從h的序列變成斜率的序列，然後截斷。其核心就是將一個無限長序列變換到另一個無限長的序列，也就是map所實現的。在函數式編程的語境下面，map就是把一個序列變換成另外一個序列，這與過程式編程中的數據結構map是不同的。對於map而言，其結果仍然是一個無限長的序列，所以其也是一個無參數但是有內部狀態的函數，其接受一個變換的函數和無限長序列，並返回一個函數。該函數無參數，其所作的事情就是將輸入的序列取一個值，把函數作用上去之後返回。
在方案二裡面的實現求導數如下所示，首先每次將h取半，通過迭代得到一個無限長的序列seq，然後切斜率函數將其作用在原來的無限長序列上面得到另一個無限長序列，然後使用eps誤差進行截斷。代碼的實現是相當直白的，基本上就是按照limit記號來寫的。
在這個方案中引入了一個無限長序列的概念，而無限長序列在計算機中是無法實現的，所以將其轉換成了一個Lazy sequence，除了與業務相關within2函數中的誤差屬於業務概念外，iterate和map都不是業務的概念。方案二中引入的新增概念就是Lazy sequence和within2，所以方案二比方案一更為直觀，需要引入更少的概念，不需要表觀和轉移，尤其是對於牛頓-拉夫森迭代演算法這樣的情況，在方案一牛頓-拉夫森迭代演算法的表觀函數就是一個恆等函數，演算法本身不需要表觀概念，但是為了套在within1框架中，所以強制搞出來一個表觀函數，而在方案二中卻是不需要的。總而言之就是方案二比方案一代碼實現更簡潔，更貼近業務。
總結
總結而言，在本次分享中主要介紹了以下四點：
1. 高階函數。函數可以作為參數，也可以作為返回值。
2. Lazy sequence。邏輯上的無限長序列，實現中是一個有狀態無參數的函數。
3. 新的「膠水」。函數式編程提供了新的建模思路，新的膠合代碼組件的方法。「膠水」不同，分解問題的方式也不同。
4. 「沒有銀彈」。如果你手裡只有鎚子，看什麼都像釘子。學習函數式編程是為了豐富你的武器庫。
原文鏈接：http://click.aliyun.com/m/49211/
更多技術乾貨敬請關注云棲社區知乎機構號：阿里云云棲社區 - 知乎
本文為雲棲社區原創內容，未經允許不得轉載。
推薦閱讀：
※lambda演算與數據類型
※什麼是函數式編程？函數式編程到底有什麼好處？(轉)
※lambda 重點高級知識講解1 - 實例方法的方法引用
※如果讓自己只能保留一種編程語言，我選擇……