Python作为一门多范式编程语言，也提供了对函数式编程（Functional Programming）的支持，虽然并不是那么纯粹，也不支持尾递归优化。文档讲述了Python在函数式编程方面的支持与语言特性，例如iterators, generators以及相关的库itertools和functools。

Introduction

什么是函数式编程，Functional Programming？

编程语言可以分为以下几种：

  • 面向过程：程序直接告诉计算机如何处理程序输入的指令列表，C、Pascal甚至Unix shell都是面向过程的编程语言。
  • 在声明性语言（declarative languages）中，编写了一个描述要解决的问题的规范，并且编程语言的实现，指出了如何高效地执行计算。SQL应该是最有名的声明性语言。
  • 面向对象：程序处理对象的集合。对象具有自己的内部状态，并且具有支持查询或修改此内部状态方法。Smalltalk和Java是面向对象的编程语言，C++和Python也是支持面向对象编程的语言，但不强制使用面向对象编程范式。
  • 函数式编程将问题分解为一组函数。理想情况下，函数只接收输入并产生输出，并且函数的内部状态不会影响给定输入产生的输出。这也是函数式编程的一大优势，即Immutable Data（数据不可变）。简而言之，不依赖于外部的数据，而且也不改变外部数据的值，这种思想可以大大减少代码中的Bug，并且函数式编程也支持像使用变量一样使用函数。函数式语言包括 ML family (Standard ML, OCaml, and other variants)和Haskell。

函数式编程是一种抽象程度很高的编程范式，纯粹的函数式编程语言编写的函数没有变量。因此，任意一个函数，只要输入是确定的，输出就是确定的，即每个函数的输出只能依赖于它的输入。这种纯函数（purely functional）我们称之为没有副作用 (side effect)。而允许使用变量的程序设计语言，由于函数内部的变量状态不确定，同样的输入，可能得到不同的输出，因此，这种函数是有副作用的。

函数式编程可以被认为是面向对象编程的反面。对象是包含内部状态以及允许修改此状态的方法的集合，而函数式编程希望处理数据流时，尽可能避免状态变化。

一些编程语言对纯度（purity）非常严格，甚至没有赋值语句，如a = 3或c = a + b，但副作用很难避免。例如，打印到屏幕或写入磁盘文件是有副作用的。在Python中，对print()或time.sleep()函数的调用都不会返回有用的值，它们只会发送一些文字到屏幕或暂停执行一秒钟的副作用。

那么为什么要采用函数式编程的范式？为什么要避免对象和副作用？

函数式编程有着理论和实践上的优势：

  • Formal provability 简而言之，相对易于在数学上证明函数是正确的
  • Modularity 这种范式迫使必须将问题分解，程序因此更模块化。
  • Composability
  • Ease of debugging and testing

我们可以不用极端的使用函数式编程，而是使函数的接口使用近似于函数式的风格，在内部使用非函数式范式。例如，函数的实现仍然赋值给局部变量，但不会修改全局变量或有其他副作用。

函数式编程的令一个特点是允许把函数本身作为参数传入另一个函数，甚至允许返回一个函数。

这样我们可以总结下面对对象编程和函数式编程：

面对对象的：

  • 数据和对数据的操作紧紧耦合
  • 对象隐藏它们操作的实现细节，其他对象调用这些操作只需要通过接口。
  • 核心抽象模型是数据自己
  • 核心活动是组合新对象和拓展已经存在的对象，这是通过加入新的方法实现的。

函数式编程：

  • 数据与函数是松耦合的
  • 函数隐藏了它们的实现，语言的抽象是函数，以及将函数组合起来表达。
  • 核心抽象模型是函数，不是数据结构
  • 核心活动是编写新的函数。
  • 变量缺省是不变的，减少可变性变量的使用，并发性好

Iterators 迭代器

我们从Python语言特征中支持函数式编程的重要基础 Iterable 和 Iterator 迭代器开始。

可以直接作用于for循环的对象统称为可迭代对象：Iterable，Python的一些内置数据类型支持迭代，最常见的是list和dictionary。我们可以使用Python标准库collections和isinstance来判断一个对象是否是Iterable的。

1
2
3
4
5
6
7
8
9
>>> from collections import Iterable
>>> isinstance([x for x in range(10]), Iterable)
True
>>> isinstance({}, Iterable)
True
>>> isinstance('abc', Iterable)
True
>>> isinstance(123, Iterable)
False

而迭代器是一个表示数据流的对象，这个对象一次返回一个元素的数据。Python迭代器不但可以作用于for循环 ，且可以被next()函数调用并不断返回下一个值，即必须支持名为__next__()的方法，该方法不接受任何参数，并且始终返回数据流的下一个元素。如果数据流中没有更多元素，__next__()必须抛出StopIteration异常。

因此，迭代器不一定是有限的，编写一个能够产生无限数据流的迭代器是完全有可能的。

内置(built-in)iter()函数接受任意对象，并尝试返回一个将返回对象内容或元素的迭代器，如果该对象不支持迭代，则引发TypeError。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> L = [1,2,3]
>>> it = iter(L)
>>> it  
<...iterator object at ...>
>>> it.__next__()  # same as next(it)
1
>>> next(it)
2
>>> next(it)
3
>>> next(it)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

同时可以通过list()，tuple()等函数将迭代器转为list、tuple等对象。

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

序列解包（sequence unpacking ）也支持迭代器，知道迭代器将返回N个元素，则可以将它们解包为N元组：

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

也可以使用isinstance()判断一个对象是否是迭代器对象：

1
2
3
4
5
6
7
8
9
>>> from collections import Iterator
>>> isinstance((x for x in range(10)), Iterator)
True
>>> isinstance([], Iterator)
False
>>> isinstance({}, Iterator)
False
>>> isinstance('abc', Iterator)
False

诸如max()和min()之类的内置函数可以接受一个迭代器参数，并返回最大或最小的元素。"in"和"not in"运算符也支持迭代器：如果可以在迭代器返回的流中找到X，则X in iterator为true。

如果迭代器是无限的，则max()，min()自然无返回值，如果元素X从不出现在流中，那么"in"和"not in"运算符也无返回。

**注意，在迭代器中只能前进。**没有办法获得前一个元素，也不能重置迭代器或生成迭代器的原始副本。

迭代器对象可以选择提供些额外的功能，但迭代器协议仅指定__next __()方法。因此函数可能会消耗迭代器的所有输出，并且如果您需要对同一个流执行不同的操作，则必须创建一个新的迭代器。

支持迭代器的数据结构

list、dict、tuple支持迭代器。 实际上，任何一个Python序列类型（如字符串）都支持创建迭代器。在dict上调用iter()会返回一个遍历dict中key的迭代器：

实际上这里for key in iter(m)和for key in m是等价的，因为dict也是Iterable。顺序基本上是随机的，因为基于dict中对象的哈希排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
>>> 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 iter(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

文件还通过调用readline()方法来迭代，直到文件中没有行。

迭代器对象都是Iterable，但list、dict、str、tuple、set虽然是Iterable，却不是迭代器。

可以从这个角度理解：迭代器不一定是有限的，Iterator的计算是惰性的，只有在需要返回下一个数据时它才会计算，因此编写一个能够产生无限数据流的迭代器是完全有可能的，而无限长的list，dict，str，tuple、set是不存在的。

生成器和list

对于一个迭代器输出，会有一些常见操作：

  • 对每个元素执行一些操作
  • 选择满足某些条件的元素子集

这些操作可以称为列表生成式和生成器表达式（List comprehensions and generator expressions），简写为：“listcomps"和"genexps”。生成器表达式由圆括号()包裹，列表生成式由方括号[]包裹。

例如，给定一个字符串列表，删除每行尾部的空白或提取包含给定子字符串的所有字符串。

1
2
3
4
5
6
7
8
9
10
11
>>> line_list = ['  line 1\n', 'line 2  \n']

# Generator expression -- returns iterator
>>> stripped_iter = (line.strip() for line in line_list)
>>> stripped_iter
<generator object <genexpr> at 0x000001B1E9FF1F68>

# List comprehension -- returns list
>>> stripped_list = [line.strip() for line in line_list]
>>> stripped_list
['line 1', 'line 2']

也可以使用"if"语句来选择某些元素：

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

通过列表生成式(list comprehension)，可以得到一个Python list，即stripped_list返回的是包含结果行的list，而不是迭代器。生成器表达式(generator expressions)返回一个迭代器，根据需要计算值，而不需要一次实现所有值。

这意味着如果返回无限流或非常大量数据的迭代器时，应使用生成器表达式。

下面是一个典型的生成器表达式，列表生成式只需将()换位[]。

1
2
3
4
5
6
7
8
( 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 )

实际上，上面的列表生成式或生成器表达式等同于以下Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
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.

生成器表达式必须写在圆括号中，但用于函数调用的括号也会被计数。因此，创建一个将被立即传递给函数的迭代器：

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

同时注意到，为了避免在Python语法中引入歧义，如果表达式创建一个元组，它必须用圆括号包裹。下面的第一个列表生成式语法错误，第二个正确：

1
2
3
4
# Syntax error
[x, y for x in seq1 for y in seq2]
# Correct
[(x, y) for x in seq1 for y in seq2]

生成器 Generators

生成器是一类特殊的函数，可以简化编写迭代器的任务。一般的函数计算一个值并将其返回，但生成器返回一个迭代器，这个迭代器返回一个数据流。

在Python中，调用一个函数时，它会得到一个私有命名空间，其中创建了局部变量。当函数到达return语句时，局部变量将被销毁，并且该值将返回给调用者。之后调用相同的函数将创建一个新的私有命名空间和一组新的局部变量。

但是，如何使局部变量在退出函数时不被销毁？如何恢复到之前调用函数离开时的位置？这正是生成器所提供的功能。

如下是生成器的简单示例：

1
2
3
>>> def generate_ints(N):
...    for i in range(N):
...        yield i

任何包含yield关键字的函数都是生成器函数，由Python的字节码编译器负责检测，该编译器专门编译该函数。

当调用生成器函数时，它不会返回单个值，相反，返回一个支持迭代器协议的生成器对象。

在执行yield表达式时，生成器输出i的值，类似于return语句。yield与return语句之间的差异在于，在达到yield时，生成器的执行状态将暂停并保留局部变量。当下一次调用生成器的__next__()方法时，函数将继续执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> gen = generate_ints(3)
>>> gen  
<generator object generate_ints at ...>
>>> next(gen)
0
>>> next(gen)
1
>>> next(gen)
2
>>> next(gen)
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)。

Python库 Lib/test/test_generators.py 中包含许多更有趣的示例。下面一个使用递归实现树的按中序遍历的生成器。

1
2
3
4
5
6
7
8
9
10
# 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-Queens问题（将N个皇后放置在NxN棋盘上，并保证一个皇后不会威胁到另一个皇后）和骑士之旅（在NxN棋盘中，骑士寻找不重复到达的每个方格的路线）。

传值给生成器 Passing values into a generator

在Python2.5及以后，可以将值简单的传递到生成器。yield成为一个表达式，返回一个可以赋值给一个变量或以其他方式运行的值：

1
val = (yield i)

建议在使用返回的值进行操作时，总是用()包裹yield表达式，如上例所示。

在PEP 342解释了这个规则，即一个yield-expression必须总是被加上括号，除非它出现在赋值右边的顶级表达式上，如val = yield i，但在有操作时使用括号，如val =（yield i）+ 12。

通过调用send(value)方法，可以将值传至生成器中。此方法恢复执行生成器的代码，且yield表达式返回指定的值。 如果调用__next__()方法，则yield返回None。

这里有一个简单的计数器，递增1并允许更改内部计数器的值。

1
2
3
4
5
6
7
8
9
def counter(maximum):
    i = 0
    while i < maximum:
        val = (yield i)
        # If value provided, change counter
        if val is not None:
            i = val
        else:
            i += 1

更改计数器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> it = counter(10)  
>>> next(it)  
0
>>> next(it)  
1
>>> it.send(8)  
8
>>> next(it)  
9
>>> next(it)  
Traceback (most recent call last):
  File "t.py", line 15, in <module>
    it.next()
StopIteration

因为yield通常会返回None，所以应该经常检查这个情况。除非确定send()方法将是唯一用于恢复生成器函数的方法，否则不要在表达式中使用。

除了send()，还有其他两个发生器方法

  • throw(type，value = None，traceback = None)用于在生成器内引发异常。生成器执行暂停时的yield表达式引发异常，之后会继续执行生成器对象中后面的语句，直至遇到下一个yield语句返回。如果在生成器对象方法执行完毕后，依然没有遇到yield语句，抛出StopIteration异常。
  • close()在生成器中引发一个GeneratorExit异常来终止迭代。在收到此异常时，生成器的代码必须抛出GeneratorExit或StopIteration，捕获异常并执行其他任何操作都是非法的，并且会触发RuntimeError。 当生成器销毁时，close()也将被Python的垃圾回收调用。

如果需要在发生GeneratorExit时运行清理代码，建议使用try：... finally：,而不是捕获GeneratorExit。

有了这些方法，将生成器从“一个单向信息生产者”转变为“一个生产者和消费者”。

生成器也成为了协程（coroutines），这是一种更普遍的子程序形式。

子程序，或者称为函数，在所有语言中都是层级调用，比如A调用B，B在执行过程中又调用了C，C执行完毕返回，B执行完毕返回，最后是A执行完毕。所以子程序调用是通过栈实现的，一个线程就是执行一个子程序。子程序调用总是一个入口，一次返回，调用顺序是明确的。

而协程的调用和子程序不同。协程看上去也是子程序，但执行过程中，在子程序内部可中断，然后转而执行别的子程序，在适当的时候再返回来接着执行。在一个子程序中中断，去执行其他子程序，不是函数调用，有点类似CPU的中断。

Reference

  1. Python官方文档：Python HOWTOs
  2. 面向函数范式编程(Functional programming)
  3. 廖雪峰Python教程