相信大家平時或多或少聽過不少關於“函數式編程” （FP）相關的詞語，有些Geek經常吹捧函數式的優點或者特性比如：純函數無副作用、不變的數據、高階函數、流計算模式、尾遞歸、柯裡化等等，再加上目前的函數式理論越來越多的應用於工程中，OCaml，clojure, scala等FP語言日漸火爆。本編文章，筆者准備帶領大家深入理解函數式編程的相關理論概念。
首先引用維基百科對函數式編程的解釋：在計算機科學裡，函數式編程是一種編程范式，它將計算描述為表達式求值並避免了狀態和數據改變。函數式編程裡面的“函數”指的是數學函數，數學函數和我們平時工作中遇到的編程函數有什麼區別呢？
從上圖不難發現：數學函數的特點是對於每一個自變量，存在唯一的因變量與之對應。而編程函數的特點是參數和返回值都不是必須的，函數可能依賴外界或者影響外界。那麼編程函數能否轉換成數學函數，或者說我們的編程函數能否變成“純函數”？
對於任何一個編程函數，需要滿足下面3個條件，即可轉換成純數學函數。
以快排為例，過程式的版本，可以發現重視過程：
void Solution::quickSort(vecotr<int> &nums, int left, int right)
{
int i = left, j = right;
int pviot = nums[(i + j) >> 1];
while (i <= j)
{
while (nums[i] < pviot)
i ++;
while (nums[j] > pviot)
j --;
if (i <= j)
{
swap(nums[i], nums[j]);
i ++;
j --;
}
}
if (left < j)
quickSort(nums, left, j);
if (right > i)
quickSort(nums, i, right);
}Haskell的快排實現，可以發現更加注重結果：
quickSort :: (Ord a) => [a] -> [a]
-- If input list is empty
quickSort [] = []
-- List isn't empty
quickSort (x : xs) =
let smallerSorted = quickSort (filter (<= x) xs)
biggerSorted = quickSort (filter (> x) xs)
in smallerSorted ++ [x] ++ biggerSorted所有的命令式語言都被設計來高效地使用馮諾依曼體系結構的計算機。實際上，最初的命令式語言的目的就是取代匯編語言，對機器指令進行進一步抽象。因此，命令式語言帶有強烈的硬件結構特征。命令式語言的核心特性有：模擬存儲單元的變量、基於傳輸操作的賦值語句，以及迭代形式的循環運算。命令式語言的基礎是語句（特別是賦值），它們通過修改存儲器的值而產生副作用（side effect）的方式去影響後續的計算。
函數式語言設計的基礎是Lambda表達式，函數式程序設計把程序的輸出定義為其輸入的一個數學函數，在這裡沒有內部狀態，也沒有副作用。函數式語言進行計算的主要是將函數作用與給定參數之上。函數式語言沒有命令式語言所必需的那種變量，可以沒有賦值語句，也可以沒有循環。一個程序就是函數定義和函數應用的說明；一個程序的執行就是對函數應用的求值。
高階函數實際上就是函數的函數，它是所有函數式語言的性質。函數式語言中，函數作為第一等公民，這也意味著你像定義或調用變量一樣去定義或調用函數。可以在任何地方定義，在函數內或函數外，可以將函數作為參數或者返回值。在數學和計算機科學中，高階函數是至少滿足下列一個條件的函數:
在數學中它們也叫做算子(運算符)或泛函。微積分中的導數就是常見的例子，因為它映射一個函數到另一個函數。
以Haskell裡面的Map和Filter為例子。
-- 比如我們有一組List,[1,2,3,4,5],我需要將他們都平方
map (\x->x^2) [1,2,3,4,5]
-- 找到大於3的所有數
filter (>3) [1,2,3,4,5]由於變量不可變，純函數編程語言裡面無法實現循環，這是因為for循環使用可變的狀態作為計數器，而while循環或者do-while循環需要可變的狀態作為跳出循環的條件。因此函數式語言裡面只能用遞歸來解決迭代問題，這使得函數式編程嚴重依賴遞歸。以階乘函數的實現為例子：
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)這個時候的程序調用內部的計算表現形式為線性擴張（先擴張，後收縮）：
回顧下函數調用的過程：
在函數 A 執行的時候，如果在第二步中，它又調用了另一個函數 B，B 又調用 C.... 棧就會不斷地增長不斷地裝入數據，當這個調用鏈很深的時候，棧很容易就滿 了，這就是一般遞歸函數所容易面臨的大問題。稍有不慎，就會有爆棧的危險（比如經典的斐波那契數列，樹形擴張）。
尾調用：指某個函數的最後一步是調用另一個函數。
尾遞歸：函數尾部調用自身。大部分函數式編程語言比如Scheme、Haskell裡面要求實現尾遞歸優化，編譯器會在編譯期間會將尾遞歸優化為循環。
將上述普通遞歸函數用尾遞歸的方式重寫：
factorial :: Int -> Int
factorial n = factiter 1 1 n
factiter :: Int -> Int -> Int -> Int
factiter product counter maxCount
| counter > maxCount = product
| otherwise = factiter (* counter product) (+ counter 1) maxCount這個時候的程序調用內部的計算表現形式如圖，內存消耗從O(n)到O(1)：
偏函數解決這樣的問題：如果我們有函數是多個參數的，我們希望能固定其中某幾個參數的值。以Python為例子:
from functools import partial
def foo (a, b, c):
return a + b + c
foo21 = partial (foo, b=21)
foo21(a = 1, c = 3) # => 25函數式語言的currying特性來自於lambda calculus，lambda calculus只支持單參函數，但它可以返回一個函數來接受第二個參數。
關於柯裡化，我們可以這麼理解：柯裡化就是一個函數在參數沒給全時返回另一個函數，返回的函數的參數正好是余下的參數。比如：你制定了x和y, 如2的3次方,就返回8, 如果你只制定x為2,y沒指定, 那麼就返回一個函數：2的y次方, 這個函數只有一個參數:y。
它的 2 大特性：
以Javascript為例子，一個函數接受2個參數，返回它們的和：
functionadd (a, b) {
return a + b;
}
add(3, 4); returns 7采用柯裡化後，變成一個函數接受1個參數，返回一個接受另外一個參數並且返回它們和的的函數：
functionadd (a) {
return function (b) {
return a + b;
}
}
// 調用
add(3)(4);
var add3 = add(3);
add3(4);這個概念來自於SICP裡面的第3章，可以理解為unix裡面的pipline，使用它可以讓代碼具有申明式的語義化、模塊化，更加富有表現力。
以javascript為例，設計好的風格的代碼表現如下：
getAsyncStockData()
.filter(quote => quote.price > 30)
.map(quote => quote.price)
.forEach(price => console.log(`Prices higher than $30: ${price}`));
