歷史來源
在計算機的世界中，有兩位巨擘對問題的可計算性做了模型化描述
一位是阿蘭.圖靈（Alan Turing），他提出的圖靈機。計算機系的各種學科中都充斥著這個概念，假設有一個紙帶和一個打孔機，然后有一套指令，能夠控制打孔機在紙帶上移動、能夠讀取當前位置是否打了孔、能夠在當前位置打一個孔，這就是一個圖靈機，假設一個問題能夠靠這個紙帶+打孔機+指令的方式解決，那就說明這個問題是“可計算的”。
另外一個位巨擘，是阿隆佐·邱奇（Alonzo Church）。邱奇是個數(shù)學家，他提出了Lambda演算(Lambda Calculus)的概念，用函數(shù)組合的方式來描述計算過程，換句話來說，如果一個問題能夠用一套函數(shù)組合的算法來表達，那就說明這個問題是可計算的。
我個人對這兩種計算過程的模型是這樣理解的，不一定對：
圖靈機是通過一系列指令和狀態(tài)來完成某種過程的
Lambda演算是通過一系列函數(shù)來描述問題并求解的
當然世上沒有兩全其美的東西上面兩種模型肯定都有自己的局限性，并不是所有的問題都是可以用函數(shù)式模型解決
編程范式
編程語言主要有三種類型：
聲明式編程：專注于”做什么”而不是”如何去做”。在更高層面寫代碼，更關心的是目標，而不是底層算法實現(xiàn)的過程。
如：css,正則表達式，sql語句，html,xml…命令式編程(過程式編程) : 專注于”如何去做”，這樣不管”做什么”，都會按照你的命令去做。解決某一問題的具體算法實現(xiàn)。
函數(shù)式編程：把運算過程盡量寫成一系列嵌套的函數(shù)調(diào)用。
命令式編程
命令式編程是通過賦值（由表達式和變量組成）以及控制結構（如，條件分支、循環(huán)語句等）來修改可修改的變量。
它的運作方式具有圖靈機特性，且和馮諾依曼體系的對應關系非常密切。甚至可以說，命令式程序就是一個馮諾依曼機的指令序列：
變量 →
內(nèi)存
變量引用 →
輸入設備
變量賦值 →
輸出設備
控制結構 →
跳轉(zhuǎn)操作
我們知道的，馮諾依曼結構需要用總線來傳輸數(shù)據(jù)，我們只能一個字節(jié)一個字節(jié)處理。
這也就形成了運行的瓶頸。程序執(zhí)行的效率取決于執(zhí)行命令的數(shù)量，因此才會出現(xiàn)大O表示法等等表示時間空間復雜度的符號。
函數(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ù)式編程
相比于命令式編程關心解決問題的步驟，函數(shù)式編程是面向數(shù)學的抽象，關心數(shù)據(jù)（代數(shù)結構）之間的映射關系。函數(shù)式編程將計算描述為一種表達式求值。
在狹義上，函數(shù)式編程意味著沒有可變變量，賦值，循環(huán)和其他的命令式控制結構。即，純函數(shù)式編程語言。
Pure Lisp, XSLT, XPath, XQuery, FP
Haskell (without I/O Monad or UnsafPerformIO)
在廣義上，函數(shù)式編程意味著專注于函數(shù)
Lisp, Scheme, Racket, Clojure
SML, Ocaml, F#
Haskell (full language)
Scala
Smalltalk, Ruby
函數(shù)
函數(shù)式編程中的函數(shù)，這個術語不是指命令式編程中的函數(shù)（我們可以認為C++程序中的函數(shù)本質(zhì)是一段子程序Subroutine），而是指數(shù)學中的函數(shù)，即自變量的映射（一種東西和另一種東西之間的對應關系）。也就是說，一個函數(shù)的值僅決定于函數(shù)參數(shù)的值，不依賴其他狀態(tài)。
在函數(shù)式語言中，函數(shù)被稱為一等函數(shù)（First-class function），與其他數(shù)據(jù)類型一樣，作為一等公民，處于平等地位，可以在任何地方定義，在函數(shù)內(nèi)或函數(shù)外；可以賦值給其他變量；可以作為參數(shù)，傳入另一個函數(shù)，或者作為別的函數(shù)的返回值。
純函數(shù)
純函數(shù)是一種函數(shù)特殊的函數(shù)，即xtong相同的輸入永遠會得到相同的輸出，而且沒有任何可觀察的副作用。
即：不依賴外部狀態(tài),不改變外部狀態(tài)
這里用JavaScript舉例
//不純的函數(shù)
var num = 2;
function add(a){
return a+ num;
}
var arr = [1,2,3];
function myPush(arr){
return arr.push(4)
}
//num arr 都被函數(shù)改變了
//純的函數(shù)
function add(a,b){
return a+b;
}
//add 函數(shù)沒有改變外部變量 同時相同的輸入永遠會得到相同的輸出
// 比如 add(1,2)=add(1,2)
變量與表達式
純函數(shù)式編程語言中的變量也不是命令式編程語言中的變量（存儲狀態(tài)的內(nèi)存單元），而是數(shù)學代數(shù)中的變量，即一個值的名稱。
變量的值是不可變的（immutable），也就是說不允許像命令式編程語言中那樣能夠多次給一個變量賦值。比如說在命令式編程語言我們寫x = x + 1。
函數(shù)式語言中的條件語句，循環(huán)語句等也不是命令式編程語言中的控制語句，而是一種表達式。
“表達式”（expression）是一個單純的運算過程，總是有返回值；
“語句”（statement）是執(zhí)行某種操作(更多的是邏輯語句。)，沒有返回值。
函數(shù)式編程要求，只使用表達式，不使用語句。也就是說，每一步都是單純的運算，而且都有返回值。比如在Scala語言中，if else不是語句而是三元運算符，是有返回值的。
嚴格意義上的函數(shù)式編程意味著不使用可變的變量，賦值，循環(huán)和其他命令式控制結構進行編程。 當然，很多所謂的函數(shù)式編程語言并沒有嚴格遵循這一類的準則，只有某些純函數(shù)式編程語言，如Haskell等才是完完全全地依照這種準則設計的。
函數(shù)與方法
當然在現(xiàn)在很多（非純）函數(shù)式編程語言中也有方法和函數(shù)的區(qū)別。比如scala
scala> def m(x:Int) = 2*x //定義一個方法
m: (x: Int)Int
scala> m //方法不能作為最終表達式出現(xiàn)
<console>:9: error: missing arguments for method m;
follow this method with '_' if you want to treat it as a partially applied function
m
^
scala> val f = (x:Int) => 2*x //定義一個函數(shù)
f: Int => Int = <function1>
scala> f //函數(shù)可以作為最終表達式出現(xiàn)
res9: Int => Int = <function1>
方法就是命令式編程中的函數(shù)，而函數(shù)則是函數(shù)式編程中的函數(shù)。
狀態(tài)
首先要意識到，我們的程序是擁有“狀態(tài)”的。 想一想我們調(diào)試C++程序的時候，經(jīng)常會在某處設置一個斷點。程序執(zhí)行斷點就暫停了，也就是說程序停留在了某一個狀態(tài)上。
這個狀態(tài)包括了當前定義的全部變量，以及一些當前系統(tǒng)的狀態(tài)，比如打開的文件、網(wǎng)絡的連接、申請的內(nèi)存等等。具體保存的信息和語言有關系。
比如使用過Matlab、R之類的科學計算語言的朋友會知道，在退出程序的時候它會讓你選擇是否要保存當前的session，如果保存了，下次打開時候它會從這個session開始繼續(xù)執(zhí)行，而不是清空一切重來。你之前定義了一個變量x = 1，現(xiàn)在這個x還在那里，值也沒變。
這個狀態(tài)就是圖靈機的紙帶。有了狀態(tài)，我們的程序才能不斷往前推進，一步步向目標靠攏的。
函數(shù)式編程不一樣。函數(shù)式編程強調(diào)無狀態(tài)，不是不保存狀態(tài)，而是強調(diào)將狀態(tài)鎖定在函數(shù)的內(nèi)部，不依賴于外部的任何狀態(tài)。更準確一點，它是通過函數(shù)創(chuàng)建新的參數(shù)或返回值來保存程序的狀態(tài)的。
我們都知道函數(shù)的狀態(tài)是完全存在棧上，函數(shù)執(zhí)行完后就會從棧中彈出函數(shù)內(nèi)部的狀態(tài)也就會消失，這時候就可以使用遞歸來維持這個狀態(tài)，函數(shù)一層層的疊加起來，其中每個函數(shù)的參數(shù)（是參數(shù)，不是變量）或返回結果來代表了程序的一個中間狀態(tài)。
用斐波那契數(shù)函數(shù)舉個例子
def Fib(a):
if a==0 or a==1:
return 1
else:
return Fib(a-2)+Fib(a-1)
//執(zhí)行的時候每個步驟的狀態(tài)都儲存棧上知道a==0 or a==1的時候在歸納從棧中一個個彈出
//命令編程模式的寫法
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ù)式編程的特性
- 高階函數(shù)（Higher-order function）
- 偏應用函數(shù)（Partially Applied Functions）
- 柯里化（Currying）
- 閉包（Closure）
高階函數(shù)
高階函數(shù)就是參數(shù)為函數(shù)或返回值為函數(shù)的函數(shù)，可以理解為函數(shù)的抽象
有了高階函數(shù)，就可以將復用的粒度降低到函數(shù)級別。相對于面向?qū)ο笳Z言中的抽象類，高階函數(shù)的復用粒度更低
舉個栗子
def id(x: Int): Int = x
def cube(x: Int): Int = x * x * x
def fact(x: Int): Int = if (x == 0) 1 else fact(x - 1)
//計算a~b之間整數(shù)的和
def sumInts(a: Int, b: Int): Int =
if (a > b) 0 else a + sumInts(a + 1, b)
//計算a~b之間立方和
def sumCubes(a: Int, b: Int): Int =
if (a > b) 0 else cube(a) + sumCubes(a + 1, b)
//計算a~b之間階乘和
def sumFactorials(a: Int, b: Int): Int =
if (a > b) 0 else fact(a) + sumFactorials(a + 1, b)
上面三個函數(shù)參數(shù)相同計算的形狀都式求和但是計算的方式不同，這時候就可以把這三個函數(shù)抽象一下
//在函數(shù)式編程模式里函數(shù)式一等公民可以和變量一樣傳入另一個函數(shù)中
def sum(f: Int => Int, a: Int, b: Int): Int =
if (a > b) 0
else f(a) + sum(f, a + 1, b)
def sumInts(a: Int, b: Int) = sum(id, a, b)
def sumCubs(a: Int, b: Int) = sum(cube, a, b)
def sumFactorials(a: Int, b: Int) = sum(fact, a, b)
高階函數(shù)提供了一種函數(shù)級別上的依賴注入（或反轉(zhuǎn)控制）機制，在上面的例子里，sum函數(shù)的邏輯依賴于注入進來的函數(shù)的邏輯。很多GoF設計模式都可以用高階函數(shù)來實現(xiàn)，如Visitor(訪問者模式)，Strategy(策略模式)，Decorator(裝飾模式)等。比如Visitor模式就可以用集合類的map()或foreach()高階函數(shù)來替代。
函數(shù)式語言通常提供非常強大的集合類（Collection），提供很多高階函數(shù)，因此使用非常方便。
比如說，我們想對一個列表中的每個整數(shù)乘2，在命令式編程中需要通過循環(huán)，然后對每一個元素乘2，但是在函數(shù)式編程中，我們不需要使用循環(huán)，只需要使用如下代碼：
scala> val numbers = List(1, 2, 3, 4)
numbers: List[Int] = List(1, 2, 3, 4)
scala> numbers.map(x=>x*2)
res3: List[Int] = List(2, 4, 6, 8)
在大數(shù)據(jù)處理框架Spark中，一個RDD就是一個集合。以詞頻統(tǒng)計的為例代碼如下：
val file = spark.textFile("hdfs://...") val counts = file.flatMap(line => line.split(" ")) .map(word => (word, 1)) .reduceByKey(_ + _) counts.saveAsTextFile("hdfs://...")
偏應用函數(shù)（Partially Applied Functions）
偏函數(shù)，也叫部分應用函數(shù)，就是固化函數(shù)的一個或一些參數(shù)，只傳入函數(shù)的部分參數(shù)，從而產(chǎn)生一個新的函數(shù)
舉個例子
object PartialAppliedFunction {
def main(args: Array[String]): Unit = {
val part_sum = sum(1,_:Int,3)
//這里只想要傳入要_代表的那一部分參數(shù)就行了
println(part_sum(2))
}
def sum(a:Int,b:Int,c:Int)=a+b+c
}
柯里化
curry 的概念很簡單：把接受多個參數(shù)的函數(shù)變換成接受一個單一參數(shù)（最初函數(shù)的第一個參數(shù)）的函數(shù)，并且返回接受余下的參數(shù)而且返回結果的新函數(shù)
舉個例子
//柯里化前
function add(a, b, c) { return a + b + c;}
//柯里化后
function _add(a) {
return function(b) {
return function(c) {
return a + b + c;
}
}
}
console.log(add(1)(2)(3)) // 6
//進階版 可以無限調(diào)用
function add(){
var args = [].slice.call(arguments);
var fn = function(){
var newArgs = args.concat([].slice.call(arguments));
return add.apply(null,newArgs);
}
fn.toString = function(){
return args.reduce(function(a, b) { return a + b; })
}
return fn ;
}
console.log(add(1)(2)(3));
閉包
閉包的基礎是一等函數(shù)（First-class function）。
閉包在形式上就是一個函數(shù)內(nèi)部定義另一個函數(shù)，函數(shù)的堆棧在在函數(shù)返回后并不釋放
舉個栗子
function outer() {
var n = 2;
function inner() { return n; };
return inner();
}
var result = outer();
console.log(result); // 2 行數(shù)中的n并沒有在執(zhí)行后釋放
函數(shù)式編程的好處
由于命令式編程語言也可以通過類似函數(shù)指針的方式來實現(xiàn)高階函數(shù)，函數(shù)式的最主要的好處主要是不變性帶來的。
引用透明（Referential transparency）
引用透明（Referential transparency），指的是函數(shù)的運行不依賴于外部變量或”狀態(tài)”，只依賴于輸入的參數(shù)，任何時候只要參數(shù)相同，引用函數(shù)所得到的返回值總是相同的。
其他類型的語言，函數(shù)的返回值往往與系統(tǒng)狀態(tài)有關，不同的狀態(tài)之下，返回值是不一樣的。這就叫”引用不透明”，很不利于觀察和理解程序的行為。
沒有可變的狀態(tài)，函數(shù)就是引用透明（Referential transparency）
沒有副作用（No Side Effect）。
副作用（side effect），指的是函數(shù)內(nèi)部與外部互動（最典型的情況，就是修改全局變量的值），產(chǎn)生運算以外的其他結果。
函數(shù)式編程強調(diào)沒有”副作用”，意味著函數(shù)要保持獨立，所有功能就是返回一個新的值，沒有其他行為，尤其是不得修改外部變量的值。
函數(shù)即不依賴外部的狀態(tài)也不修改外部的狀態(tài)，函數(shù)調(diào)用的結果不依賴調(diào)用的時間和位置，這樣寫的代碼容易進行推理，不容易出錯。這使得單元測試和調(diào)試都更容易。
還有一個好處是，由于函數(shù)式語言是面向數(shù)學的抽象，更接近人的語言，而不是機器語言，代碼會比較簡潔，也更容易被理解。
優(yōu)化處理
由以上兩點，由衍生出了更多的特性。
無鎖并發(fā)
沒有副作用使得函數(shù)式編程各個獨立的部分的執(zhí)行順序可以隨意打亂，（多個線程之間）不共享狀態(tài)，不會造成資源爭用(Race condition)，也就不需要用鎖來保護可變狀態(tài)，也就不會出現(xiàn)死鎖，這樣可以更好地進行無鎖（lock-free）的并發(fā)操作。
尤其是在對稱多處理器（SMP）架構下能夠更好地利用多個處理器（核）提供的并行處理能力。
惰性求值
惰性求值[7]（lazy evaluation，也稱作call-by-need）是這樣一種技術：是在將表達式賦值給變量（或稱作綁定）時并不計算表達式的值，而在變量第一次被使用時才進行計算。
這樣就可以通過避免不必要的求值提升性能。
在Scala里，通過lazy val來指定一個變量是惰性求值的，如下面的示例所示：
scala> val x = { println("x"); 15 }
x
x: Int = 15
scala> lazy val y = { println("y"); 13 }
y: Int = <lazy>
scala> y
y
res3: Int = 13
scala> y
res4: Int = 13
可以看到，在Scala的解釋器中，當定義了x變量時就打印出了“x”，而定義變量y時并沒有打印出”y“，而是在第一次引用變量y時才打印出來。
函數(shù)式編程總覽
看完了函數(shù)式編程的特點，我們想想函數(shù)式編程的應用場合。
數(shù)學推理
并行程序
其實函數(shù)式編程最適合地還是解決局部性的數(shù)學小問題，要讓函數(shù)式編程來做CRUD，來做我們傳統(tǒng)的邏輯性很強的Web編程，就有些免為其難了，現(xiàn)在Java8中也引入了lambda表達式來支持函數(shù)式編程
參考文章
https://www.cnblogs.com/feng9exe/p/9167737.html
https://blog.csdn.net/u013007900/article/details/79104110
https://blog.csdn.net/jiajiayouba/article/details/49983325?utm_source=blogxgwz0
https://blog.csdn.net/LeeSirbupt/article/details/80834700?utm_source=blogxgwz0
https://www.ibm.com/developerworks/cn/java/j-lo-java8streamapi/
https://www.jb51.net/article/73208.htm
