歷史來(lái)源

在計(jì)算機(jī)的世界中，有兩位巨擘對(duì)問(wèn)題的可計(jì)算性做了模型化描述

一位是阿蘭.圖靈（Alan Turing），他提出的圖靈機(jī)。計(jì)算機(jī)系的各種學(xué)科中都充斥著這個(gè)概念，假設(shè)有一個(gè)紙帶和一個(gè)打孔機(jī)，然后有一套指令，能夠控制打孔機(jī)在紙帶上移動(dòng)、能夠讀取當(dāng)前位置是否打了孔、能夠在當(dāng)前位置打一個(gè)孔，這就是一個(gè)圖靈機(jī)，假設(shè)一個(gè)問(wèn)題能夠靠這個(gè)紙帶+打孔機(jī)+指令的方式解決，那就說(shuō)明這個(gè)問(wèn)題是“可計(jì)算的”。

另外一個(gè)位巨擘，是阿隆佐·邱奇（Alonzo Church）。邱奇是個(gè)數(shù)學(xué)家，他提出了Lambda演算(Lambda Calculus)的概念，用函數(shù)組合的方式來(lái)描述計(jì)算過(guò)程，換句話來(lái)說(shuō)，如果一個(gè)問(wèn)題能夠用一套函數(shù)組合的算法來(lái)表達(dá)，那就說(shuō)明這個(gè)問(wèn)題是可計(jì)算的。

我個(gè)人對(duì)這兩種計(jì)算過(guò)程的模型是這樣理解的，不一定對(duì)：

圖靈機(jī)是通過(guò)一系列指令和狀態(tài)來(lái)完成某種過(guò)程的
Lambda演算是通過(guò)一系列函數(shù)來(lái)描述問(wèn)題并求解的
當(dāng)然世上沒(méi)有兩全其美的東西上面兩種模型肯定都有自己的局限性，并不是所有的問(wèn)題都是可以用函數(shù)式模型解決

編程范式

編程語(yǔ)言主要有三種類型：

• 聲明式編程：專注于”做什么”而不是”如何去做”。在更高層面寫(xiě)代碼，更關(guān)心的是目標(biāo)，而不是底層算法實(shí)現(xiàn)的過(guò)程。
  如：css, 正則表達(dá)式，sql 語(yǔ)句，html, xml…

• 命令式編程(過(guò)程式編程) : 專注于”如何去做”，這樣不管”做什么”，都會(huì)按照你的命令去做。解決某一問(wèn)題的具體算法實(shí)現(xiàn)。

• 函數(shù)式編程：把運(yùn)算過(guò)程盡量寫(xiě)成一系列嵌套的函數(shù)調(diào)用。

命令式編程

命令式編程是通過(guò)賦值（由表達(dá)式和變量組成）以及控制結(jié)構(gòu)（如，條件分支、循環(huán)語(yǔ)句等）來(lái)修改可修改的變量。

它的運(yùn)作方式具有圖靈機(jī)特性，且和馮諾依曼體系的對(duì)應(yīng)關(guān)系非常密切。甚至可以說(shuō)，命令式程序就是一個(gè)馮諾依曼機(jī)的指令序列：

    變量 →
    內(nèi)存
    變量引用 →
    輸入設(shè)備
    變量賦值 →
    輸出設(shè)備
    控制結(jié)構(gòu) →
    跳轉(zhuǎn)操作

我們知道的，馮諾依曼結(jié)構(gòu)需要用總線來(lái)傳輸數(shù)據(jù)，我們只能一個(gè)字節(jié)一個(gè)字節(jié)處理。

這也就形成了運(yùn)行的瓶頸。程序執(zhí)行的效率取決于執(zhí)行命令的數(shù)量，因此才會(huì)出現(xiàn)大O表示法等等表示時(shí)間空間復(fù)雜度的符號(hào)。

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

一直以來(lái)，作為函數(shù)式編程代表的Lisp，還是Haskell，更多地都是在大學(xué)中，在實(shí)驗(yàn)室中應(yīng)用，而很少真的應(yīng)用到真實(shí)的生產(chǎn)環(huán)境。

先讓我們?cè)賮?lái)回顧一下偉大的摩爾定律：

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

2、微處理器的性能每隔18個(gè)月提高一倍，而價(jià)格下降一半。

3、用一個(gè)美元所能買(mǎi)到的電腦性能，每隔18個(gè)月翻兩番。

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

多核并行程序設(shè)計(jì)就這樣被推到了前線，而命令式編程天生的缺陷卻使并行編程模型變得非常復(fù)雜，無(wú)論是信號(hào)量，還是鎖的概念，都使程序員不堪其重。

就這樣，函數(shù)式編程終于在數(shù)十年后，終于走出實(shí)驗(yàn)室，來(lái)到了真實(shí)的生產(chǎn)環(huán)境中，無(wú)論是冷門(mén)的Haskell，Erlang，還是Scala，F(xiàn)#，都是函數(shù)式編程成功的典型。

函數(shù)式編程

相比于命令式編程關(guān)心解決問(wèn)題的步驟，函數(shù)式編程是面向數(shù)學(xué)的抽象，關(guān)心數(shù)據(jù)（代數(shù)結(jié)構(gòu)）之間的映射關(guān)系。函數(shù)式編程將計(jì)算描述為一種表達(dá)式求值。

在狹義上，函數(shù)式編程意味著沒(méi)有可變變量，賦值，循環(huán)和其他的命令式控制結(jié)構(gòu)。即，純函數(shù)式編程語(yǔ)言。

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ù)，這個(gè)術(shù)語(yǔ)不是指命令式編程中的函數(shù)（我們可以認(rèn)為C++程序中的函數(shù)本質(zhì)是一段子程序Subroutine），而是指數(shù)學(xué)中的函數(shù)，即自變量的映射（一種東西和另一種東西之間的對(duì)應(yīng)關(guān)系）。也就是說(shuō)，一個(gè)函數(shù)的值僅決定于函數(shù)參數(shù)的值，不依賴其他狀態(tài)。

在函數(shù)式語(yǔ)言中，函數(shù)被稱為一等函數(shù)（First-class function），與其他數(shù)據(jù)類型一樣，作為一等公民，處于平等地位，可以在任何地方定義，在函數(shù)內(nèi)或函數(shù)外；可以賦值給其他變量；可以作為參數(shù)，傳入另一個(gè)函數(shù)，或者作為別的函數(shù)的返回值。

純函數(shù)

純函數(shù)是一種函數(shù)特殊的函數(shù)，即xtong相同的輸入永遠(yuǎn)會(huì)得到相同的輸出，而且沒(méi)有任何可觀察的副作用。
即：不依賴外部狀態(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ù)沒(méi)有改變外部變量 同時(shí)相同的輸入永遠(yuǎn)會(huì)得到相同的輸出
// 比如 add(1,2)=add(1,2)

變量與表達(dá)式

純函數(shù)式編程語(yǔ)言中的變量也不是命令式編程語(yǔ)言中的變量（存儲(chǔ)狀態(tài)的內(nèi)存單元），而是數(shù)學(xué)代數(shù)中的變量，即一個(gè)值的名稱。

變量的值是不可變的（immutable），也就是說(shuō)不允許像命令式編程語(yǔ)言中那樣能夠多次給一個(gè)變量賦值。比如說(shuō)在命令式編程語(yǔ)言我們寫(xiě)x = x + 1。

函數(shù)式語(yǔ)言中的條件語(yǔ)句，循環(huán)語(yǔ)句等也不是命令式編程語(yǔ)言中的控制語(yǔ)句，而是一種表達(dá)式。

“表達(dá)式”（expression）是一個(gè)單純的運(yùn)算過(guò)程，總是有返回值；
“語(yǔ)句”（statement）是執(zhí)行某種操作(更多的是邏輯語(yǔ)句。)，沒(méi)有返回值。

函數(shù)式編程要求，只使用表達(dá)式，不使用語(yǔ)句。也就是說(shuō)，每一步都是單純的運(yùn)算，而且都有返回值。比如在Scala語(yǔ)言中，if else不是語(yǔ)句而是三元運(yùn)算符，是有返回值的。

嚴(yán)格意義上的函數(shù)式編程意味著不使用可變的變量，賦值，循環(huán)和其他命令式控制結(jié)構(gòu)進(jìn)行編程。 當(dāng)然，很多所謂的函數(shù)式編程語(yǔ)言并沒(méi)有嚴(yán)格遵循這一類的準(zhǔn)則，只有某些純函數(shù)式編程語(yǔ)言，如Haskell等才是完完全全地依照這種準(zhǔn)則設(shè)計(jì)的。

函數(shù)與方法

當(dāng)然在現(xiàn)在很多（非純）函數(shù)式編程語(yǔ)言中也有方法和函數(shù)的區(qū)別。比如scala

scala> def m(x:Int) = 2*x   //定義一個(gè)方法
m: (x: Int)Int

scala> m    //方法不能作為最終表達(dá)式出現(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   //定義一個(gè)函數(shù)
f: Int => Int = <function1>

scala> f    //函數(shù)可以作為最終表達(dá)式出現(xiàn)
res9: Int => Int = <function1>

方法就是命令式編程中的函數(shù)，而函數(shù)則是函數(shù)式編程中的函數(shù)。

狀態(tài)

首先要意識(shí)到，我們的程序是擁有“狀態(tài)”的。 想一想我們調(diào)試C++程序的時(shí)候，經(jīng)常會(huì)在某處設(shè)置一個(gè)斷點(diǎn)。程序執(zhí)行斷點(diǎn)就暫停了，也就是說(shuō)程序停留在了某一個(gè)狀態(tài)上。

這個(gè)狀態(tài)包括了當(dāng)前定義的全部變量，以及一些當(dāng)前系統(tǒng)的狀態(tài)，比如打開(kāi)的文件、網(wǎng)絡(luò)的連接、申請(qǐng)的內(nèi)存等等。具體保存的信息和語(yǔ)言有關(guān)系。

比如使用過(guò)Matlab、R之類的科學(xué)計(jì)算語(yǔ)言的朋友會(huì)知道，在退出程序的時(shí)候它會(huì)讓你選擇是否要保存當(dāng)前的session，如果保存了，下次打開(kāi)時(shí)候它會(huì)從這個(gè)session開(kāi)始繼續(xù)執(zhí)行，而不是清空一切重來(lái)。你之前定義了一個(gè)變量x = 1，現(xiàn)在這個(gè)x還在那里，值也沒(méi)變。

這個(gè)狀態(tài)就是圖靈機(jī)的紙帶。有了狀態(tài)，我們的程序才能不斷往前推進(jìn)，一步步向目標(biāo)靠攏的。

函數(shù)式編程不一樣。函數(shù)式編程強(qiáng)調(diào)無(wú)狀態(tài)，不是不保存狀態(tài)，而是強(qiáng)調(diào)將狀態(tài)鎖定在函數(shù)的內(nèi)部，不依賴于外部的任何狀態(tài)。更準(zhǔn)確一點(diǎn)，它是通過(guò)函數(shù)創(chuàng)建新的參數(shù)或返回值來(lái)保存程序的狀態(tài)的。

我們都知道函數(shù)的狀態(tài)是完全存在棧上，函數(shù)執(zhí)行完后就會(huì)從棧中彈出函數(shù)內(nèi)部的狀態(tài)也就會(huì)消失，這時(shí)候就可以使用遞歸來(lái)維持這個(gè)狀態(tài)，函數(shù)一層層的疊加起來(lái)，其中每個(gè)函數(shù)的參數(shù)（是參數(shù)，不是變量）或返回結(jié)果來(lái)代表了程序的一個(gè)中間狀態(tài)。

用斐波那契數(shù)函數(shù)舉個(gè)例子

def Fib(a): 
    if a==0 or a==1: 
        return 1 
    else: 
        return Fib(a-2)+Fib(a-1)
//執(zhí)行的時(shí)候每個(gè)步驟的狀態(tài)都儲(chǔ)存棧上知道a==0 or a==1的時(shí)候在歸納從棧中一個(gè)個(gè)彈出        
       
//命令編程模式的寫(xiě)法 
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）
• 偏應(yīng)用函數(shù)（Partially Applied Functions）
• 柯里化（Currying）
• 閉包（Closure）

高階函數(shù)

高階函數(shù)就是參數(shù)為函數(shù)或返回值為函數(shù)的函數(shù)，可以理解為函數(shù)的抽象
有了高階函數(shù)，就可以將復(fù)用的粒度降低到函數(shù)級(jí)別。相對(duì)于面向?qū)ο笳Z(yǔ)言中的抽象類，高階函數(shù)的復(fù)用粒度更低

舉個(gè)栗子

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)
//計(jì)算a~b之間整數(shù)的和
def sumInts(a: Int, b: Int): Int = 
    if (a > b) 0 else a + sumInts(a + 1, b) 

//計(jì)算a~b之間立方和
def sumCubes(a: Int, b: Int): Int = 
    if (a > b) 0 else cube(a) + sumCubes(a + 1, b) 

//計(jì)算a~b之間階乘和
def sumFactorials(a: Int, b: Int): Int = 
    if (a > b) 0 else fact(a) + sumFactorials(a + 1, b)

上面三個(gè)函數(shù)參數(shù)相同計(jì)算的形狀都式求和但是計(jì)算的方式不同，這時(shí)候就可以把這三個(gè)函數(shù)抽象一下

//在函數(shù)式編程模式里函數(shù)式一等公民可以和變量一樣傳入另一個(gè)函數(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ù)級(jí)別上的依賴注入（或反轉(zhuǎn)控制）機(jī)制，在上面的例子里，sum函數(shù)的邏輯依賴于注入進(jìn)來(lái)的函數(shù)的邏輯。很多GoF設(shè)計(jì)模式都可以用高階函數(shù)來(lái)實(shí)現(xiàn)，如Visitor(訪問(wèn)者模式)，Strategy(策略模式)，Decorator(裝飾模式)等。比如Visitor模式就可以用集合類的map()或foreach()高階函數(shù)來(lái)替代。

函數(shù)式語(yǔ)言通常提供非常強(qiáng)大的集合類（Collection），提供很多高階函數(shù)，因此使用非常方便。

比如說(shuō)，我們想對(duì)一個(gè)列表中的每個(gè)整數(shù)乘2，在命令式編程中需要通過(guò)循環(huán)，然后對(duì)每一個(gè)元素乘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中，一個(gè)RDD就是一個(gè)集合。以詞頻統(tǒng)計(jì)的為例代碼如下：

val file = spark.textFile("hdfs://...") val counts = file.flatMap(line => line.split(" ")) .map(word => (word, 1)) .reduceByKey(_ + _) counts.saveAsTextFile("hdfs://...")

偏應(yīng)用函數(shù)（Partially Applied Functions）

偏函數(shù)，也叫部分應(yīng)用函數(shù)，就是固化函數(shù)的一個(gè)或一些參數(shù)，只傳入函數(shù)的部分參數(shù)，從而產(chǎn)生一個(gè)新的函數(shù)
舉個(gè)例子

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 的概念很簡(jiǎn)單：把接受多個(gè)參數(shù)的函數(shù)變換成接受一個(gè)單一參數(shù)（最初函數(shù)的第一個(gè)參數(shù)）的函數(shù)，并且返回接受余下的參數(shù)而且返回結(jié)果的新函數(shù)

舉個(gè)例子

//柯里化前
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

//進(jìn)階版 可以無(wú)限調(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));

閉包

閉包的基礎(chǔ)是一等函數(shù)（First-class function）。

閉包在形式上就是一個(gè)函數(shù)內(nèi)部定義另一個(gè)函數(shù)，函數(shù)的堆棧在在函數(shù)返回后并不釋放

舉個(gè)栗子

function outer() {
    var n = 2; 
    function inner() { return n; }; 
    return inner(); 
} 
var result = outer(); 
console.log(result); // 2 行數(shù)中的n并沒(méi)有在執(zhí)行后釋放

函數(shù)式編程的好處

由于命令式編程語(yǔ)言也可以通過(guò)類似函數(shù)指針的方式來(lái)實(shí)現(xiàn)高階函數(shù)，函數(shù)式的最主要的好處主要是不變性帶來(lái)的。

引用透明（Referential transparency）

引用透明（Referential transparency），指的是函數(shù)的運(yùn)行不依賴于外部變量或”狀態(tài)”，只依賴于輸入的參數(shù)，任何時(shí)候只要參數(shù)相同，引用函數(shù)所得到的返回值總是相同的。

其他類型的語(yǔ)言，函數(shù)的返回值往往與系統(tǒng)狀態(tài)有關(guān)，不同的狀態(tài)之下，返回值是不一樣的。這就叫”引用不透明”，很不利于觀察和理解程序的行為。

沒(méi)有可變的狀態(tài)，函數(shù)就是引用透明（Referential transparency）

沒(méi)有副作用（No Side Effect）。

副作用（side effect），指的是函數(shù)內(nèi)部與外部互動(dòng)（最典型的情況，就是修改全局變量的值），產(chǎn)生運(yùn)算以外的其他結(jié)果。

函數(shù)式編程強(qiáng)調(diào)沒(méi)有”副作用”，意味著函數(shù)要保持獨(dú)立，所有功能就是返回一個(gè)新的值，沒(méi)有其他行為，尤其是不得修改外部變量的值。

函數(shù)即不依賴外部的狀態(tài)也不修改外部的狀態(tài)，函數(shù)調(diào)用的結(jié)果不依賴調(diào)用的時(shí)間和位置，這樣寫(xiě)的代碼容易進(jìn)行推理，不容易出錯(cuò)。這使得單元測(cè)試和調(diào)試都更容易。

還有一個(gè)好處是，由于函數(shù)式語(yǔ)言是面向數(shù)學(xué)的抽象，更接近人的語(yǔ)言，而不是機(jī)器語(yǔ)言，代碼會(huì)比較簡(jiǎn)潔，也更容易被理解。

優(yōu)化處理

由以上兩點(diǎn)，由衍生出了更多的特性。

無(wú)鎖并發(fā)

沒(méi)有副作用使得函數(shù)式編程各個(gè)獨(dú)立的部分的執(zhí)行順序可以隨意打亂，（多個(gè)線程之間）不共享狀態(tài)，不會(huì)造成資源爭(zhēng)用(Race condition)，也就不需要用鎖來(lái)保護(hù)可變狀態(tài)，也就不會(huì)出現(xiàn)死鎖，這樣可以更好地進(jìn)行無(wú)鎖（lock-free）的并發(fā)操作。

尤其是在對(duì)稱多處理器（SMP）架構(gòu)下能夠更好地利用多個(gè)處理器（核）提供的并行處理能力。

惰性求值

惰性求值[7]（lazy evaluation，也稱作call-by-need）是這樣一種技術(shù)：是在將表達(dá)式賦值給變量（或稱作綁定）時(shí)并不計(jì)算表達(dá)式的值，而在變量第一次被使用時(shí)才進(jìn)行計(jì)算。

這樣就可以通過(guò)避免不必要的求值提升性能。

在Scala里，通過(guò)lazy val來(lái)指定一個(gè)變量是惰性求值的，如下面的示例所示：

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的解釋器中，當(dāng)定義了x變量時(shí)就打印出了“x”，而定義變量y時(shí)并沒(méi)有打印出”y“，而是在第一次引用變量y時(shí)才打印出來(lái)。

函數(shù)式編程總覽

看完了函數(shù)式編程的特點(diǎn)，我們想想函數(shù)式編程的應(yīng)用場(chǎng)合。

1. 數(shù)學(xué)推理

2. 并行程序

其實(shí)函數(shù)式編程最適合地還是解決局部性的數(shù)學(xué)小問(wèn)題，要讓函數(shù)式編程來(lái)做CRUD，來(lái)做我們傳統(tǒng)的邏輯性很強(qiáng)的Web編程，就有些免為其難了，現(xiàn)在Java8中也引入了lambda表達(dá)式來(lái)支持函數(shù)式編程

社區(qū)論壇

參考文章
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