python中的函数式编程

本文译自Functional Programming HOWTO

在这篇文章中,我们将带你浏览python语言中适合使用函数式编程风险的特性。在介绍完函数式编程的相关概念之后,我们将介绍诸如迭代器和生成器之类的语言特性以及相关的模块与库,如itertools和functools。

导论

本节介绍函数式编程的基本概念; 如果您只是想学习Python的语言特性,可以跳过这一节。

不同的编程语言以不同的方式来对问题进行分解:

  • 大多数编程语言是过程式的:程序是指示计算机对程序输入做什么的指令列表。 C,Pascal,甚至Unix shell都是过程式的程序语言。
  • 在声明式的编程语言中,您通过特定的方式明确需要解决的问题,然后编程语言自己决定如何更有效的进行计算。 SQL可能是您最熟悉的声明式语言,一个SQL查询语句描述要检索的数据集,SQL引擎决定是扫描表还是使用索引,首先执行哪些子语句等。
  • 面向对象式的程序语言操作对象的集合。对象具有内部状态,并且支持相应的方法来查询或修改这些内部状态。 Smalltalk和Java就是面向对象的语言。 C++和Python是支持面向对象编程的语言,但并不强制要求使用面向对象特性。
  • 函数式编程将需要解决的问题分解成一组函数。理想情况下,函数只需要处理输入并产生输出,并且没有影响给定输入产生的输出的任何内部状态。大家熟知的函数式语言包括ML语言家族,如标准ML,OCaml和其他变体以及Haskell。

一些计算机语言的设计者特别强调特定的编程范式,这通常使得以不同范式编写程序变得困难。另外一些语言则是支持多种不同编程方法的多范式语言,如Lisp,C ++和Python就是多范式的。 您可以以过程式的、面向对象的以及函数式的风格,在所有这些语言中编写程序或第三方库。在一个大型程序中,不同的部分可能使用不同的范式写成,例如,GUI编程可能是面向对象的,而业务逻辑则是函数式或过程式的。

在函数式程序语言中,输入流经一系列的函数。每个函数都对其输入进行操作,并产生一些输出。函数式编程风格不鼓励修改内部状态,或进行在函数返回值中不可见的更改等具有副作用的函数。完全没有副作用的函数称为纯函数。避免副作用意味着不能使用数据随程序运行而更新的数据结构,每个函数的输出只能取决于其输入。

有些语言对纯粹性的要求非常严格,甚至没有赋值语句如a = 3或c = a + b。但是要完全避免所有副作用是很困难的。例如,打印到屏幕或向磁盘文件写入数据都是副作用。例如在Python中,print语句或time.sleep(1) 语句都没有返回任何有用的值,调用它们只是因为他们具有把文本输出到屏幕上或者暂停执行一秒的副作用。

以函数式风格编写的python程序通常不会走完全避免所有I/O操作与赋值的极端,相反,它们通常会提供一个看上去像函数式风格的接口,但是内部实现上仍是非函数式的。例如,函数内的局部变量仍然可以使用赋值,但是程序不修改全局变量,也没有其它的副作用。

函数式编程可以看作是面向对象编程的反面。对象是一种包含内部状态的小容器,它还包括一些可以修改这些状态的方法,而整个程序则是正确的状态修改方法的集合。函数式编程想要尽可能的避免状态变化,只和函数间的数据流动打交道。在python中,你可以通过编写可以返回特定对象的实例的方式来将两种编程范式结合起来。

函数式风格看上去是一种奇怪的限制,为什么你应该避免对象和副作用?实际上,函数式风格有一些理论与实践上的优势:

  • 形式可证明
  • 模块化
  • 可组合性
  • 易于调试与测试

形式可证明

函数式编程在理论上的一个好处是,可以更加容易的构建出表明程序正确性的数学证明。

很长时间以来,学者们一直想找到寻找一种可以数学化的证明程序的正确性的方法。这不同于使用许多输入测试程序,并得出结论,其输出通常是正确的,或者读程序的源代码,并得出结论代码看起来是正确的。相反,数学化证明的目标是严格证明程序可以为所有可能的输入产生正确的结果。

用于证明程序正确的技术是写入不变量,输入数据的属性和始终为真的程序变量。对于每一行代码,您将显示如果在执行该行之前不变量X和Y为真,则在执行该行后,稍微不同的不变量X’和Y’为真。这样一来,直到你到达程序的结尾,在这一点上,不变量应该符合程序输出上的所需条件。

函数式编程之所以要避免赋值,主要是因为赋值很难用上面提到的方法来处理,赋值会破坏赋值前正确的不变量,同时无法产生任何新的可以继续推进的不变量。

不幸的是,证明程序的正确性很大程度上是不要实际的并且与python程序不相关。即使是微小的程序也需要几页长的证明,而中等复杂程序的正确性的证明将是极为复杂的。此外,你每天使用的程序(如Python语言的解释器,XML解析器或者Web浏览器)很少或没有能够被证明为正确的。即使你写下或给出了证明,也存在一个验证证明的问题,也许证明中有一个错误,但是你错误地相信你已经证明了程序是正确的。

模块化

函数式编程更加实际的益处在于它强迫你把要解决的问题分成更小的问题,因此,程序可以更加的模块化。编写一个只做一件事的小函数要比写一个能够实现复杂转换的大函数要更加容易,而且小函数也更容易阅读和检查错误。

易于调试与测试

对函数式程序的调试与测试更加容易。调试更加容易是因为函数通常很小而且清晰的实现了。当程序无法工作时,每个函数都是一个接口,你可以检查它的数据是否正确。你可以查看中间输入也输出,以快速隔离对错误负责的函数。测试更加容易是因为每个函数都是一个潜在的可以单元测试的对象。函数不依赖于系统的状态,这些状态是在进行测试之前必须先行复现的。相反,你只需要给出正确的输入,然后检查输出是否符合预期。

可组合性

当你在编写函数式的程序时,你会编写一些具有不同输入与输出的函数。这些函数中的一些不可避免地只针对特定应用,但是其它一些函数则可以应用在其它各式各样的程序之中。例如,一个以目录路径为输入并返回目录中的所有XML文件的函数,或一个接受文件名为输入并返回其内容的函数都可以应用于许多不同的情况。

随着时间的推移,你将形成一个你自己的函数库。你经常可以通过对已有函数进行新的设定,并编写一些处理特定任务的新函数,并将这些函数组合起来以形成新的程序。

迭代器

我们首先看一个python语言的特性:迭代器,这是编写函数式风格的程序的重要基础。

一个迭代器是一个表示数据流的对象,这个对象每次返回一个元素。python的迭代器必须支持一个名为next()的方法,这个方法不引用任何参数,并且总是返回流的下一个元素。如果数据流中没有更多的元素,next()方法必须抛出StopIteration异常。迭代器不一定必须是有限的,编写产生无限数据流的迭代器也是完全合理的。

python内置的iter()函数可以接受任意对象,并尝试返回一个迭代器,这个迭代器返回对象的内容或元素,如果对象不支持迭代,则招聘TypeError异常。Python的几个内置数据类型支持迭代,最常见的是列表和字典。如果一个对象可以获得迭代器,则这个对象称为可迭代的。

你可以手动地实验一下迭代器:

>>> L = [1,2,3]
>>> it = iter(L)
>>> print it
<...iterator object at ...>
>>> it.next()
1
>>> it.next()
2
>>> it.next()
3
>>> it.next()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
>>>

python在几个不同的上下文中都需要可迭代对象,最重要的就是在for语句中。在语句for X in Y中,Y必须是一个迭代器或者是一个拥有iter()方法的对象,这个方法可以为其创造一个迭代器。以下两个语句是等价的:

for i in iter(obj):
print i
for i in obj:
print i

迭代器可以通过使用list()tuple()构造函数来实现列表或元组:

>>> L = [1,2,3]
>>> iterator = iter(L)
>>> t = tuple(iterator)
>>> t
(1, 2, 3)

序列解包也支持迭代器:如果你知道迭代器将返回N个元素,则可以将它们解包为N元组:

>>> L = [1,2,3]
>>> iterator = iter(L)
>>> a,b,c = iterator
>>> a,b,c
(1, 2, 3)

内置函数如max()min()可以接受一个迭代器输入参数并且返回迭代器中的最大值与最小值。innot in运算符也支持迭代器,X在迭代器中当且仅当X在迭代器数据流的返回值当中。但是如果迭代器是无限的,那么以上方法都会遇到问题,max()min()函数将永远不会返回值,而如果元素X不在迭代器生成的数据流之中,则innot运算符也不会返回任何值。

请注意,你只能在迭代器中前进,没有办法获取上一个元素,重置迭代器,或者复制它。迭代器对象可以选择提供这些附加功能,但迭代器协议仅指定了next()方法。 因此,函数可能会销毁所有迭代器的输出,如果你需要使用相同的数据流执行不同的操作,则必须创建一个新的迭代器。

支持迭代器的数据类型

我们已经看到了列表和元组如何支持迭代器。事实上,任何Python语言中的序列类型(如字符串)都可以自动支持创建迭代器。

在字典上调用iter()会返回一个迭代器,这个迭代器会遍历字典中的所有键:

>>> m = {'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4, 'May': 5, 'Jun': 6,
... 'Jul': 7, 'Aug': 8, 'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12}
>>> for key in m:
... print key, m[key]
Mar 3
Feb 2
Aug 8
Sep 9
Apr 4
Jun 6
Jul 7
Jan 1
May 5
Nov 11
Dec 12
Oct 10

可以发现,打印的顺序是随机的,因为它基于字典中对象的散列值的顺序。

在字典中使用iter()方法总是会遍历所有键,但是字典也有其它方法可以返回其它迭代器。如果你想遍历键、值或键值对,你可以分别使用iterkeys()itervalues()iteritems()方法来得到适当的迭代器。

dict()构造函数可以接受一个返回有限的键值对元组数据流的迭代器:

>>> L = [('Italy', 'Rome'), ('France', 'Paris'), ('US', 'Washington DC')]
>>> dict(iter(L))
{'Italy': 'Rome', 'US': 'Washington DC', 'France': 'Paris'}

通过调用readline()方法也可以使得文件支持迭代,直到文件中不再有剩余的行,这意味着你可以像这样读取文件中的每一行:

for line in file:
# do something for each line
...

集合可以从一个可迭代对象中获取它们的内容,并让你遍历集合的元素:

S = set((2, 3, 5, 7, 11, 13))
for i in S:
print i

生成器表达式与列表推导式

对迭代器输出的两个常见操作是:1)对每个元素执行一些操作;2)选择满足某些条件的元素的子集。 例如,给定一个字符串列表,您可能需要从每行删除尾随空格,或者提取包含给定子字符串的所有字符串。

列表推导和生成器表达式(简写形式:listcompsgenexps)是从函数式编程语言Haskell借用的表示这种操作的简明符号。你可以使用以下代码从字符串流中去掉所有空格:

line_list = [' line 1\n', 'line 2 \n', ...]
# Generator expression -- returns iterator
stripped_iter = (line.strip() for line in line_list)
# List comprehension -- returns list
stripped_list = [line.strip() for line in line_list]

你可以通过添加if条件来选择某些元素:

stripped_list = [line.strip() for line in line_list if line != ""]

使用列表推导式,你会得到一个python列表,stripped_list是一个包含结果行的列表,而不是一个迭代器。生成器表达式返回一个迭代器,根据需要计算值,而不需要一次实现所有的值。这意味着如果你需要一个返回无限流或非常多数据的迭代器,列表推导式将是无效的,在这种情况下,生成器表达式更为可取。

生成器表达式由小括号括起来,而列表推导式由方括号括起来,生成器表达式有如下形式:

( expression for expr in sequence1
if condition1
for expr2 in sequence2
if condition2
for expr3 in sequence3 ...
if condition3
for exprN in sequenceN
if conditionN )

列表推导式的代码与上面类似,唯一的区别只是使用的括号不同(使用方括号而不是小括号)。生成器表达式的输出是前后相继的表达式的值。if语句是可选的,如果有,则只有当条件为真时,表达式才会被计算并添加到结果中。生成器表达式必须写在括号内,但是表示函数调用的括号也是一样的。如果要创建一个将立即传递给函数的迭代器,你可以这么写:

obj_total = sum(obj.count for obj in list_all_objects())

for ... in子句包含要迭代的序列。序列的长度不一定相同,因为迭代的顺序是从左到右的,而不是并行的。对于序列1中的每个元素,序列2从头开始循环。序列3则遍历由序列1与序列2的结果组成的每一对元素。换句话说,列表解析或生成器表达式相当于以下Python代码:

for expr1 in sequence1:
if not (condition1):
continue # Skip this element
for expr2 in sequence2:
if not (condition2):
continue # Skip this element
...
for exprN in sequenceN:
if not (conditionN):
continue # Skip this element
# Output the value of
# the expression.

这意味着当有多个for ... in语句而没有if语句时,结果的长度等于所有序列的长度的乘积。如果你有两个长度为3的列表,则输出列表的长度为9个元素:

>>> seq1 = 'abc'
>>> seq2 = (1,2,3)
>>> [(x,y) for x in seq1 for y in seq2]
[('a', 1), ('a', 2), ('a', 3),
('b', 1), ('b', 2), ('b', 3),
('c', 1), ('c', 2), ('c', 3)]

为了避免在Python的语法中引起歧义,如果表达式要创建一个元组,则必须用括号括起来。下面的第一个列表推导式的语法是错误的,第二个是正确的:

# Syntax error
[ x,y for x in seq1 for y in seq2]
# Correct
[ (x,y) for x in seq1 for y in seq2]

生成器

生成器一种特殊的函数,可以简化编写迭代器的工作。普通的函数计算一个值并且返回它,但是生成器返回一个迭代器,这个迭代器则返回一个值构成的数据流。

你无疑非常熟悉普通函数在Python或C语言中调用方式。当你调用一个函数,它将获取一个私有的命名空间,在这个命名空间里它可以创那些局部变量。当函数执行到return语句时,私有变量被销毁,它的值则返回给函数的调用者。之后对同一个函数的调用将创造新的命名空间和一系列新的局部变量。但是,如果局部变量在退出函数时没有丢弃呢?如果你之后可以从退出函数的地方恢复这个函数呢?生成器提供了这些特性,你可以把它们看作可恢复的函数。下面是一个生成函数的最简单的例子:

def generate_ints(N):
for i in range(N):
yield i

任何包含yield关键字的函数都是生成函数,这可以由Python语言的编译器检测到,从而使用特殊的方式来编译这个函数。

当你调用生成函数时,它不返回单个值,而是返回一个支持迭代器协议的生成器对象。在执行yield表达式时,生成器输出i的值,这一点与return语句类似。yieldreturn语句之间的最大区别在于,在执行到yield语句时,生成器的执行状态将被暂停,并保留局部变量。在下一次调用生成器的next()方法时,该函数将继续执行。

下面是一个generate_ints()生成器的示例用法:

>>> gen = generate_ints(3)
>>> gen
<generator object generate_ints at ...>
>>> gen.next()
0
>>> gen.next()
1
>>> gen.next()
2
>>> gen.next()
Traceback (most recent call last):
File "stdin", line 1, in <module>
File "stdin", line 2, in generate_ints
StopIteration

你也可以写成for i in generate_ints(5)或者a,b,c = generate_ints(3)

在一个生成器函数中,返回语句只能在没有值的情况下使用,并且表示数值处理流程的结束,返回语句执行后,生成器不能再返回任何其他值。在生成器内返回一个数值(如return 5)的做法是错误的。生成器的最终结果也可以通过手动抛出StopIteration来实现,或者可以通过不断执行迭代器而得到。

你可以通过编写自己的类并将生成器的所有本地变量存储为实例变量来手动实现生成器的效果。例如,返回整数列表可以通过将self.count设置为0并使next()方法增加self.count并返回来完成。然而,对于一个稍微复杂点的生成器,编写相应的类可能会更加麻烦。

Python库中自带的测试套件,test_generators.py包含一些更加有趣的例子。下面一个使用生成器递归地实现树的顺序遍历的生成器。

# A recursive generator that generates Tree leaves in in-order.
def inorder(t):
if t:
for x in inorder(t.left):
yield x
yield t.label
for x in inorder(t.right):
yield x

test_generators.py中的另外两个例子为N皇后问题(将N个女王放在NxN棋盘上,以便没有女王威胁到另一个)和骑士旅行问题(找到一个骑士到NxN棋盘的每个方格的路线但不会访问任何方格两次)给出了解决方案。