用函數式編程語言（比如說Scheme）寫的程序可以反映出數學表達式的結構；數學表達式是由若幹函數字符串組成的，其中的每一個都能計算出一個結 果並且不產生任何副作用。同樣的函數用同樣的參數去調用就會產生同樣的結果，這和調用時的上下文是無關的。用這樣的方法可以將我們的代碼優雅地結構化（並 且一定程度上也起到了簡化的效果）。Python編程語言擁有所有讓它在函數式編程（FP）上有優勢的特性。在這篇文章中，我們將從“Pythonic” 的角度來看一下FP中的一些有趣的思想如高階函數、閉包、lambda以及柯裏化等等。

什麽是函數式編程？

作為程序的一部分，我們所寫的函數只是在表面上和數學函數類似。比方說我們寫這麽一個函數：

int current_balance = 100;

int withdraw(int w)

{

  current_balance = current_balance - w;

  return current_balance;

}

我們調用一次“withdraw(10)”之後90這個值將會被返回。再調用一次“withdraw(10)”則返回80。如果 “withdraw”是一個“純”數學函數的話，那麽兩次調用應該返回同樣的值，因為我們傳給它的參數值是一樣的。而我們的程序則“記住”了前次的調用 （它有“狀態”）然後每次都返回一個新的值 。一個如下的數學方程：

y = f(a) + g(b) + f(a)

有一個很好的屬性就是它可以被化簡為：

y = 2*f(a) + g(b)

事實上如果有一個計算機程序是由一組會修改全面變量的函數構成的話，我們是無法對它進行這樣化簡的。相比於生成一個數學證明，驗證一個計算機程序的正確性更像是一個探索各種假設分析的情境的過程。

“賦值”操作符也帶來了些問題。讓我們簡單地看一個計算階乘的循環：

# Compute factorial of 'n'

int f = 1, n = 5;

while (n > 0) {

  f = f * n;

  n = n - 1;

}

return f;

我們會犯的一個常見的錯誤就是在循環體內交換兩個語句的順序。因為賦值操作符改變了它左邊的符號的值，所以這讓我們在考慮在我們的程序中每一個動作的順序時需要格外的小心。

函數式編程的範式鼓勵我們把程序結構化成一系列“純”的函數，這些函數沒有全局的狀態也不使用賦值操作符（註意這並不是所有情況下都可行的，很顯然 一個銀行的系統就需要“記住”很多東西）。函數式編程人員使用遞歸的函數調用（循環可以當成一種特殊的遞歸，於是特定的循環結構“while”和 “for”也就不需要了）來產生重復性的行為。函數則成為了我們的“一等公民”，比方說，它們可以被當成參數傳給另一個函數，也可以被別的函數返回，這就 促成了我們稱之為“高階函數”的產生。當和“閉包”這個思想結合在一起的時候，這就成為了一個很強大的思想，它可以很簡單地捕獲很多復雜的可計算模式。

遞歸表示

Python中定義一個遞歸函數沒什麽了不起的。這裏是一個用Python寫的經典階乘函數：

def fact(n):

  if (n == 0): return 1

  return n * fact(n - 1)

作為一等公民對象的函數

讓我們在Python的命令行中定義兩個函數，然後來做些實驗：

>>>

>>>def sqr(x): return x*x

...

>>>def cube(x): return x*x*x

...

>>>sqr

>>>a = [sqr, cube]

>>>a[0](2)

>>>def compose(f, g): return f(g(x))

...

>>>compose(sqr, cube, 2)

64

>>>

我們先將兩個函數存到數組中，然後用“a[0][2]”的方式來調用“sqr”。接著我們又定義一個叫“compose”的函數，然後將“sqr” 和“cube”這兩個函數作為參數傳給它們並進行調用。註意這邊並沒有任何特殊的記號，我們操作函數時就好像它們是像數組和數字之類的對象一樣。

高階函數的威力

Structure and Interpretation of Computer Programs，這本由Abelson和Sussman寫的傳奇般的“指南書”中詳細地描述了高階函數的作用。一個“函數”（或子程序、輔程序、過程）被認為是一種捕獲模式的機制。如果我們有如下形式的語句

a*a*a

b*b*b

c*c*c

.....

我們可以想到要定義一個叫“cube”（立方）的函數來捕獲這種模式的本質並給它一個名字。將函數當成參數傳給別的函數的這種能力拓寬了這種“模式捕獲”機制的領域。讓我們來看一個簡單的函數，叫“sum”：

def sum(a, b):

  if (a > b): return 0

  else: return a + sum(a+1, b)

這個函數將從“a”到“b”的所有數字進行累加。我們嘗試著拓寬這個函數的領域，讓它具有操作任意序列的能力，比如說：

1/(1*3) + 1/(5*7) + 1/(9*11) + ...

我們發現到上面的序列和下面這個：

1 + 2 + 3 + 4 + ...

有著相似之處，即它們都是“求和”。我們想象一個變量“a”從1變到2，2變到3，然後一直這麽做下去。這種從1到2的變化可以用一個函數來捕獲 （就是一個簡單的“加1”函數）。在第一個序列中，這個變量是從1到5，5到9，9到11這麽變化的。所以在這裏的這種變化我們可以用一個“加4”的函數 來捕獲。另一個小問題是，這個數列中的通項並不是數字1、5、9、11等等而是1/(1*3)、1/(5*7)……但是接著這種轉換也可以通過一個函數表 示！我們觀察的結果可以用一個函數“sigma”表示出來：

def sigma(term, a, next, b):

  if(a > b): return 0

  return term(a) + sigma(term, next(a), next, b)

然後看看我們怎麽通過“sigma”來計算這個序列的和：

1/(1*3) + 1/(5*7) + 1/(9*11) + ...

我們來定義兩個函數：

def term(x): return 1.0/(x * (x+2))

def next(x): return x + 4

然後調用：

sigma(term, 1, next, 1000)

這樣就成功了！現在我們就能只要定義兩個輔助函數就可以累積任意數列的和了。

故事還沒有結束。我們可以想想怎麽將“sigma”進行泛化。我們註意到“sigma”只是使用了一個組合函數“add”來將一個序列中的各項“組 合”起來。為什麽不用一個泛化的過程來根據一個用戶定義好並作為參數傳過來的函數來組合函數中的各項呢？讀者可以把這個當成一個練習來試試！

使用“lambda”

我們再來試試下面些命令：

>>>

>>>lambda x: x+4

 at 0x402ba25c>

>>>f = lambda x: x+4

>>>f(3)

7

>>>

lambda關鍵字創建了一個匿名函數。lambda的主體只能由一些簡單的表達式組成。在上一個例子中，我們用lambda來創建一個函數，這個 函數接受一個參數，並將它加4後返回。當我們需要定義一個函數而只將這個函數用於傳遞給另一個函數的時候，我們應當想到使用“lambda”。比如說：

>>>

>>>map(lambda x:x*x, [1,3,7,9])

[1, 9, 49, 81]

>>>filter(lambda x: x%2 == 0, range(10))

[0, 2, 4, 6, 8]

>>>

map函數接受一個函數和一個列表作為參數，然後將函數運用在原列表的每一個元素上，並將得到的新列表返回。filter也是類似的，它返回的列表只由原列表中那些能使函數返回true的元素組成。

閉包

Python允許嵌套的函數定義。

def add(x):

  return lambda(y): x+y

調用add(3)將返回一個帶單參數的函數。現在這個返回的函數有一個特性——它能記住它被創建時的環境。函數體中的“x”是我們在調用“add”時提供給它的。我們把這樣的函數叫作“閉包”。調用add(3)(4)將使這個函數以x = 3和y = 4的值執行。

也許你已經註意到了一些有趣的地方。我們並沒有定義一個接受兩個參數的“add”函數，而是可以將一個單參數的函數嵌在另一個單參數的函數中，並產生相同的效果。我們也可以將這升到任意層次：

def add3(x):

  return lambda y: lambda z: x+y+z

現在我們就可以調用“add3(1)(2)(3)”了！這個思想在FP社區中被稱為“柯裏化”。

讓我們試著寫一個做“數值”微分的函數。

def differentiate(f):

  return lambda x: (f(x+0.001) - f(x))/0.001

這個函數可以這麽試出來：

>>>

>>>p = differentiate(cube)

>>>p(2)

12

>>>

用“cube”作為參數來調用differentiate會返回一個單參數函數，這個函數會記得“f”的值等於“cube”。現在，用2作為參數來調用這個函數就會產生如下的計算：

(cube(2+0.001) - cube(2))/0.001

關於lambda的一點好玩的地方

函數式編程中“用函數來計算”的思想可以走向極端；我們甚至可以說萬事萬物（是的，我的意思是甚至是整數，真值，假值這樣的東西，也就是字面上的萬事萬物）都可以表示成函數。一個十分聰明的家夥Alonzo Church指出如何做到這一點並產生一個了不起的成果，稱之為“Lambda演算”。我們並不會深入到Church的成果的細節中，但是會來簡單地看一些好玩的函數。

讓我們看下我們對於“true”和“false”的定義：

true = lambda x, y: x

false = lambda x, y: y

iff = lambda p, x, y: p(x, y)

我們定義的true為一個函數，它返回兩個參數中的前一個；而false則返回後一個參數。當我們看看我們怎麽使用這樣的“true”和 “false”的時候就會明白這種定義的邏輯了。調用iff(true, 2, 3)將返回2，而調用iff(false, 2, 3)則返回3。

我們之前說的是所有可計算的建構都可以通過lambda定義出來。那麽讓我們來試著建立一個基本的數據結構，一個“pair”。

pair = lambda x, y: lambda f: f(x, y)

這種定義有點小技巧：“pair”是一個接受兩個參數的函數，並返回另一個函數；與此同時，這個返回的函數接受一個參數，並將這個參數運用在x和y上。當我們定義另兩個函數的時候這種思想就變得很明了了。

first = lambda p: p(true)

second = lambda p: p(false)

現在，讓我們變得哲學一點並問一個問題：“什麽是pair？”答案是：“如果存在兩個函數‘first’和‘second’使得first(P)為x且second(P)為y，則我們說P是這兩個x和y的一個pair。”讓我們這麽試一下：

>>>

>>>P=pair(2,3)

>>>first(P)

2

>>>second(P)

3

>>>

神奇吧！好好地想一想！