Python中的函数式编程

用函数式编程语言（比如说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
<function sqr at 0x402ba10c>
>>>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
<function <lambda;> 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
>>>

神奇吧！好好地想一想！