標籤：

什麼是函數式編程思維？

11-24

看好多帖子，愣是沒明白。或者說沒有文章能告訴我函數式編程幫我解決了什麼問題. 舉個例子，我看完"面向對象分析與設計"那本經典，我就能明白面向對象的方法或者說模型如何控制複雜性(軟體固有複雜性)。

2015/3/4 補充：我看到有些文章習慣性的就給我上函數式編程語言的，如柯里化，不變性。而在我看來，這些只是函數式編程語言的feature。而我更希望看到的是這些feature背後的邏輯。

（知乎的代碼觀感不太好，我的博客里可能排版舒服一點）

函數式編程與命令式編程最大的不同其實在於：

函數式編程關心數據的映射，命令式編程關心解決問題的步驟

這裡的映射就是數學上「函數」的概念——一種東西和另一種東西之間的對應關係。

這也是為什麼「函數式編程」叫做「函數」式編程。

這是什麼意思呢？

假如，現在你來到 google 面試，面試官讓你把二叉樹鏡像反轉一下（大霧

幾乎不假思索的，就可以寫出這樣的 Python 代碼：

def invertTree(root):
if root is None:
return None
root.left, root.right = invertTree(root.right), invertTree(root.left)
return root

好了，現在停下來看看這段代碼究竟代表著什麼——

它的含義是：首先判斷節點是否為空；然後翻轉左樹；然後翻轉右樹；最後左右互換。

這就是命令式編程——你要做什麼事情，你得把達到目的的步驟詳細的描述出來，然後交給機器去運行。

這也正是命令式編程的理論模型——圖靈機的特點。一條寫滿數據的紙帶，一條根據紙帶內容運動的機器，機器每動一步都需要紙帶上寫著如何達到。

那麼，不用這種方式，如何翻轉二叉樹呢？

函數式思維提供了另一種思維的途徑——

所謂「翻轉二叉樹」，可以看做是要得到一顆和原來二叉樹對稱的新二叉樹。

這顆新二叉樹的特點是每一個節點都遞歸地和原樹相反。

用 haskell 代碼表達出來就是：

data Tree a = Nil | Node a (Tree a) (Tree a)
deriving (Show, Eq)

invert :: Tree a -&> Tree a
invert Nil = Nil
invert (Node v l r) = Node v (invert r) (invert l)

（防止看不懂，翻譯成等價的 python ）

def invert(node):
if node is None:
return None
else
return Tree(node.value, invert(node.right), invert(node.left))

這段代碼體現的思維，就是舊樹到新樹的映射——對一顆二叉樹而言，它的鏡像樹就是左右節點遞歸鏡像的樹。

這段代碼最終達到的目的同樣是翻轉二叉樹，但是它得到結果的方式和 python 代碼有著本質的差別：通過描述一個 舊樹-&>新樹 的映射，而不是描述「從舊樹得到新樹應該怎樣做」來達到目的。

那麼這樣有什麼好處呢？

首先，最直觀的角度來說，函數式風格的代碼可以寫得很精簡，大大減少了鍵盤的損耗（

其次，函數式的代碼是「對映射的描述」，它不僅可以描述二叉樹這樣的數據結構之間的對應關係，任何能在計算機中體現的東西之間的對應關係都可以描述——比如函數和函數之間的映射（比如 functor）；比如外部操作到 GUI 之間的映射（就是現在前端熱炒的所謂 FRP）。它的抽象程度可以很高，這就意味著函數式的代碼可以更方便的復用。

另外還有其他答主提到的，可以方便的並行。

同時，將代碼寫成這種樣子可以方便用數學的方法進行研究（不能理解 monad 就是自函子範疇上的一個幺半群你還想用 Haskell 寫出 Hello world ？）

至於什麼科里化、什麼數據不可變，都只是外延體現而已。

自邀，@nameoverflow 已經說的很好了，我就說些自己的看法。

首先引用@nameoverflow 的這句話：

函數式編程關心數據的映射，命令式編程關心解決問題的步驟

我想稍微改一下，使其更數學化一點。

函數式編程關心類型（代數結構）之間的關係，命令式編程關心解決問題的步驟

函數式編程中的lambda可以看成是兩個類型之間的關係，一個輸入類型和一個輸出類型。lambda演算就是給lambda表達式一個輸入類型的值，則可以得到一個輸出類型的值，這是一個計算，計算過程滿足 alpha -等價和 eta -規約。

函數式編程的思維就是如何將這個關係組合起來，用數學的構造主義將其構造出你設計的程序。

用Haskell來說，這個關係就是運算符(-&>)，其表示了一個lambda演算的類型，在值的層面和符號""一起構造了一個lambda表達式。空類型()、積類型(a, b)與和類型Either a b是最基本的數據類型的構造，其和curry和uncurry一起，還有米田定理、伴隨函子，使得我們可以構造任意複雜的數據類型和程序。比如Functor、Applicative、Monad/Comonad、Limit/Colimit、End/Coend、Left Kan Extenstion/Right Kan extension等。

具體的程序構造例子可以看我的回答

parker liu：Haskell中的foldl和foldr的聯繫？

先說這麼多吧。

編程範式
函數式編程是一種編程範式，我們常見的編程範式有命令式編程（Imperative programming），函數式編程，邏輯式編程，常見的面向對象編程是也是一種命令式編程。

命令式編程是面向計算機硬體的抽象，有變數（對應著存儲單元），賦值語句（獲取，存儲指令），表達式（內存引用和算術運算）和控制語句（跳轉指令），一句話，命令式程序就是一個馮諾依曼機的指令序列。

而函數式編程是面向數學的抽象，將計算描述為一種表達式求值，一句話，函數式程序就是一個表達式。

函數式編程的本質
函數式編程中的函數這個術語不是指計算機中的函數（實際上是Subroutine），而是指數學中的函數，即自變數的映射。也就是說一個函數的值僅決定於函數參數的值，不依賴其他狀態。比如sqrt(x)函數計算x的平方根，只要x不變，不論什麼時候調用，調用幾次，值都是不變的。

在函數式語言中，函數作為一等公民，可以在任何地方定義，在函數內或函數外，可以作為函數的參數和返回值，可以對函數進行組合。

純函數式編程語言中的變數也不是命令式編程語言中的變數，即存儲狀態的單元，而是代數中的變數，即一個值的名稱。變數的值是不可變的（immutable），也就是說不允許像命令式編程語言中那樣多次給一個變數賦值。比如說在命令式編程語言我們寫「x = x + 1」，這依賴可變狀態的事實，拿給程序員看說是對的，但拿給數學家看，卻被認為這個等式為假。

函數式語言的如條件語句，循環語句也不是命令式編程語言中的控制語句，而是函數的語法糖，比如在Scala語言中，if else不是語句而是三元運算符，是有返回值的。

嚴格意義上的函數式編程意味著不使用可變的變數，賦值，循環和其他命令式控制結構進行編程。

從理論上說，函數式語言也不是通過馮諾伊曼體系結構的機器上運行的，而是通過λ演算來運行的，就是通過變數替換的方式進行，變數替換為其值或表達式，函數也替換為其表達式，並根據運算符進行計算。λ演算是圖靈完全（Turing completeness）的，但是大多數情況，函數式程序還是被編譯成（馮諾依曼機的）機器語言的指令執行的。

函數式編程的好處
由於命令式編程語言也可以通過類似函數指針的方式來實現高階函數，函數式的最主要的好處主要是不可變性帶來的。沒有可變的狀態，函數就是引用透明（Referential transparency）的和沒有副作用（No Side Effect）。

一個好處是，函數即不依賴外部的狀態也不修改外部的狀態，函數調用的結果不依賴調用的時間和位置，這樣寫的代碼容易進行推理，不容易出錯。這使得單元測試和調試都更容易。

不變性帶來的另一個好處是：由於（多個線程之間）不共享狀態，不會造成資源爭用(Race condition)，也就不需要用鎖來保護可變狀態，也就不會出現死鎖，這樣可以更好地並發起來，尤其是在對稱多處理器（SMP）架構下能夠更好地利用多個處理器（核）提供的並行處理能力。

2005年以來，計算機計算能力的增長已經不依賴CPU主頻的增長，而是依賴CPU核數的增多，如圖：

（圖片來源：The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software ）

圖中深藍色的曲線是時鐘周期的增長，可以看到從2005年前已經趨於平緩。 在多核或多處理器的環境下的程序設計是很困難的，難點就是在於共享的可變狀態。在這一背景下，這個好處就有非常重要的意義。

由於函數是引用透明的，以及函數式編程不像命令式編程那樣關注執行步驟，這個系統提供了優化函數式程序的空間，包括惰性求值和並性處理。

還有一個好處是，由於函數式語言是面向數學的抽象，更接近人的語言，而不是機器語言，代碼會比較簡潔，也更容易被理解。

函數式編程的特性
由於變數值是不可變的，對於值的操作並不是修改原來的值，而是修改新產生的值，原來的值保持不便。例如一個Point類，其moveBy方法不是改變已有Point實例的x和y坐標值，而是返回一個新的Point實例。

class Point(x: Int, y: Int){
override def toString() = "Point (" + x + ", " + y + ")"

def moveBy(deltaX: Int, deltaY: Int) = {
new Point(x + deltaX, y + deltaY)
}
}

（示例來源：Anders Hejlsberg在echDays 2010上的演講）

同樣由於變數不可變，純函數編程語言無法實現循環，這是因為For循環使用可變的狀態作為計數器，而While循環或DoWhile循環需要可變的狀態作為跳出循環的條件。因此在函數式語言里就只能使用遞歸來解決迭代問題，這使得函數式編程嚴重依賴遞歸。

通常來說，演算法都有遞推（iterative）和遞歸（recursive）兩種定義，以階乘為例，階乘的遞推定義為：

而階乘的遞歸定義

遞推定義的計算時需要使用一個累積器保存每個迭代的中間計算結果，Java代碼如下：

public static int fact(int n){
int acc = 1;

for(int k = 1; k &<= n; k++){ acc = acc * k; } return acc; }

而遞歸定義的計算的Scala代碼如下：

def fact(n: Int):Int= {
if(n == 0) return 1
n * fact(n-1)
}

我們可以看到，沒有使用循環，沒有使用可變的狀態，函數更短小，不需要顯示地使用累積器保存中間計算結果，而是使用參數n（在棧上分配）來保存中間計算結果。
（示例來源：1. Recursion）

當然，這樣的遞歸調用有更高的開銷和局限（調用棧深度），那麼盡量把遞歸寫成尾遞歸的方式，編譯器會自動優化為循環，這裡就不展開介紹了。

一般來說，遞歸這種方式於循環相比被認為是更符合人的思維的，即告訴機器做什麼，而不是告訴機器怎麼做。遞歸還是有很強大的表現力的，比如換零錢問題。

問題：假設某國的貨幣有若干面值，現給一張大面值的貨幣要兌換成零錢，問有多少種兌換方式。
遞歸解法：

def countChange(money: Int, coins: List[Int]): Int = {
if (money == 0)
1
else if (coins.size == 0 || money &< 0) 0 else countChange(money, coins.tail) + countChange(money - coins.head, coins) }

（示例來源：有趣的 Scala 語言: 使用遞歸的方式去思考）
從這個例子可以看出，函數式程序非常簡練，描述做什麼，而不是怎麼做。

函數式語言當然還少不了以下特性：

  • 高階函數（Higher-order function）
  • 偏應用函數（Partially Applied Functions）
  • 柯里化（Currying）
  • 閉包（Closure）

高階函數就是參數為函數或返回值為函數的函數。有了高階函數，就可以將復用的粒度降低到函數級別，相對於面向對象語言，復用的粒度更低。

舉例來說，假設有如下的三個函數，

def sumInts(a: Int, b: Int): Int =
if (a &> b) 0 else a + sumInts(a + 1, b)

def sumCubes(a: Int, b: Int): Int =
if (a &> b) 0 else cube(a) + sumCubes(a + 1, b)

def sumFactorials(a: Int, b: Int): Int =
if (a &> b) 0 else fact(a) + sumFactorials(a + 1, b)

分別是求a到b之間整數之和，求a到b之間整數的立方和，求a到b之間整數的階乘和。

其實這三個函數都是以下公式的特殊情況
sum_{n=a}^{b}{f(n)}
三個函數不同的只是其中的f不同，那麼是否可以抽象出一個共同的模式呢？

我們可以定義一個高階函數sum：

def sum(f: Int =&> Int, a: Int, b: Int): Int =
if (a &> b) 0
else f(a) + sum(f, a + 1, b)

其中參數f是一個函數，在函數中調用f函數進行計算，並進行求和。

然後就可以寫如下的函數

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)

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)

這樣就可以重用sum函數來實現三個函數中的求和邏輯。
（示例來源：https://d396qusza40orc.cloudfront.net/progfun/lecture_slides/week2-2.pdf）

高階函數提供了一種函數級別上的依賴注入（或反轉控制）機制，在上面的例子里，sum函數的邏輯依賴於注入進來的函數的邏輯。很多GoF設計模式都可以用高階函數來實現，如Visitor，Strategy，Decorator等。比如Visitor模式就可以用集合類的map()或foreach()高階函數來替代。

函數式語言通常提供非常強大的集合類（Collection），提供很多高階函數，因此使用非常方便。

比如說，我們想對一個列表中的每個整數乘2，在命令式編程中需要通過循環，然後對每一個元素乘2，但是在函數式編程中，我們不需要使用循環，只需要使用如下代碼：

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)

（示例來源：Programming Scala: Tackle Multi-Core Complexity on the Java Virtual Machine一書的Introduction）

其中x=&>x*2是一個匿名函數，接收一個參數x，輸出x*2。這裡也可以看出來函數式編程關注做什麼（x*2），而不關注怎麼做（使用循環控制結構）。程序員完全不關心，列表中的元素是從前到後依次計算的，還是從後到前依次計算的，是順序計算的，還是並行進行的計算，如Scala的並行集合（Parallel collection）。

使用集合類的方法，可以使對一些處理更簡單，例如上面提到的求階乘的函數，如果使用集合類，就可以寫成：

def fact(n: Int): Int = (1 to n).reduceLeft((acc,k)=&>acc*k)

其中(1 to n)生成一個整數序列，而reduceLeft()高階函數通過調用匿名函數將序列化簡。

那麼，在大數據處理框架Spark中，一個RDD就是一個集合。以詞頻統計的為例代碼如下：

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

（示例來源：https://spark.apache.org/examples.html）

示例里的flatMap()，map()，和集合類中的同名方法是一致的，這裡的map方法的參數也是一個匿名函數，將單詞變成一個元組。寫這個函數的人不用關心函數是怎麼調度的，而實際上，Spark框架會在多台計算機組成的分散式集群上完成這個計算。

此外，如果對比一下Hadoop的詞頻統計實現：WordCount - Hadoop Wiki ，就可以看出函數式編程的一些優勢。

函數式編程語言還提供惰性求值（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 = &

scala&> y
y
res3: Int = 13

scala&> y
res4: Int = 13

（示例來源：scala - What does a lazy val do?）

可以看到，在Scala的解釋器中，當定義了x變數時就列印出了「x」，而定義變數y時並沒有列印出」y「，而是在第一次引用變數y時才列印出來。

函數式編程語言一般還提供強大的模式匹配（Pattern Match）功能。在函數式編程語言中可以定義代數數據類型（Algebraic data type），通過組合已有的數據類型形成新的數據類型，如在Scala中提供case class，代數數據類型的值可以通過模式匹配進行分析。

總結
函數式編程是給軟體開發者提供的另一套工具箱，為我們提供了另外一種抽象和思考的方式。

函數式編程也有不太擅長的場合，比如處理可變狀態和處理IO，要麼引入可變變數，要麼通過Monad來進行封裝（如State Monad和IO Monad）

要判斷一個東西算不算函數式編程, 或者說一門編程語言是不是FP語言, 只看 用到/有 哪些語法特性是不夠的. 一切還需要回歸到函數式編程的初衷來, 也就是: 希望可以允許程序員用計算來表示程序, 用計算的組合來表達程序的組合. 而非函數式編程則習慣於用命令來表示程序, 用命令的順序執行來表達程序的組合.

如果在解決某個具體問題的過程中, 你的程序能完全用計算來表示, 你在組合程序的子部分得到最終程序的過程中, 使用的組合方式是計算的組合, 那麼它就可以說是函數式編程, 而與你用的什麼編程語言, 以及你在此過程中用到了哪些語言特性沒有直接的關係.

比如, 用一個簡單的例子:

程序1:

int a, b, r;
void add_abs() {
scanf("%d %d", a, b);
r = abs(a) + abs(b)
printf("%d", r);
}

程序2:

int add_abs(int a, int b) {
int r = 0;
r += abs(a);
r += abs(b);
return r;
}

程序3:

int add_abs(int a, int b) {
return abs(a) + abs(b);
}

程序1 是用命令來表示程序, 用命令的順序執行來表示程序的組合, 不算函數式
程序2 是用函數來表示程序, 但在內部是用命令的順序執行來實現, 不太函數式
程序3 是用函數來表示程序, 用函數的組合來表達程序的組合, 是完全的函數式編程

注意我們的判斷標準關注的是程序在人(也就是程序員)腦中的狀態, 它關心的是某個人在思考問題的時候, 程序是以什麼樣的概念存在於腦中的 -- 是指令的序列呢, 還是計算呢 -- 而跟程序在機器中執行的狀態無關, 畢竟函數式的代碼和非函數式的代碼最終編譯得到的機器碼完全有可能是一樣的. 所以這裡重要的區別在於人如何理解程序, 而非程序如何執行.

所以對於某段代碼算不算函數式編程這個問題, 我覺得這跟它用的什麼編程語言並沒有什麼直接的關係 (比如我在程序3中用的同樣是非函數式語言), 它跟問題本身有關, 跟具體的實現思路有關, 甚至具體到一個程序員, 它還跟這個程序員如何去解讀這段程序有關 (比如當我把程序2中的add_abs看作黑盒的時候, 我忽略它的實現, 而在其它地方把它當做純函數去使用, 它也完全可能成為函數式代碼的一部分).

函數式編程思維, 就是用計算(函數)來表示程序, 用計算(函數)的組合來表達程序的組合的思維方式.

用haskell（純函數式編程語言）別彆扭扭的去寫一個稍微有點規模的應用就會慢慢明白了，haskell會逼你只能用函數式的特性來解決問題，一定會碰到有的需求不知道怎麼實現的時候，這個時候去請教，收益最大。

站在門外，讀再多的文章你也不會理解什麼是函數式編程思想的。

模塊復用和訪存控制。


1. 模塊復用

「通過少量的表達式構造規則和靈活的表達式組合方式，可以構造足夠實用、強大的程序語言。」

變數、函數、對象、類型等等都是可以復用的程序元素。

第一階函數：函數可以被賦給變數，可以作為其他函數的參數、返回值。函數的復用更自由、方便。

// JavaScript
function outer() {
var x = 11;
function inner() {
x = x + 1;
console.log(x);
}

return inner; // 函數作為返回值
}

// 函數賦給變數
var test = outer();

抽象數據類型：在處理遞歸結構時方便很多（如數據結構中的樹，編譯器的Parser等）
以TAPL第三章untyped arith語言的解釋器為例（部分）

(* Ocaml *)
type term =
TmTrue of info
| TmFalse of info
| TmIf of info * term * term * term
| TmSucc of info * term
| TmPred of info * term
| TmIsZero of info * term

// Scala
// case class/object可以實現ADT
sealed trait Term
case object TmTrue extends Term
case object TmFalse extends Term
case class TmIf(cond: Term, t1: Term, t2: Term) extends Term
case object TmZero extends Term
case class TmPred(t: Term) extends Term
case class TmIsZero(t: Term) extends Term

在ML、Haskell等語言中，遞歸函數、數據結構的定義往往會用到模式匹配 語法
模式匹配通常比if-else和switch更強大、高效。（註：初學者在使用時常犯錯誤

多樣化的多態
函數重載（ad-hoc多態）、泛型（參數化多態）和subtyping。
Haskell的typeclass，Ocaml的Module system，Common lisp的mutiple dispatch。。。
當然，C++的模板+模板特化可以模擬typeclass，Java不也有泛型么（黑）。。

2. 訪存控制

變數的不可變性
"Aliasing+mutation=&>內存問題，aliasing+mutation+ordering=&>數據競爭。想要安全，就應該要麼消除aliasing，要麼消除mutation。"

純函數式語言如Haskell，號稱「變數的不可變性」（immutable)，即只綁定一次，完全無副作用。這種理念影響了Scala、Rust等現代語言

如Scala中val和var的區別，標準庫分別提供immutable和mutable collections。


類型相關的許可權
dynamic type一時爽。。當然Scheme/Clojure等語言也是動態類型的。。
這裡要強調的是靜態強類型。在函數式語言中它得到了充分的發展。

前面討論的內容可能並不限於「函數式」，也必然有些內容未涉及。
待補充。。

程序復用和許可權控制，在命令式、面向對象中也有，但是函數式語言中它們做得更極致，或者說，給了人們新的視角：
為什麼一定要把函數放在類中（Java），
為什麼要函數指針用多了那麼彆扭（C），
為什麼有些設計模式實現起來那麼地「繞」，
為什麼不能擺脫和鎖的鬥爭。。
...
搜「函數式編程」有真相。。

我畢設就搞的這個，不要攔著我！！！

《函數式編程（Functional Programming）簡介》
http://janfan.github.io/chinese/2015/05/18/functional-programming.html
（論文寫得還沒博客認真這種事情我會亂說？）

談談我的理解:

背景介紹: 現在工作全職fp, 算是fp工業界老兵了, 有幾十萬行OCaml的經驗, OCaml 2012-2013 core contributor, original author of bucklescript(Bloomberg Open-sources BuckleScript, JavaScript Backend for OCaml), 學習編程的入門語言C/C++

結論: 函數式編程是一種風格 與編程語言無關， 面向對象也是一種風格 與編程語言無關，兩種風格並不矛盾，可以結合的- 叫 functional object(Objects in OCaml)

函數式編程其實是一種非常簡單的風格 比命令式和面向對象還要簡單 。主要理論基礎是lambda 演算，規則也很簡單.

無類型的lambda 演算其實規則很簡單 只有三條

1. 變數 (variable)
2. 函數 (lambda-abstraction)
3. 替代 (beta-reduction)

任何支持函數的語言都可以進行函數式風格的編程 注意到與命令式風格不同的是沒有賦值，這意味著reason 程序的時候每個變數的值是不變的 不用考慮程序變數隨著時間的變化 -- 大大降低了程序的複雜性。

既然C/C++(98) 也能進行函數式風格的編程 為什麼不認為它是一門函數式語言呢，因為需要容易的進行函數式編程需要以下幾個語言特性支持

1. closure
按照上面的三條規則函數式是first class 的 是可以直接傳遞作為參數的，而因為lambda演算作用於是lexical scope 的，variable capture 意味著語言要支持GC才能更方便的操作。 這意味著像Java(8以前), C/C++ 這兩門工業界語言函數式編程並不非常適合.

2. 高階類型推斷
因為函數可以作為參數，其類型可以非常複雜 比如下面的函數類型其實非常普遍:

val callCC : (("a -&> "b -&> "c) -&> ("a -&> "c) -&> "d) -&> ("a -&> "c) -&> "d

如果沒有類型推斷，其實很難寫對或者理解它的語義

3. tail-call
因為函數式風格沒有賦值，也就沒有for循環， 要實現循環操作 只能通過遞歸調用, 比如下面簡單的例子:

let rec even n = if n = 0 then true else if n = 1 then false else odd (n - 1)
and odd n = if n = 1 then true else if n = 0 then false else even (n - 1)

這需要編譯器保證上面的例子不能有stackoverflow 能提供這樣保證的編譯器並不多，比如所謂的 "函數式" 語言scala 就不能提供這種保證 也就實際上不是函數式語言.


相比函數式風格我覺得更重要的一個語言特性的時代數數據類型和模式匹配，這裡就不說了

把 OOP 裡面的概念全部換成對偶的，恭喜你學會 FP 了（逃
「Lens 無非是一個余狀態（Co-State）余單子（Comonad）上面的一個余代數（Coalgebra）而已嘛，有什麼難理解的？」

函數式編程在使用的時候的特點就是，你已經再也不知道數據是從哪裡來了，每一個函數都是為了用小函數組織成更大的函數，函數的參數也是函數，函數返回的也是函數，最後得到一個超級牛逼的函數，就等著別人用他來寫一個main函數把數據灌進去了。

至於說要如何體會這樣的東西，題主把Haskell學會了就明白了。

寫了一篇專欄文章，簡單介紹了一下函數式編程的來龍去脈 React世界的函數式編程(Functional Programming) - 知乎專欄

【轉載】傻瓜函數編程
原始鏈接:
justinyhuang/Functional-Programming-For-The-Rest-of-Us-Cn · GitHub

開篇

我們這些碼農做事都是很拖拉的。每天例行報到後，先來點咖啡，看看郵件還有RSS訂閱的文章。然後翻翻新聞還有那些技術網站上的更新，再過一遍編程論壇口水區里那些無聊的論戰。最後從頭把這些再看一次以免錯過什麼精彩的內容。然後就可以吃午飯了。飯飽過後，回來盯著IDE發一會呆，再看看郵箱，再去搞杯咖啡。光陰似箭，可以回家了……
（在被眾人鄙視之前）我唯一想說的是，在這些拖拉的日子裡總會時不時讀到一些不明覺厲的文章。如果沒有打開不應該打開的網站，每隔幾天你都可以看到至少一篇這樣的東西。它們的共性：難懂，耗時，於是這些文章就慢慢的堆積成山了。很快你就會發現自己已經累積了一堆的收藏鏈接還有數不清的PDF文件，此時你只希望隱入一個杳無人煙的深山老林里什麼也不做，用一年半載好好的消化這些私藏寶貝。當然，我是說最好每天還是能有人來給送吃的順帶幫忙打掃衛生倒垃圾，哇哈哈。

我不知道你都收藏了些什麼，我的閱讀清單裡面相當大部分都是函數式編程相關的東東：基本上是最難啃的。這些文章充斥著無比枯燥的教科書語言，我想就連那些在華爾街浸淫10年以上的大牛都無法搞懂這些函數式編程（簡稱FP）文章到底在說什麼。你可以去花旗集團或者德意志銀行找個項目經理來問問1：你們為什麼要選JMS而不用Erlang？答案基本上是：我認為這個學術用的語言還無法勝任實際應用。可是，現有的一些系統不僅非常複雜還需要滿足十分嚴苛的需求，它們就都是用函數式編程的方法來實現的。這，就說不過去了。
關於FP的文章確實比較難懂，但我不認為一定要搞得那麼晦澀。有一些歷史原因造成了這種知識斷層，可是FP概念本身並不難理解。我希望這篇文章可以成為一個「FP入門指南」，幫助你從指令式編程走向函數式編程。先來點咖啡，然後繼續讀下去。很快你對FP的理解就會讓同事們刮目相看了。

什麼是函數式編程（Functional Programming，FP）？它從何而來？可以吃嗎？倘若它真的像那些鼓吹FP的人說的那麼好，為什麼實際應用中那麼少見？為什麼只有那些在讀博士的傢伙想要用它？而最重要的是，它母親的怎麼就那麼難學？那些所謂的closure、continuation，currying，lazy evaluation還有no side effects都是什麼東東（譯者：本著保留專用術語的原則，此處及下文類似情形均不譯）？如果沒有那些大學教授的幫忙怎樣把它應用到實際工程里去？為什麼它和我們熟悉的萬能而神聖的指令式編程那麼的不一樣？
我們很快就會解開這些謎團。剛才我說過實際工程和學術界之間的知識斷層是有其歷史原因的，那麼就先讓我來解釋一下這個問題。答案，就在接下來的一次公園漫步中：

公園漫步

時間機器啟動……我們來到公元前380年，也就是2000多年前的雅典城外。這是一個陽光明媚的久違的春天，柏拉圖和一個帥氣的小男僕走在一片橄欖樹蔭下。他們正準備前往一個學院。天氣很好，吃得很飽，漸漸的，兩人的談話轉向了哲學。

「你看那兩個學生，哪一個更高一些？」，柏拉圖小心的選擇用字，以便讓這個問題更好的引導眼前的這個小男孩。
小男僕望向水池旁邊的兩個男生，「他們差不多一樣高。」。
「『差不多一樣高』是什麼意思？」柏拉圖問。
「嗯……從這裡看來他們是一樣高的，但是如果走近一點我肯定能看出差別來。」
柏拉圖笑了。他知道這個小孩已經朝他引導的方向走了。「這麼說來你的意思是世界上沒有什麼東西是完全相同的咯？」
思考了一會，小男孩回答：「是的。萬物之間都至少有一丁點差別，哪怕我們無法分辨出來。」
說到點子上了！「那你說，如果世界上沒有什麼東西是完全相等的，你怎麼理解『完全相等』這個概念？」
小男僕看起來很困惑。「這我就不知道了。」

這是人類第一次試圖了解數學的本質。柏拉圖認為我們所在的世界中，萬事萬物都是完美模型的一個近似。他同時意識到雖然我們不能感受到完美的模型，但這絲毫不會阻止我們了解完美模型的概念。柏拉圖進而得出結論：完美的數學模型只存在於另外一個世界，而因為某種原因我們卻可以通過聯繫著這兩個世界的一個紐帶來認識這些模型。一個簡單的例子就是完美的圓形。沒有人見過這樣的一個圓，但是我們知道怎樣的圓是完美的圓，而且可以用公式把它描述出來。

如此說來，什麼是數學呢？為什麼可以用數學法則來描述我們的這個宇宙？我們所處的這個世界中萬事萬物都可以用數學來描述嗎？2 數理哲學是一門很複雜的學科。它和其他多數哲學一樣，更著重於提出問題而不是給出答案。數學就像拼圖一樣，很多結論都是這樣推導出來的：先是確立一些互不衝突的基礎原理，以及一些操作這些原理的規則，然後就可以把這些原理以及規則拼湊起來形成新的更加複雜的規則或是定理了。數學家把這種方法稱為「形式系統」或是「演算」。如果你想做的話，可以用形式系統描述俄羅斯方塊這個遊戲。而事實上，俄羅斯方塊這個遊戲的實現，只要它正確運行，就是一個形式系統。只不過它以一種不常見的形式表現出來罷了。

如果半人馬阿爾法上有文明存在的話，那裡的生物可能無法解讀我們的俄羅斯方塊形式系統甚至是簡單的圓形的形式系統，因為它們感知世界的唯一器官可能只有鼻子（譯者：偶的媽你咋知道？）也許它們是無法得知俄羅斯方塊的形式系統了，但是它們很有可能知道圓形。它們的圓形我們可能沒法解讀，因為我們的鼻子沒有它們那麼靈敏（譯者：那狗可以么？）可是只要越過形式系統的表示方式（比如通過使用「超級鼻子」之類的工具來感知這些用味道表示的形式系統，然後使用標準的解碼技術把它們翻譯成人類能理解的語言），那麼任何有足夠智力的文明都可以理解這些形式系統的本質。
有意思的是，哪怕宇宙中完全不存在任何文明，類似俄羅斯方塊還有圓形這樣的形式系統依舊是成立的：只不過沒有智慧生物去發現它們而已。這個時候如果忽然一個文明誕生了，那麼這些具有智慧的生物就很有可能發現各種各樣的形式系統，並且用它們發現的系統去描述各種宇宙法則。不過它們可能不會發現俄羅斯方塊這樣的形式系統，因為在它們的世界裡沒有俄羅斯方塊這種東西嘛。有很多像俄羅斯方塊這樣的形式系統是與客觀世界無關的，比如說自然數，很難說所有的自然數都與客觀世界有關，隨便舉一個超級大的數，這個數可能就和世界上任何事物無關，因為這個世界可能不是無窮大的。

歷史回眸3

再次啟動時間機……這次到達的是20世紀30年代，離今天近了很多。無論新舊大陸，經濟大蕭條都造成了巨大的破壞。社會各階層幾乎每一個家庭都深受其害。只有極其少數的幾個地方能讓人們免於遭受窮困之苦。幾乎沒有人能夠幸運的在這些避難所里度過危機，注意，我說的是幾乎沒有，還真的有這麼些幸運兒，比如說當時普林斯頓大學的數學家們。

新建成的哥特式辦公樓給普林斯頓大學帶來一種天堂般的安全感。來自世界各地的邏輯學者應邀來到普林斯頓，他們將組建一個新的學部。正當大部分美國人還在為找不到一片麵包做晚餐而發愁的時候，在普林斯頓卻是這樣一番景象：高高的天花板和木雕包覆的牆，每天品茶論道，漫步叢林。 一個名叫阿隆佐·邱奇(Alonzo Church)的年輕數學家就過著這樣優越的生活。阿隆佐本科畢業於普林斯頓後被留在研究院。他覺得這樣的生活完全沒有必要，於是他鮮少出現在那些數學茶會中也不喜歡到樹林里散心。阿隆佐更喜歡獨處：自己一個人的時候他的工作效率更高。儘管如此他還是和普林斯頓學者保持著聯繫，這些人當中有艾倫·圖靈、約翰·馮·諾伊曼、庫爾特·哥德爾。
這四個人都對形式系統感興趣。相對於現實世界，他們更關心如何解決抽象的數學問題。而他們的問題都有這麼一個共同點：都在嘗試解答關於計算的問題。諸如：如果有一台擁有無窮計算能力的超級機器，可以用來解決什麼問題？它可以自動的解決這些問題嗎？是不是還是有些問題解決不了，如果有的話，是為什麼？如果這樣的機器採用不同的設計，它們的計算能力相同嗎？
在與這些人的合作下，阿隆佐設計了一個名為lambda演算的形式系統。這個系統實質上是為其中一個超級機器設計的編程語言。在這種語言裡面，函數的參數是函數，返回值也是函數。這種函數用希臘字母lambda（λ），這種系統因此得名4。有了這種形式系統，阿隆佐終於可以分析前面的那些問題並且能夠給出答案了。
除了阿隆佐·邱奇，艾倫·圖靈也在進行類似的研究。他設計了一種完全不同的系統（後來被稱為圖靈機），並用這種系統得出了和阿隆佐相似的答案。到了後來人們證明了圖靈機和lambda演算的能力是一樣的。

如果二戰沒有發生，這個故事到這裡就應該結束了，我的這篇小文沒什麼好說的了，你們也可以去看看有什麼其他好看的文章。可是二戰還是爆發了，整個世界陷於火海之中。那時的美軍空前的大量使用炮兵。為了提高轟炸的精度，軍方聘請了大批數學家夜以繼日的求解各種差分方程用於計算各種火炮發射數據表。後來他們發現單純手工計算這些方程太耗時了，為了解決這個問題，各種各樣的計算設備應運而生。IBM製造的Mark一號就是用來計算這些發射數據表的第一台機器。Mark一號重5噸，由75萬個零部件構成，每一秒可以完成3次運算。
戰後，人們為提高計算能力而做出的努力並沒有停止。1949年第一台電子離散變數自動計算機誕生並取得了巨大的成功。它是馮·諾伊曼設計架構的第一個實例，也是一台現實世界中實現的圖靈機。相比他的這些同事，那個時候阿隆佐的運氣就沒那麼好了。
到了50年代末，一個叫John McCarthy的MIT教授（他也是普林斯頓的碩士）對阿隆佐的成果產生了興趣。1958年他發明了一種列表處理語言（Lisp），這種語言是一種阿隆佐lambda演算在現實世界的實現，而且它能在馮·諾伊曼計算機上運行！很多計算機科學家都認識到了Lisp強大的能力。1973年在MIT人工智慧實驗室的一些程序員研發出一種機器，並把它叫做Lisp機。於是阿隆佐的lambda演算也有自己的硬體實現了！

函數式編程

函數式編程是阿隆佐思想的在現實世界中的實現。不過不是全部的lambda演算思想都可以運用到實際中，因lambda演算在設計的時候就不是為了在各種現實世界中的限制下工作的。所以，就像面向對象的編程思想一樣，函數式編程只是一系列想法，而不是一套嚴苛的規定。有很多支持函數式編程的程序語言，它們之間的具體設計都不完全一樣。在這裡我將用Java寫的例子介紹那些被廣泛應用的h函數式編程思想（沒錯，如果你是受虐狂你可以用Java寫出函數式程序）。在下面的章節中我會在Java語言的基礎上，做一些修改讓它變成實際可用的函數式編程語言。那麼現在就開始吧。

Lambda演算在最初設計的時候就是為了研究計算相關的問題。所以函數式編程主要解決的也是計算問題，而出乎意料的是，是用函數來解決的！（譯者：請理解原作者的苦心，我想他是希望加入一點調皮的風格以免讀者在中途睡著或是轉檯……）。函數就是函數式編程中的基礎元素，可以完成幾乎所有的操作，哪怕最簡單的計算，也是用函數完成的。我們通常理解的變數在函數式編程中也被函數代替了：在函數式編程中變數僅僅代表某個表達式（這樣我們就不用把所有的代碼都寫在同一行里了）。所以我們這裡所說的『變數』是不能被修改的。所有的變只能被附一次初值。在Java中就意味著每一個變數都將被聲明為final（如果你用C++，就是const）。在FP中，沒有非final的變數。


final int i = 5;
final int j = i + 3;

既然FP中所有的變數都是final的，可以引出兩個規定：一是變數前面就沒有必要再加上final這個關鍵字了，二是變數就不能再叫做『變數』了……於是現在開始對Java做兩個改動：所有Java中聲明的變數默認為final，而且我們把所謂的『變數』稱為『符號』。
到現在可能會有人有疑問：這個新創造出來的語言可以用來寫什麼有用的複雜一些的程序嗎？畢竟，如果每個符號的值都是不能修改的，那麼我們就什麼東西都不能改變了！別緊張，這樣的說法不完全正確。阿隆佐在設計lambda演算的時候他並不想要保留狀態的值以便稍後修改這些值。他更關心的是基於數據之上的操作（也就是更容易理解的「計算」）。而且，lambda演算和圖靈機已經被證明了是具有同樣能力的系統，因此指令式編程能做到的函數式編程也同樣可以做到。那麼，怎樣才能做到呢？
事實上函數式程序是可以保存狀態的，只不過它們用的不是變數，而是函數。狀態保存在函數的參數中，也就是說在棧上。如果你需要保存一個狀態一段時間並且時不時的修改它，那麼你可以編寫一個遞歸函數。舉個例子，試著寫一個函數，用來反轉一個Java的字元串。記住咯，這個程序里的變數都是默認為final的5。


String reverse(String arg) {
if(arg.length == 0) {
return arg;
}
else {
return reverse(arg.substring(1, arg.length)) + arg.substring(0, 1);
}
}

這個方程運行起來會相對慢一些，因為它重複調用自己6。同時它也會大量的消耗內存，因為它會不斷的分配創建內存對象。無論如何，它是用函數式編程思想寫出來的。這時候可能有人要問了，為什麼要用這種奇怪的方式編寫程序呢？嘿，我正準備告訴你。

FP之優點

你大概已經在想：上面這種怪胎函數怎麼也不合理嘛。在我剛開始學習FP的時候我也這樣想的。不過後來我知道我是錯的。使用這種方式編程有很多好處。其中一些是主觀的。比如說有人認為函數式程序更容易理解。這個我就不說了，哪怕街上隨便找個小孩都知道『容易理解』是多麼主觀的事情。幸運的是，客觀方面的好處還有很多。

單元測試

因為FP中的每個符號都是final的，於是沒有什麼函數會有副作用。誰也不能在運行時修改任何東西，也沒有函數可以修改在它的作用域之外修改什麼值給其他函數繼續使用（在指令式編程中可以用類成員或是全局變數做到）。這意味著決定函數執行結果的唯一因素就是它的返回值，而影響其返回值的唯一因素就是它的參數。
這正是單元測試工程師夢寐以求的啊。現在測試程序中的函數時只需要關注它的參數就可以了。完全不需要擔心函數調用的順序，也不用費心設置外部某些狀態值。唯一需要做的就是傳遞一些可以代表邊界條件的參數給這些函數。相對於指令式編程，如果FP程序中的每一個函數都能通過單元測試，那麼我們對這個軟體的質量必將信心百倍。反觀Java或者C++，僅僅檢查函數的返回值是不夠的：代碼可能修改外部狀態值，因此我們還需要驗證這些外部的狀態值的正確性。在FP語言中呢，就完全不需要。

調試查錯

如果一段FP程序沒有按照預期設計那樣運行，調試的工作幾乎不費吹灰之力。這些錯誤是百分之一百可以重現的，因為FP程序中的錯誤不依賴於之前運行過的不相關的代碼。而在一個指令式程序中，一個bug可能有時能重現而有些時候又不能。因為這些函數的運行依賴於某些外部狀態， 而這些外部狀態又需要由某些與這個bug完全不相關的代碼通過某個特別的執行流程才能修改。在FP中這種情況完全不存在：如果一個函數的返回值出錯了，它一直都會出錯，無論你之前運行了什麼代碼。
一旦問題可以重現，解決它就變得非常簡單，幾乎就是一段愉悅的旅程。中斷程序的運行，檢查一下棧，就可以看到每一個函數調用時使用的每一個參數，這一點和指令式代碼一樣。不同的是指令式程序中這些數據還不足夠，因為函數的運行還可能依賴於成員變數，全局變數，還有其他類的狀態（而這些狀態又依賴於類似的變數）。FP中的函數只依賴於傳給它的參數，而這些參數就在眼前！還有，對指令式程序中函數返回值的檢查並不能保證這個函數是正確運行的。還要逐一檢查若干作用域以外的對象以確保這個函數沒有對這些牽連的對象做出什麼越軌的行為（譯者：好吧，翻譯到這裡我自己已經有點激動了）。對於一個FP程序，你要做的僅僅是看一下函數的返回值。
把棧上的數據過一遍就可以得知有哪些參數傳給了什麼函數，這些函數又返回了什麼值。當一個返回值看起來不對頭的那一刻，跳進這個函數看看裡面發生了什麼。一直重複跟進下去就可以找到bug的源頭！

並發執行

不需要任何改動，所有FP程序都是可以並發執行的。由於根本不需要採用鎖機制，因此完全不需要擔心死鎖或是並發競爭的發生。在FP程序中沒有哪個線程可以修改任何數據，更不用說多線程之間了。這使得我們可以輕鬆的添加線程，至於那些禍害並發程序的老問題，想都不用想！
既然是這樣，為什麼沒有人在那些高度並行的那些應用程序中採用FP編程呢？事實上，這樣的例子並不少見。愛立信開發了一種FP語言，名叫Erlang，並應用在他們的電信交換機上，而這些交換機不僅容錯度高而且拓展性強。許多人看到了Erlang的這些優勢也紛紛開始使用這一語言。在這裡提到的電信交換控制系統遠遠要比華爾街上使用的系統具有更好的擴展性也更可靠。事實上，用Erlang搭建的系統並不具備可擴展性和可靠性，而Java可以提供這些特性。Erlang只是像岩石一樣結實不容易出錯而已。
FP關於並行的優勢不僅於此。就算某個FP程序本身只是單線程的，編譯器也可以將其優化成可以在多CPU上運行的並發程序。以下面的程序為例：


String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);

如果是函數式程序，編譯器就可以對代碼進行分析，然後可能分析出生成字元串s1和s2的兩個函數可能會比較耗時，進而安排它們並行運行。這在指令式編程中是無法做到的，因為每一個函數都有可能修改其外部狀態，然後接下來的函數又可能依賴於這些狀態的值。在函數式編程中，自動分析代碼並找到適合併行執行的函數十分簡單，和分析C的內聯函數沒什麼兩樣。從這個角度來說用FP風格編寫的程序是「永不過時」的（雖然我一般不喜歡說大話空話，不過這次就算個例外吧）。硬體廠商已經沒辦法讓CPU運行得再快了。他們只能靠增加CPU核的數量然後用並行來提高運算的速度。這些廠商故意忽略一個事實：只有可以並行的軟體才能讓你花大價錢買來的這些硬體物有所值。指令式的軟體中只有很小一部分能做到跨核運行，而所有的函數式軟體都能實現這一目標，因為FP的程序從一開始就是可以並行運行的。

熱部署

在Windows早期，如果要更新系統那可是要重啟電腦的，而且還要重啟很多次。哪怕只是安裝一個新版本的播放器。到了XP的時代這種情況得到比較大的改善，儘管還是不理想（我工作的時候用的就是Windows，就在現在，我的系統托盤上就有個討厭的圖標，我不重啟機子就不消失）。這一方面Unix好一些，曾經。只需要暫停一些相關的部件而不是整個操作系統，就可以安裝更新了。雖然是要好一些了，對很多伺服器應用來說這也還是不能接受的。電信系統要求的是100%的在線率，如果一個救急電話因為系統升級而無法撥通，成千上萬的人就會因此喪命。同樣的，華爾街的那些公司怎麼也不能說要安裝軟體而在整個周末停止他們系統的服務。
最理想的情況是更新相關的代碼而不用暫停系統的其他部件。對指令性程序來說是不可能的。想想看，試著在系統運行時卸載掉一個Java的類然後再載入這個類的新的實現，這樣做的話系統中所有該類的實例都會立刻不能運行，因為該類的相關狀態已經丟失了。這種情況下可能需絞盡腦汁設計複雜的版本控制代碼，需要將所有這種類正在運行的實例序列化，逐一銷毀它們，然後創建新類的實例，將現有數據也序列化後裝載到這些新的實例中，最後希望負責裝載的程序可以正確的把這些數據移植到新實例中並正常的工作。這種事很麻煩，每次有新的改動都需要手工編寫裝載程序來完成更新，而且這些裝載程序還要很小心，以免破壞了現有對象之間的聯繫。理論上是沒問題，可是實際上完全行不通。
FP的程序中所有狀態就是傳給函數的參數，而參數都是儲存在棧上的。這一特性讓軟體的熱部署變得十分簡單。只要比較一下正在運行的代碼以及新的代碼獲得一個diff，然後用這個diff更新現有的代碼，新代碼的熱部署就完成了。其它的事情有FP的語言工具自動完成！如果還有人認為這隻存在於科幻小說中，他需要再想想：多年來Erlang工程師已經使用這種技術對它們的系統進行升級而完全不用暫停運行了。

機器輔助優化及證明

FP語言有一個特性很有意思，那就是它們是可以用數學方法來分析的。FP語言本身就是形式系統的實現，只要是能在紙上寫出來的數學運算就可以用這種語言表述出來。於是只要能夠用數學方法證明兩段代碼是一致的，編譯器就可以把某段代碼解析成在數學上等同的但效率又更高的另外一段代碼7。 關係資料庫已經用這種方法進行優化很多年了。沒有理由在常規的軟體行業就不能應用這種技術。 另外，還可以用這種方法來證明代碼的正確性，甚至可以設計出能夠自動分析代碼並為單元測試自動生成邊緣測試用例的工具出來！對於那些對缺陷零容忍的系統來說，這一功能簡直就是無價之寶。例如心臟起搏器，例如飛行管控系統，這幾乎就是必須滿足的需求。哪怕你正在開發的程序不是為了完成什麼重要核心任務，這些工具也可以幫助你寫出更健壯的程序，直接甩競爭對手n條大街。

高階函數

我還記得在了解到FP以上的各種好處後想到：「這些優勢都很吸引人，可是，如果必須非要用這種所有變數都是final的蹩腳語言，估計還是不怎麼實用吧」。其實這樣的想法是不對的。對於Java這樣的指令式語言來說，如果所有的變數都是必須是final的，那麼確實很束手束腳。然而對函數式語言來說，情況就不一樣了。函數式語言提供了一種特別的抽象工具，這種工具將幫助使用者編寫FP代碼，讓他們甚至都沒想到要修改變數的值。高階函數就是這種工具之一。
FP語言中的函數有別於Java或是C。可以說這種函數是一個全集：Java函數可以做到的它都能做，同時它還有更多的能力。首先，像在C里寫程序那樣創建一個函數：


int add(int i, int j) {
return i + j;
}

看起來和C程序沒什麼區別，但是很快你就可以看出區別來。接下來我們擴展Java的編譯器以便支持這種代碼，也就是說，當我們寫下以上的程序編譯器會把它轉化成下面的Java程序（別忘了，所有的變數都是final的）：


class add_function_t {
int add(int i, int j) {
return i + j;
}
}

add_function_t add = new add_function_t();

在這裡，符號add並不是一個函數，它是只有一個函數作為其成員的簡單的類。這樣做有很多好處，可以在程序中把add當成參數傳給其他的函數，也可以把add賦給另外一個符號，還可以在運行時創建add_function_t的實例然後在不再需要這些實例的時候由系統回收機制處理掉。這樣做使得函數成為和integer或是string這樣的第一類對象。對其他函數進行操作（比如說把這些函數當成參數）的函數，就是所謂的高階函數。別讓這個看似高深的名字嚇倒你（譯者：好死不死起個這個名字，初一看還準備搬出已經塵封的高數教材……），它和Java中操作其他類（也就是把一個類實例傳給另外的類）的類沒有什麼區別。可以稱這樣的類為「高階類」，但是沒人會在意，因為Java圈裡就沒有什麼很強的學術社團。（譯者：這是高級黑嗎？）
那麼什麼時候該用高階函數，又怎樣用呢？我很高興有人問這個問題。設想一下，你寫了一大堆程序而不考慮什麼類結構設計，然後發現有一部分代碼重複了幾次，於是你就會把這部分代碼獨立出來作為一個函數以便多次調用（所幸學校里至少會教這個）。如果你發現這個函數里有一部分邏輯需要在不同的情況下實現不同的行為，那麼你可以把這部分邏輯獨立出來作為一個高階函數。搞暈了？下面來看看我工作中的一個真實的例子。

假設有一段Java的客戶端程序用來接收消息，用各種方式對消息做轉換，然後發給一個伺服器。


class MessageHandler {
void handleMessage(Message msg) {
// ...
msg.setClientCode("ABCD_123");
// ...

sendMessage(msg);
}

// ...
}

再進一步假設，整個系統改變了，現在需要發給兩個伺服器而不再是一個了。系統其他部分都不變，唯獨客戶端的代碼需要改變：額外的那個伺服器需要用另外一種格式發送消息。應該如何處理這種情況呢？我們可以先檢查一下消息要發送到哪裡，然後選擇相應的格式把這個消息發出去：


class MessageHandler {
void handleMessage(Message msg) {
// ...
if(msg.getDestination().equals("server1") {
msg.setClientCode("ABCD_123");
} else {
msg.setClientCode("123_ABC");
}
// ...

sendMessage(msg);
}

// ...
}

可是這樣的實現是不具備擴展性的。如果將來需要增加更多的伺服器，上面函數的大小將呈線性增長，使得維護這個函數最終變成一場噩夢。面向對象的編程方法告訴我們，可以把MessageHandler變成一個基類，然後將針對不同格式的消息編寫相應的子類。


abstract class MessageHandler {
void handleMessage(Message msg) {
// ...
msg.setClientCode(getClientCode());
// ...

sendMessage(msg);
}

abstract String getClientCode();

// ...
}

class MessageHandlerOne extends MessageHandler {
String getClientCode() {
return "ABCD_123";
}
}

class MessageHandlerTwo extends MessageHandler {
String getClientCode() {
return "123_ABCD";
}
}

這樣一來就可以為每一個接收消息的伺服器生成一個相應的類對象，添加伺服器就變得更加容易維護了。可是，這一個簡單的改動引出了很多的代碼。僅僅是為了支持不同的客戶端行為代碼，就要定義兩種新的類型！現在來試試用我們剛才改造的語言來做同樣的事情，注意，這種語言支持高階函數：


class MessageHandler {
void handleMessage(Message msg, Function getClientCode) {
// ...
Message msg1 = msg.setClientCode(getClientCode());
// ...

sendMessage(msg1);
}

// ...
}

String getClientCodeOne() {
return "ABCD_123";
}

String getClientCodeTwo() {
return "123_ABCD";
}

MessageHandler handler = new MessageHandler();
handler.handleMessage(someMsg, getClientCodeOne);

在上面的程序里，我們沒有創建任何新的類型或是多層類的結構。僅僅是把相應的函數作為參數進行傳遞，就做到了和用面向對象編程一樣的事情，而且還有額外的好處：一是不再受限於多層類的結構。這樣做可以做運行時傳遞新的函數，可以在任何時候改變這些函數，而且這些改變不僅更加精準而且觸碰的代碼更少。這種情況下編譯器其實就是在替我們編寫面向對象的「粘合」代碼（譯者：又稱膠水代碼，粘接代碼）！除此之外我們還可以享用FP編程的其他所有優勢。函數式編程能提供的抽象服務還遠不止於此。高階函數只不過是個開始。

Currying

我遇見的大多數碼農都讀過「四人幫」的那本《設計模式》。任何稍有自尊心的碼農都會說這本書和語言無關，因此無論你用什麼編程語言，當中提到的那些模式大體上適用於所有軟體工程。聽起來很厲害，然而事實卻不是這樣。
函數式語言的表達能力很強。用這種語言編程的時候基本不需要設計模式，因為這種語言層次已經足夠高，使得使用者可以以概念編程，從而完全不需要設計模式了。以適配器模式為例（有人知道這個模式和外觀模式有什麼區別嗎？怎麼覺得有人為了出版合同的要求而硬生生湊頁數？）（譯者：您不愧是高級黑啊）。對於一個支持currying技術的語言來說，這個模式就是多餘的。
在Jaya中最有名的適配器模式就是在其「默認」抽象單元中的應用：類。在函數式語言中這種模式其實就是函數。在這個模式中，一個介面被轉換成另外一個介面，讓不同的用戶代碼調用。接下來就有一個適配器模式的例子：


int pow(int i, int j);
int square(int i)
{
return pow(i, 2);
}

上面的代碼中square函數計算一個整數的平方，這個函數的介面被轉換成計算一個整數的任意整數次冪。在學術圈裡這種簡單的技術就被叫做currying（因為邏輯學家哈斯凱爾·加里用其數學技巧將這種技術描述出來，於是就以他的名字來命名了）。在一個FP語言中函數（而不是類）被作為參數進行傳遞，currying常常用於轉化一個函數的介面以便於其他代碼調用。函數的介面就是它的參數，於是currying通常用於減少函數參數的數量（見前例）。
函數式語言生來就支持這一技術，於是沒有必要為某個函數手工創建另外一個函數去包裝並轉換它的介面，這些函數式語言已經為你做好了。我們繼續拓展Java來支持這一功能。


square = int pow(int i, 2);

上面的語句實現了一個平方計算函數，它只需要一個參數。它會繼而調用pow函數並且把第二個參數置為2。編譯過後將生成以下Java代碼：


class square_function_t {
int square(int i) {
return pow(i, 2);
}
}
square_function_t square = new square_function_t();

從上面的例子可以看到，很簡單的，函數pow的封裝函數就創建出來了。在FP語言中currying就這麼簡單：一種可以快速且簡單的實現函數封裝的捷徑。我們可以更專註於自己的設計，編譯器則會為你編寫正確的代碼！什麼時候使用currying呢？很簡單，當你想要用適配器模式（或是封裝函數）的時候，就是用currying的時候。

惰性求值

惰性求值（或是延遲求值）是一種有趣的技術，而當我們投入函數式編程的懷抱後這種技術就有了得以實現的可能。前面介紹並發執行的時候已經提到過如下代碼：


String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);

在指令式語言中以上代碼執行的順序是顯而易見的。由於每個函數都有可能改動或者依賴於其外部的狀態，因此必須順序執行。先是計算somewhatLongOperation1，然後到somewhatLongOperation2，最後執行concatenate。函數式語言就不一樣了。
在前面討論過，somewhatLongOperation1和somewhatLongOperation2是可以並發執行的，因為函數式語言保證了一點：沒有函數會影響或者依賴於全局狀態。可是萬一我們不想要這兩個函數並發執行呢？這種情況下是不是也還是要順序執行這些函數？答案是否定的。只有到了執行需要s1、s2作為參數的函數的時候，才真正需要執行這兩個函數。於是在concatenate這個函數沒有執行之前，都沒有需要去執行這兩個函數：這些函數的執行可以一直推遲到concatenate()中需要用到s1和s2的時候。假如把concatenate換成另外一個函數，這個函數中有條件判斷語句而且實際上只會需要兩個參數中的其中一個，那麼就完全沒有必要執行計算另外一個參數的函數了！Haskell語言就是一個支持惰性求值的例子。Haskell不能保證任何語句會順序執行（甚至完全不會執行到），因為Haskell的代碼只有在需要的時候才會被執行到。
除了這些優點，惰性求值也有缺點。這裡介紹了它的優點，我們將在下一章節介紹這些缺點以及如何克服它們。

代碼優化

惰性求值使得代碼具備了巨大的優化潛能。支持惰性求值的編譯器會像數學家看待代數表達式那樣看待函數式程序：抵消相同項從而避免執行無謂的代碼，安排代碼執行順序從而實現更高的執行效率甚至是減少錯誤。在此基礎上優化是不會破壞代碼正常運行的。嚴格使用形式系統的基本元素進行編程帶來的最大的好處，是可以用數學方法分析處理代碼，因為這樣的程序是完全符合數學法則的。

抽象化控制結構

惰性求值技術提供了更高階的抽象能力，這提供了實現程序設計獨特的方法。比如說下面的控制結構：


unless(stock.isEuropean()) {
sendToSEC(stock);
}

程序中只有在stock為European的時候才執行sendToSEC。如何實現例子中的unless？如果沒有惰性求值就需要求助於某種形式的宏（譯者：用if不行么？），不過在像Haskell這樣的語言中就不需要那麼麻煩了。直接實現一個unless函數就可以！


void unless(boolean condition, List code) {
if(!condition)
code;
}

請注意，如果condition值為真，那就不會計算code。在其他嚴格語言（見嚴格求值）中這種行為是做不到的，因為在進入unless這個函數之前，作為參數的code已經被計算過了。

無窮數據結構

惰性求值技術允許定義無窮數據結構，這要在嚴格語言中實現將非常複雜。例如一個儲存Fibonacci數列數字的列表。很明顯這樣一個列表是無法在有限的時間內計算出這個無窮的數列並存儲在內存中的。在像Java這樣的嚴格語言中，可以定義一個Fibonacci函數，返回這個序列中的某個數。而在Haskell或是類似的語言中，可以把這個函數進一步抽象化並定義一個Fibonacci數列的無窮列表結構。由於語言本身支持惰性求值，這個列表中只有真正會被用到的數才會被計算出來。這讓我們可以把很多問題抽象化，然後在更高的層面上解決它們（比如可以在一個列表處理函數中處理無窮多數據的列表）。

不足之處

俗話說天下沒有免費的午餐?。惰性求值當然也有其缺點。其中最大的一個就是，嗯，惰性。現實世界中很多問題還是需要嚴格求值的。比如說下面的例子：


System.out.println("Please enter your name: ");
System.in.readLine();

在惰性語言中沒人能保證第一行會中第二行之前執行！這也就意味著我們不能處理IO，不能調用系統函數做任何有用的事情（這些函數需要按照順序執行，因為它們依賴於外部狀態），也就是說不能和外界交互了！如果在代碼中引入支持順序執行的代碼原語，那麼我們就失去了用數學方式分析處理代碼的優勢（而這也意味著失去了函數式編程的所有優勢）。幸運的是我們還不算一無所有。數學家們研究了不同的方法用以保證代碼按一定的順序執行（in a functional setting?）。這一來我們就可以同時利用到函數式和指令式編程的優點了！這些方法有continuations，monads以及uniqueness typing。這篇文章僅僅介紹了continuations，以後再討論monads和uniqueness typing。有意思的是呢，coutinuations處理強制代碼以特定順序執行之外還有其他很多出處，這些我們在後面也會提及。

Continuation

continuation對於編程，就像是達芬奇密碼對於人類歷史一樣：它揭開了人類有史以來最大的謎團。好吧，也許沒有那麼誇張，不過它們的影響至少和當年發現負數有平方根不相上下。

我們對函數的理解只有一半是正確的，因為這樣的理解基於一個錯誤的假設：函數一定要把其返回值返回給調用者。按照這樣的理解，continuation就是更加廣義的函數。這裡的函數不一定要把返回值傳回給調用者，相反，它可以把返回值傳給程序中的任意代碼。continuation就是一種特別的參數，把這種參數傳到函數中，函數就能夠根據continuation將返回值傳遞到程序中的某段代碼中。說得很高深，實際上沒那麼複雜。直接來看看下面的例子好了：


int i = add(5, 10);
int j = square(i);

add這個函數將返回15然後這個值會賦給i，這也是add被調用的地方。接下來i的值又會被用於調用square。請注意支持惰性求值的編譯器是不能打亂這段代碼執行順序的，因為第二個函數的執行依賴於第一個函數成功執行並返回結果。這段代碼可以用Continuation Pass Style（CPS）技術重寫，這樣一來add的返回值就不是傳給其調用者，而是直接傳到square里去了。


int j = add(5, 10, square);

在上例中，add多了一個參數：一個函數，add必須在完成自己的計算後，調用這個函數並把結果傳給它。這時square就是add的一個continuation。上面兩段程序中j的值都是225。

這樣，我們學習到了強制惰性語言順序執行兩個表達式的第一個技巧。再來看看下面IO程序（是不是有點眼熟？）：


System.out.println("Please enter your name: ");
System.in.readLine();

這兩行代碼彼此之間沒有依賴關係，因此編譯器可以隨意的重新安排它們的執行順序。可是只要用CPS重寫它，編譯器就必須順序執行了，因為重寫後的代碼存在依賴關係了。


System.out.println("Please enter your name: ", System.in.readLine);

這段新的代碼中println需要結合其計算結果調用readLine，然後再返回readLine的返回值。這使得兩個函數得以保證按順序執行而且readLine總被執行（這是由於整個運算需要它的返回值作為最終結果）。Java的println是沒有返回值的，但是如果它可以返回一個能被readnLine接受的抽象值，問題就解決了！（譯者：別忘了，這裡作者一開始就在Java的基礎上修改搭建自己的語言）當然，如果一直把函數按照這種方法串下去，代碼很快就變得不可讀了，可是沒有人要求你一定要這樣做。可以通過在語言中添加語法糖的方式來解決這個問題，這樣程序員只要按照順序寫代碼，編譯器負責自動把它們串起來就好了。於是就可以任意安排代碼的執行順序而不用擔心會失去FP帶來的好處了（包括可以用數學方法來分析我們的程序）！如果到這裡還有人感到困惑，可以這樣理解，函數只是有唯一成員的類的實例而已。試著重寫上面兩行程序，讓println和readLine編程這種類的實例，所有問題就都搞清楚了。
到這裡本章基本可以結束了，而我們僅僅了解到continuation的一點皮毛，對它的用途也知之甚少。我們可以用CPS完成整個程序，程序里所有的函數都有一個額外的continuation作為參數接受其他函數的返回值。還可以把任何程序轉換為CPS的，需要做的只是把當中的函數看作是特殊的continuation（總是將返回值傳給調用者的continuation）就可以了，簡單到完全可以由工具自動完成（史上很多編譯器就是這樣做的）。

一旦將程序轉為CPS的風格，有些事情就變得顯而易見了：每一條指令都會有一些continuation，都會將它的計算結果傳給某一個函數並調用它，在一個普通的程序中這個函數就是該指令被調用並且返回的地方。隨便找個之前提到過的代碼，比如說add(5,10)好了。如果add屬於一個用CPS風格寫出的程序，add的continuation很明顯就是當它執行結束後要調用的那個函數。可是在一個非CPS的程序中，add的continuation又是什麼呢？當然我們還是可以把這段程序轉成CPS的，可是有必要這樣做嗎？
事實上沒有必要。注意觀察整個CPS轉換過程，如果有人嘗試要為CPS程序寫編譯器並且認真思考過就會發現：CPS的程序是不需要棧的！在這裡完全沒有函數需要做傳統意義上的「返回」操作，函數執行完後僅需要接著調用另外一個函數就可以了。於是就不需要在每次調用函數的時候把參數壓棧再將它們從中取出，只要把這些參數存放在一片內存中然後使用跳轉指令就解決問題了。也完全不需要保留原來的參數：因為這種程序里的函數都不返回，所以它們不會被用第二次！
簡單點說呢，用CPS風格寫出來的程序不需要棧，但是每次調用函數的時候都會要多加一個參數。非CPS風格的程序不需要額外的參數但又需要棧才能運行。棧裡面存的是什麼？僅僅是參數還有一個供函數運行結束後返回的程序指針而已。這個時候你是不是已經恍然大悟了？對啊，棧裡面的數據實際上就是continuation的信息！棧上的程序返回指針實質上就是CPS程序中需要調用的下一個函數！想要知道add(5, 10)的continuation是什麼？只要看它運行時棧的內容就可以了。
接下來就簡單多了。continuation和棧上指示函數返回地址的指針其實是同一樣東西，只是continuation是顯式的傳遞該地址並且因此代碼就不局限於只能返回到函數被調用的地方了。前面說過，continuation就是函數，而在我們特製的語言中函數就是類的實例，那麼可以得知棧上指向函數返回地址的指針和continuation的參數是一樣的，因為我們所謂的函數（就像類的一個實例）其實就是指針。這也意味著在程序運行的任何時候，你都可以得到當前的continuation（就是棧上的信息）。

好了，我們已經搞清楚當前的continuation是什麼了。接下來要弄明白它的存在有什麼意義。只要得到了當前的continuation並將它保存起來，就相當於保存了程序的當前狀態：在時間軸上把它凍結起來了。這有點像操作系統進入休眠狀態。continuation對象保存了足夠的信息隨時可以從指定的某個狀態繼續運行程序。在切換線程的時候操作系統也是這樣做的。唯一的區別在於它保留了所有的控制權利。當請求某個continuation對象時（在Scheme語言中是通過調用call-with-current-continuation函數實現的）得到的是一個存有當前continuation的對象，也就是棧對象（在CPS中也就是下一個要執行的函數）。可以把這個對象保存做一個變數中（或者是存在磁碟上）。當以該continuation對象「重啟」該程序時，程序的狀態就會立即「轉換」為該對象中保存的狀態。這一點和切換回一個被暫停的線程或是從系統休眠中喚醒很相像，唯一不同的是continuatoin對象可以反覆的這樣使用。當系統喚醒後，休眠前保存的信息就會銷毀，否則你也可以反覆的從該點喚醒系統，就像乘時光機回到過去一樣。有了continuation你就可以做到這一點！

那麼continuation在什麼情況下有用呢？有一些應用程序天生就沒有狀態，如果要在這樣的系統中模擬出狀態以簡化工作的時候，就可以用到continuation。最合適的應用場合之一就是網頁應用程序。微軟的http://ASP.NET為了讓程序員更輕鬆的編寫應用程序，花了大量的精力去模擬各種狀態。假如C#支持continuation的話，那麼http://ASP.NET的複雜度將減半：因為只要把某一時刻的continuation保存起來，下次用戶再次發起同樣請求的時候，重新載入這個continuation即可。對於網路應用的程序員來說就再也沒有中斷了：輕輕鬆鬆程序就從下一行開始繼續運行了！對於一些實際問題來說，continuation是一種非常有用的抽象工具。如今大量的傳統胖客戶端（見瘦客戶端）正紛紛走進網路，continuation在未來將扮演越來越重要的角色。

模式匹配

模式匹配並不是什麼新功能。而事實上它和函數式編程也沒有什麼太大的關係。它之所以常常被認為是FP的一個特性，是因為在函數式語言已經支持模式匹配很長一段時間後的今天，指令式語言是還沒有這個功能。

還是直接用例子來看看什麼是模式匹配吧，這是一個用Java寫的Fibonacci函數：


int fib(int n) {
if(n == 0) return 1;
if(n == 1) return 1;

return fib(n - 2) + fib(n - 1);
}

再看看用我們基於Java修改過的新語言寫出來的Fibonacci函數，這種新語言就支持模式匹配：


int fib(0) {
return 1;
}
int fib(1) {
return 1;
}
int fib(int n) {
return fib(n - 2) + fib(n - 1);
}

區別在哪裡呢？在於後者的編譯器替我們實現了程序的分支。
這有什麼了不起的？確實也沒什麼。只是有人注意到很多函數中有非常複雜的switch結構（對於函數式程序而言更是如此），於是想到如果能把這層結構也抽象化就更好了。然後就把這個複雜的函數拆分成若干新的函數，並在這些函數的某些參數中應用模式（這和重載有點類似）。這樣依賴當這個函數被調用的時候，編譯器會在運行時將調用者傳入的參數與各個新函數的參數定義進行比較，找出合適的那個函數來執行。合適的函數往往是參數定義上最具體最接近傳入參數的那個函數。在這個例子中，當n為1時，可以用函數int fib(int n)，不過真正調用的是int fib(1)因為這個函數更具體更接近調用者的要求。
模式匹配一般來說要比這裡舉的例子更加複雜。比如說，高級模式匹配系統可以支持下面的操作：


int f(int n &< 10) { ... } int f(int n) { ... }

那麼什麼情況下模式匹配會有用呢？在需要處理一大堆程序分支的時候！每當需要實現複雜的嵌套if語句的時候，模式匹配可以幫助你用更少的代碼更好的完成任務。我所知道的一個這樣的函數是標準的WndProc函數，該函數是所有Win32應用程序必須具備的（儘管它經常會被抽象化）。模式匹配系統一般都可以像匹配簡單數值一樣匹配數據集合。舉個例子，對於一個接受數組作為參數的函數，可以通過模式匹配數組中第一個數字為1並且第三個數字大於3的輸入。 模式匹配的另外一個好處是每當需要添加或者修改程序分支時，再也不用面對那個龐大臃腫的函數了。只要添加（或者修改）相關的函數定義即可。有了模式匹配就不再需要四人幫的很多設計模式了。程序分支越多越複雜，模式匹配就越有用。而在習慣使用這一技術之後，你可能會懷疑沒有它你一天都過不下去了。

Closure

目前為止關於函數式編程各種功能的討論都只局限在「純」函數式語言範圍內：這些語言都是lambda演算的實現並且都沒有那些和阿隆佐形式系統相衝突的特性。然而，很多函數式語言的特性哪怕是在lambda演算框架之外都是很有用的。確實，如果一個公理系統的實現可以用數學思維來看待程序，那麼這個實現還是很有用的，但這樣的實現卻不一定可以付諸實踐。很多現實中的語言都選擇吸收函數式編程的一些元素，卻又不完全受限於函數式教條的束縛。很多這樣的語言（比如Common Lisp）都不要求所有的變數必須為final，可以修改他們的值。也不要求函數只能依賴於它們的參數，而是可以讀寫函數外部的狀態。同時這些語言又包含了FP的特性，如高階函數。與在lambda演算限制下將函數作為參數傳遞不同，在指令式語言中要做到同樣的事情需要支持一個有趣的特性，人們常把它稱為lexical closure。還是來看看例子。要注意的是，這個例子中變數不是final，而且函數也可以讀寫其外部的變數：


Function makePowerFn(int power) {
int powerFn(int base) {
return pow(base, power);
}

return powerFn;
}

Function square = makePowerFn(2);
square(3); // returns 9

makePowerFn函數返回另一個函數，這個新的函數需要一個整數參數然後返回它的平方值。執行square(3)的時候具體發生了什麼事呢？變數power並不在powerFn的域內，因為makePowerFn早就運行結束返回了，所以它的棧也已經不存在了。那麼square又是怎麼正常工作的呢？這個時候需要語言通過某種方式支持繼續存儲power的值，以便square後面繼續使用。那麼如果再定義一個函數，cube，用來計算立方，又應該怎麼做呢？那麼運行中的程序就必須存儲兩份power的值，提供給makePowerFn生成的兩個函數分別使用。這種保存變數值的方法就叫做closure。closure不僅僅保存宿主函數的參數值，還可以用在下例的用法中：


Function makeIncrementer() {
int n = 0;

int increment() {
return ++n;
}
}

Function inc1 = makeIncrementer();
Function inc2 = makeIncrementer();

inc1(); // returns 1;
inc1(); // returns 2;
inc1(); // returns 3;
inc2(); // returns 1;
inc2(); // returns 2;
inc2(); // returns 3;

運行中的程序負責存儲n的值，以便incrementer稍後可以訪問它。與此同時，程序還會保存多份n的拷貝，雖然這些值應該在makeIncrementer返回後就消失，但在這個情況下卻繼續保留下來給每一個incrementer對象使用。這樣的代碼編譯之後會是什麼樣子？closure幕後的真正工作機理又是什麼？這次運氣不錯，我們有一個後台通行證，可以一窺究竟。
一點小常識往往可以幫大忙。乍一看這些本地變數已經不再受限於基本的域限制並擁有無限的生命周期了。於是可以得出一個很明顯的結論：它們已經不是存在棧上，而是堆上了8。這麼說來closure的實現和前面討論過的函數差不多，只不過closure多了一個額外的引用指向其外部的變數而已：


class some_function_t {
SymbolTable parentScope;

// ...
}

當closure需要訪問不在它本地域的變數時，就可以通過這個引用到更外一層的父域中尋找該變數。謎底揭開了！closure將函數編程與面向對象的方法結合了起來。下一次為了保存並傳遞某些狀態而創建類的時候，想想closure。它能在運行時從相應的域中獲得變數，從而可以把該變數當初「成員變數」來訪問，也因為這樣，就不再需要去創建一個成員變數了。

路在何方？

這篇文章僅僅涉及到函數式編程的一些皮毛。考慮到有時候星星之火可以燎原，所以如果它能給你一些幫助那就再好不過了。接下來我計劃就範疇論、monads、函數式編程數據結構、函數式語言中的類型系統、並行函數式編程、資料庫的函數式編程以及更多的話題寫些類似的文章。如果我可以寫出（在我學習的同時）以上清單的一半，我的人生就完整了。於此同時，Google將是我們的良師益友。

歡迎聯繫

如果您有任何問題，評價或者建議，請發郵件到coffeemug@gmail.com（譯者：如果翻譯方面的問題／建議請發到yang.huang@ymail.com:)）。期待您的回復。

註：
1當我在2005年求職時的的確確經常問別人這個問題。看著那些茫然的面孔實在是很好玩的事情。你們這些年薪30萬美金的傢伙，至少應該對自己可以利用的工具有個起碼的理解嘛。
2這是個有爭議的問題。物理學家和數學家不得不承認目前還無法確定宇宙萬物是不是都遵從可以用數學方法描述的各種法則。
3我一直一來都很討厭在歷史課上羅列一堆枯燥無味的時間、人名、事件。對我來說歷史就是關於那些改變世界的人們活生生的故事，是他們行為背後的個人動機，是那些他們用以影響芸芸眾生的方法和工具。從這個角度來說，接下來的這堂歷史課是不完整的，很遺憾。只有那些非常相關的人和事會被提及。
4在我學習函數式編程的時候，「lambda」這個術語搞得我很煩，因為我不知道它到底是什麼意思。在這裡lambda就是一個函數，在數學符號中用這個希臘字母只是因為它更容易寫。所以以後在談及函數式編程的時候只要你聽到lambda，把它在腦中翻譯為「函數」就可以了。
5有意思的是不論如何Java中的字元串總是不可修改的。討論這種背叛Java的設計背後的原因會很有意思，可惜這樣會讓我們跑題的。
6大部分函數式語言的編譯器都會盡量將迭代函數轉換為對等的循環語句。這種做法叫做尾調用優化。
7反之則不一定成立。儘管有時候可以證明兩段代碼是等價的，但不是在所有的情況下都可以得出這樣的結論。
8實際上這樣做並不比棧上存儲要慢，因為在引入垃圾回收機制後，內存分配操作的時間代價僅為O(1)。

如果面向對象式編程是用名詞抽象世界，從而達到對於事物的封裝和重用。

那函數式編程對應的就是用動詞抽象世界，從而達到對於行為的封裝和重用。

首先提一點題外話，不是很喜歡函數式編程這個詞語，我們叫它「泛函編程」吧。

因為數學有一門課叫做「Functional Analysis」（泛函分析），而我們這種編程叫做「Functional Programming」（泛函編程）。泛函編程的作用有點類似泛函分析。

初中時候學的函數是 f : 數域 → 數域 。比如 f(x) = sin a x ,我們在寫公式時候用到了 x 和 a ， a 屬於外部狀態, f : 值 imes外部狀態 → 值 ，但是外部狀態是常量，所以是不變的，所以函數還是等價於 f : 數域 → 數域

計算機剛剛上課你學到的函數是 f : 值 imes外部狀態 → 值 imes外部狀態 ，其中外部的狀態是一個關於時間的函數（因為允許的變數，所以外部狀態會隨著時間變換），所以你也可以把它等價為 f : 值 imes 時刻→ 值 imes 時刻 。由於時間這個變數是隱含變化的，這會給人帶來方便的同時，還可能帶來一些心智上的負擔，因為要時時注意外部的環境。這就是初學計算機的時候感覺「函數」和數學中函數不一樣的地方。所以 @D Flip Flop 吐槽「我認為命令式編程中的function翻譯成"函數"並不準確，應該考慮function的"功能"的意思。」很有道理啊！如果我設計編程語言的話，我會把命令式的編程語言的函數關鍵字叫做「subroutine」（如果有更好的建議，請評論區留言），反正不叫function

上大學了，我們學到的函數就變成了 f : 集合 → 集合 ，而對於初中那種比較狹義的函數，我們可以稱它為數函，另外泛函分析這門課（別轉牛角尖去學它了，編程不一定用得到）還會涉及到兩種函數，一種是 f : 函數 → 實數 ，我們稱之為泛函，另一種是 f : 函數 → 函數 ，我們稱之為運算元。泛函和運算元就對應著編程裡面的高階函數。

泛函可以視為對函數的度量，回憶一下物理裡面對泛函最簡單的應用：給一條路徑，求其需要花費的時間。路徑就是用一個函數表示，而時間就是一個實數。編程中也是一樣的啊，我給出一個函數來表示，我要做什麼樣的操作（比如我要做乘法，我就寫(a,b)=&>a*b），然後，我就對某列數據來reduce，最後得出一個新數據。我們有了一個新的思路，就是用函數來表示一種操作，函數也是一種簡單的值。如果函數是值了，我們還可以對函數進行裝飾，一個號函數變成另一個函數，那就是運算元啦。

為什麼我們之前的計算機做法都是喜歡用變數，賦值等難以理解的操作呢？因為接近底層，效率高。另外一點，我猜可能是那時候的編譯器水平不夠，不方便提供函數類型來給大家，大家就想了用循環賦值等來模擬我們的需求，然後約定成俗了，技術是有路徑依賴的。

如果不理解，就先用上。首先，試試禁用所有的解決問題的步驟強相關的功能，比如循環，可變數據……寫代碼就一路const下去，沿途使用各種高階函數，並掌握函數的特徵（輸入類型，輸出類型，轉換過程的特徵）。

我舉幾個轉換過程的特徵的例子：

map：把當前的列表的每一個item做映射，而且每個item做映射時候不知道當前的狀態

reduce：和map相比多了知道當前已經做了映射的結果（隱含著，可以用reduce寫出map），注意是左向reduce還是右向reduce

filter：把某些不合法的元素剔除（也可以通過reduce寫出filter）

還有groupBy，sort，findFirst，find，zip，等各種高階函數（名字不一定正確，但是記住特徵就可以了，記不住名字去查文檔就好了嘛），以及lens等好用的工具。平時有空看一看就好了。

把日常用的數據都弄成不可變的，好處已經好多其他同學說過了，我就不細說啦。

把某些自己用到過十多遍的高階函數的一些特徵記住，然後平時用到就依據特徵找函數，或者找不到內置的自己寫就好了。找找自己常用語言裡面的fp相關的工具集，比如JavaScript的有Ramda Documentation ， 看看人家的api是怎麼提供的。

——————————————————————————————————————

順便一提，有空去看看大名鼎鼎的lambda演算吧，可能能讓你更習慣fp的思維，其實規則很少，兩條規則就夠用了，幾個小時就能掌握了。

Alpha轉換就對應這我們日常的編程的參數名變換，比如從f(x)=sin(x)變成f(y)=sin(y)。

Beta規約就是對應著函數的求值。

（注意：我用的詞語都是對應著，lambda演算只是一堆字元串的變化，可以說，和我們所謂的函數無關）

寫幾個lambda演算裡面的程序，比如寫個Y，寫個乘除，寫個列表的map之類的，回來再看就會習慣很多

主要就是不要用括弧

這是Lambda Calculus和Combinatory Logic曠日持久的聖戰

Lambda Calculus主張能用括弧就應該加括弧

Combinatory Logic主張能不用括弧就不該加括弧

假如你有函數式思維，方差就差不多應該這麼定義

各減平均各自乘相加除以項數

太棒了，一個括弧也沒有

函數式編程就是函數也可以作為變數，參數，對象。

functions are values!

不懂函數式，只是覺得現在「函數式」這個概念的範圍越來越廣了，什麼都往裡裝，大有變成「面向對象」這種ill-defined概念的趨勢。

就我自己而言，可能「學習現代函數式編程語言中的一些技法和理念」是重要的，「學習函數式編程」這種假大空的概念是扯淡的。

比如說lambda，first-class function，curry，partial application，higher-order functions這些都還好理解。

用函數來構建控制流，延遲計算，求值順序這些也還算是函數式。applicative，functor，monoid，monad這些算在泛函的領域裡面，也還可以理解。

很多人覺得lisp是函數式編程，但我覺得lisp是面向AST編程，更接近計算機組成和元語言，應該算是「函數式編程的鼻祖」，和如今的函數式有很大差異。「數據即代碼」在我看來更像是彙編語言/計算機程序本身的特性，和函數式沒什麼關係。

多態和類型系統算不算函數式？我覺得可以算，有評論也認為first-class type不是所有函數式語言的共性，我覺得這個應該歸到PLT裡面更好。

主張immutable/stateless一定是函數式編程嗎？

sql這種基於流式計算和關係代數的範式，算是函數式編程嗎？

我在bash裡面敲了一行命令，用到了一個pipe，算是函數式編程嗎？

我用hadoop/spark搞了個分散式計算，算是函數式編程嗎？

concept/contract/trait/interface/mixin這些算是命令式/函數式編程嗎？

怎麼現在erlang，javascript，各種combinator，元編程也都也成了函數式編程呢？

大部分答案都在講函數式語言有什麼feature, 並沒有什麼卯月

最近一個conference 的名字已經概括了所謂函數式的思想: C?mp?se :: Conference

柯里化讓函數更加容易復用和組合

&> add = a b -&> a + b
這個只接受兩個參數的加法比較難復用, 例如給列表裡面每個函數+1還要新寫一個函數包裝一下
如果柯里化之後

&> add = a -&>  -&> a + b
做到同樣的效果只要部分應用下1就好了
Haskell有風騷的section語法, 那就更加爽

&> map (+1) [1..10]

to be continue

回答都有跑題，show概念之嫌，題主問的是函數式思維，這個問題我一直在思考，畢竟是方法論，能力有限，只能從切身實踐告訴你
1.表達式化
在最初的時候，需要轉變觀念，去可變數，去循環，把命令式改成表達式，注意，這只是把你丟在荒山野嶺讓你感受一下，離開熟悉的環境，地球依然在轉，但是有個重點，那就是一切都是表達式; 為什麼是表達式呢？這個問題就像為什麼魚在水裡? 因為函數式建立在lambda演算之上而非圖靈機，只不過兩者被證明等價，所以你可以在你的機器上跑全是表達式的代碼，就如有人證明天空適合魚生存，所以魚可以在天上游
當你接受了魚可以在天上游之後，就該上正餐了

1.5 數據與行為分離
這也是和面向對象不一致的地方，面向對象強調數據與行為綁定，但函數式不是，確切的說函數式 函數與數據等價，所以你才可以將函數當參數與返回值，你在設計時，切勿讓數據自己長腿能跑，其次，行為必須消除副作用，不可以偷偷把數據改了，習慣第一條後，應該不會的

2.高階邏輯
用了函數式，就不要在想循環，賦值這些低階邏輯了，而應該更高階的思考問題，這比轉化表達式更難，函數式又叫聲明式，也就是你要做什麼，只要說一下就行，而非寫個遍歷，做個狀態判斷，用函數式你不需要考慮這些，你不知道函數式的列表是怎麼遍歷的，中間向兩邊? 從後往前?這也是為何函數式適合併發的原因之一，你想知道列表中大於3的數有多少，只要，list.count(_ &> 3) 而不是寫循環，你可以直接寫你的業務，不要拘泥於細節，有點像sql, 你需要什麼告訴電腦就行，你或許會問，count foreach filter 這些函數怎麼來的? 因為有了他們你才不需要寫循環，他們把你留在高階邏輯中，這個問題的答案請看下面

3.組合子邏輯 或又叫 自底向上的設計
函數式和OO是反的，面向對象是自頂向下的設計，函數式是自底向上的設計，也就是先定義最基本的操作，然後不斷組合，不斷堆積以滿足你的所有需要，如sql定義了select, from, where...這幾個組合子，來滿足你的查詢需求，同理函數式語言會提供foreach, map等組合子(操作)來滿足你的需求，所以你必須自下而上的設計你的代碼結構，並且滿足你的需求，當你只用組合子寫代碼時，你會發現你寫的全是高階邏輯
如果這些已有組合子滿足不了你，你就得自己寫，foreach不行，你就自己寫遞歸，我告訴你，遞歸背後也是組合子，這裡一些"大神"應該不知道，在圖靈機里，遞歸就是方法不斷調用自己沒什麼好說的，但是在lambda演算中，匿名函數是沒法調用自己的，所以遞歸是用Y組合子(又叫不動點組合子)把遞歸函數自己求解出來再調用的，這才可以實現遞歸，並與圖靈機的循環等價，有點跑題了，總之要想順手的寫函數式，最好用面向組合子的設計，注意，不是必須，組合子演算和lambda演算可以相互轉化，也就是，你完全可以寫一堆雜亂的表達式，但沒有組合子邏輯來得清爽，Haskell大規模使用monad這個特殊組合子，始其變得統一整潔

好了，總結一下
函數式思維，其實就是組合子邏輯，用簡單的幾個函數組合來構建複雜邏輯，始終以高階的角度去表達問題，而非依賴副作用。
知道這點，你用java也可以寫函數式代碼了

但是，這也只是本人積累得來的感悟，絕不敢大肆伸張這就是函數式，我也在不斷研究中，如有問題，還望大神指正

推薦閱讀：

※王小波的計算機水平到底有多好？
※epoll 或者 kqueue 的原理是什麼？
※作為一個進大學才學編程的學生，如何能以後達到溫趙輪三位大神的水平？
※從零基礎開始想發一篇深度學習的論文要提前準備什麼？寫論文的周期大概多久？
※零基礎學習 Hadoop 該如何下手？

TAG:編程 | 面向對象編程 | 函數式編程 |