函数式编程是种编程方式，它将电脑运算视为函数的计算。和指令式编程相比，函数式编程强调函数的计算比指令的执行重要。和过程化编程相比，函数式编程里函数的计算可随时调用。——百度百科
函数式编程通过在函数中定义表达式和对表达式求值完成计算。它尽量避免由于状态变化和使用可变对象引入复杂性，让程序变得简洁明了。
本文将介绍函数式编程的一些基本技术和基本原则，以及如何在流行编程语言Python中运用这些技术。
虽然Python不是纯粹的函数式语言，但仍然可以使用Python进行函数式编程。Python具备函数式编程的许多核心特征，使得我们可以借鉴其他函数式语言的设计模式和编程技术，编写出简洁优雅的代码。尤其值得一提的是Python的生成器表达式，使用它可以避免在内存中创建大型数据结构，通过降低资源消耗来提高执行速度。
最后我们还会介绍通过这些设计模式构建Python应用时，函数式编程带来的好处。
编程范式
简单说，"函数式编程"是一种"编程范式"（programming paradigm），也就是如何编写程序的方法论。它属于"结构化编程"的一种，主要思想是把运算过程尽量写成一系列嵌套的函数调用。——百度百科
编程范式并没有统一的划分标准。我们重点分析其中两个范式：函数式编程和命令式编程。二者最重要的特征区别是状态。
在命令式语言（比如Python）中，计算的状态是通过不同命名空间中变量的值反映的。变量的值决定计算的当前状态，一条语句通过增加或改变（甚至是删除）变量来改变当前状态。
“命令式”语言的每一条语句都是一个通过某种方式改变状态的命令。比如，Python中用于在命令空间中改变变量规则的global、nonlocal等，用于改变变量所处语境的def、class和import等，用作判断条件确定一组语句如何改变计算状态的try、except、if、elif和else等。而循环语句，如for和while，则是将一组语句作为整体以重复改变计算状态。可见所有这些语句都是通过某种方式改变变量状态的。
理想状态下，每一条语句通过改变状态，推动计算从初始状态向期望的最终结果不断靠近。然而，这种“推动计算一步步向前”的模式难以验证。需要首先定义出最终状态，找到能达到该状态的语句，从而推导出达到该状态需要的前提条件，然后重复上述步骤，直到找到一个可接受的初始状态。
在函数式语言中，使用“对函数求值”这一更简单的概念代替改变变量值的“状态”，每次对函数求值都会在现有对象的基础上创建一个或多个新对象。函数式程序即函数的组合，相应的开发过程是：首先设计一组易于理解的底层函数，然后在此基础上设计符合业务需求的高级函数。相比于由复杂的流程控制组成的指令集合，高级函数更容易可视化。
形式上，函数求值更接近算法的数学表达。以简单的代数形式设计算法，便于处理特殊情况和边界条件，而且函数更有可能按照预期工作，也便于编写单元测试用例。
请注意，通常函数式程序比功能相同的命令式（面向对象或者过程式的）程序更加简洁明了和高效，但这些优点并不是自然而然的，需要仔细地设计，但付出的努力通常少于设计功能类似的过程式程序。
细分过程范式
命令式编程可以再细分为多个子类别，比如过程式编程和面向对象编程，下面我们简单介绍下它们的区别，并重点讲解面向对象属于命令式编程的原因。
下面通过代码示例解释这些概念。
有些人觉得这么做是在重新造轮子，然而这其实是抽象概念的具体表现。
对于某些计算过程，完全可以忽略Python的面向对象特点，只使用简单的数值计算。例如用下面的方法可以得到一组属性相同的数。
s = 0 for n in range(1, 10): if n % 3 == 0 or n % 5 == 0: s += n print(s)
和m仅包括3或5的倍数。以上程序是严格过程式的，避免使用Python的任何面向对象特征。程序的状态由变量s和n定义，变量n的取值范围是1~10，每次循环中n的值依次增加，可以确定n == 10时循环结束。使用类似的原始数据结构，完全可以用C或者Java编写出功能相同的程序。
下面利用Python的面向对象编程（object-oriented programming，OOP）特征编写一段类似的代码。
m = list() for n in range(1, 10): if n % 3 == 0 or n % 5 == 0: m.append(n) print(sum(m))
程序运行结果与前面的结果相同，但它内部维护了一个状态可变的集合对象m，计算状态由m和n定义。
m.append(n)和sum(m)令人费解的语法让一些开发者误以为Python不是纯粹的面向对象语言：它混合了function()和object.method()两种语法。然而事实上Python是纯粹的面向对象语言，一些语言（例如C++）允许使用非对象的原始数据类型，例如int、float和long。Python中没有原始数据类型，前缀的语法形式不会改变语言的本质。
严格地说，完全可以采用纯粹的面向对象风格，基于list类生成一个包含sum方法的子类。
class Summable_List(list): def sum(self): s = 0 for v in self: s += v return s
接下来使用Summable_List()类代替list()方法初始化变量m，就可以用m.sum()方法代替sum(m)方法来对m求和了。该示例可以证明Python是纯粹的面向对象语言，前缀的使用仅是语法糖而已。
前面3个例子都基于变量值显式确定程序的状态，使用赋值语句改变变量值，推动计算前进。我们可以在程序中插入assert语句，确保程序状态完全按照要求变化。
关键之处不是命令式编程存在某种缺陷，而是函数式编程是一种思维方式的转变，这种改变适用于许多场景。下面介绍如何用函数式方法编写同一个算法，你会发现函数式编程并没有使算法显著变短或变快。
1.使用函数式范式
在函数式编程中，求3或5的倍数可分为两部分。
- 对一系列数值求和。
- 生成一个满足某个条件的序列，例如3或5的倍数组成的序列。
一个列表的和的递归形式定义如下。
def sumr(seq): if len(seq) == 0: return 0 return seq[0] + sumr(seq[1:])
可以把序列的和分为两种情况。基础形式：一个长度为0的序列，和为0。递归形式：序列的和等于序列中的第一个元素加上序列中后续元素的和。
由于递归形式的序列长度小于原序列，所以任何长度有限的序列最终都会退化为基础形式。
该函数运行示例如下。
>>> sumr([7, 11]) 18 >>> 7+sumr([11]) 18 >>> 18+sumr([]) 0
第一个例子计算了包含多个值的列表之和。第二个例子演示了递归规则将第一个值seq[0]和后续所有值的和seq[1:]相加。最后一个计算包含了对空列表求和，其值定义为0。
这个例子中，代码最后一行的+运算符和初始值0表明其为求和。如果将运算符从+改为*，将初始值从0改为1，则表明其为序列乘积。后面会详细介绍这种抽象化方法。
对于一列值，可以用类似的方法递归，定义如下。
def until(n, filter_func, v): if v == n: return [] if filter_func(v): return [v] + until(n, filter_func, v+1) else: return until(n, filter_func, v+1)
该函数的基础形式为：给定一个值v和一个上限n，如果v达到上限，则返回一个空列表。
根据filter_func()函数的不同返回值，递归形式有两种情况。如果v通过了filter_func()函数的测试，返回一个序列，则该序列的第一个元素是v，后续元素由until()作用于后续序列的返回值组成。如果v没有通过filter_func()函数的测试，将忽略该值，返回值由函数作用于剩余元素得到的值组成。
可以看到v在每次递归中递增，直到达到上限n，也就是基础形式。
下面介绍如何使用until()函数生成3或5的倍数。首先定义一个用于筛选数值的lambda对象。
mult_3_5 = lambda x: x % 3 == 0 or x % 5 == 0
（这里使用lambda定义简单函数是为了保持简洁。如果函数比较复杂，多于一行代码，请使用def语句。）
从命令提示符界面观察lambda的行为，如下所示。
>>> mult_3_5(3) True >>> mult_3_5(4) False >>> mult_3_5(5) True
结合until()函数，它可以生成一系列3或5的倍数。
使用until()函数生成一系列值，如下所示。
>>> until(10, lambda x: x % 3 == 0 or x % 5 == 0, 0) [0, 3, 5, 6, 9]
然后可以使用之前定义的递归版sum()函数计算一系列数值的和了。这里将用到的所有函数，包括sum()、until()和mult_3_5()，都定义为递归的，计算时不需要使用临时变量保存计算状态。
之后还会多次用到这种纯粹递归风格的函数来定义思想。请注意，许多函数式语言的编译器可以优化此类简单的递归函数，但Python不会进行此类优化。
2.使用混合范式
下面介绍如何用函数式编码实现前面计算3或5的倍数的例子。混合型函数的实现代码如下所示。
print(sum(n for n in range(1, 10) if n % 3 == 0 or n % 5 == 0))
这里使用了嵌入式生成器表达式迭代数值集合，并计算它们的和。range(1, 10)方法是可迭代的，所以它是一种生成器表达式，返回一个数值序列{n |1≤n < 10}。n for n in range(1, 10) if n % 3 == 0 or n % 5 == 0稍复杂一些，但它也是可迭代表达式，返回一个数值集合{n |1≤n < 10 ∧ (n mod 3 = 0 ∨ n mod 5 = 0)}。变量n与集合中的每个值绑定，表示集合的内容，而非当前的计算状态。sum()方法的输入值是一个可迭代表达式，输出最终计算结果：对象23。
绑定变量仅存在于生成器表达式内部，上述程序中，变量n在生成器表达式之外是不可见的。
可以将表达式中的if从句看作独立的函数，便于用其他函数替换它。可以使用一个名为filter()的高阶函数代替上面生成器表达式中的if从句。
这个例子中的变量n不同于前面两个命令式实现中的变量n，生成器表达式之外的for语句在本地命名空间中创建变量，而生成器表达式并不创建for语句式的变量。
>>> sum(n for n in range(1, 10) if n % 3 == 0 or n % 5 == 0) 23 >>> n Traceback (most recent call last): File "", line 1, in NameError: name 'n' is not defined
生成器表达式绑定的范围外不存在变量n，即它并不定义计算状态。
3.对象的创建过程
在某些情况下，观察中间对象有助于理解计算过程，但请注意，计算的路径并不是唯一的。当函数满足交换律和结合律的时候，改变求值顺序会创建出不同的中间对象。通过这种方式，可以在保证计算正确性的同时提升计算性能。
以下面这个表达式为例：
>>> 1+2+3+4 10
下面讲解不同的计算过程是如何得到相同的计算结果的。由于+运算符满足交换律和结合律，有许多条计算路径都能得到相同结果。
根据选择待计算值顺序的不同，有以下两种主要的计算路径。
>>> ((1+2)+3)+4 10 >>> 1+(2+(3+4)) 10
第一种情形是从左向右结合并求值，此时对象3和6作为求值过程的中间对象被创建出来。
第二种情形则是从右向左结合并求值，中间对象是7和9。在这个简单的整数算术运算中，两种方式的表现相同，优化无助于提升性能。
涉及数组的追加操作时，改变结合方式可能会提升性能。
示例如下。
>>> import timeit
>>> timeit.timeit("((([]+[1])+[2])+[3])+[4]")
0.8846941249794327
>>> timeit.timeit("[]+([1]+([2]+([3]+[4])))")
1.0207440659869462
可以看到，从左向右计算性能更佳。
对于函数式编程的设计，以任意顺序使用+运算符（或者add()函数），结果不变，即+运算符不影响使用方式。
4.乌龟塔
严格意义上，Python的函数式编程并非函数式的，Python不是Haskell、OCaml或Erlang。请注意，真正完成计算过程的处理器硬件本身就不是函数式的，甚至严格意义上不是面向对象的，CPU实际上是过程式的。
所有的编程语言都基于抽象、库、框架和虚拟机，这里的抽象又基于更底层的抽象、库、框架和虚拟机。有个很形象的比喻：整个世界被一只大乌龟驮在背上，这只大乌龟又被另外一只更大的乌龟驮在背上，这只更大的乌龟又被一只比它还大的乌龟驮在背上······
一言以蔽之：全是乌龟。
——佚名
抽象形成的层是无尽的。
更重要的是，这种抽象和虚拟机并不会影响通过Python的函数式特性设计软件。
即使在函数式语言内部，也存在更纯粹的语言和不太纯粹的语言。有些语言经常使用monads处理像文件系统输入、输出这样有状态的事务，另外一些语言则使用类似于Python的混合型环境，通过仔细地隔离含有状态的过程式动作来设计函数式的软件。
我们讲的函数式Python编程基于以下3层抽象。
- 应用由函数组成，直到层层分解碰到对象。
- 支撑函数式编程的Python运行时环境是由对象组成的，直到层层分解碰到库。
- 支撑Python运行的库就是驮着Python的乌龟。
更底层的操作系统和硬件有它们各自的乌龟塔，而且与我们要处理的问题无关。
函数式编程经典示例
下面我们基于John Hughes的论文“Why Functional Programming Matters”，来分析一个函数式编程的经典实例，这篇文章出自论文集Research Topics in Functional Programming。
此论文深入分析了函数式编程，并提供了几个例子，我们只分析其中的一个：用Newton-Raphson算法求解函数（平方根函数）。
该算法的许多实现都是通过loops显式管理状态的，比如Hughes的论文中就给出了一段Fortran代码，通过有状态的命令式流程求解。
算法的主体是如何根据当前的近似值计算出下一个近似值。函数next_()以sqrt(n)的当前近似值x为参数，计算出下一个近似值，并确保最终解就在之前近似值的范围内，代码如下所示。
def next_(n, x): return (x + n / x) / 2
该函数计算出一系列值
相近两个值的距离每次迭代减半，所以会迅速收敛到a=n/a，即
这里没有将迭代函数命名为next()，以避免与Python的内置函数发生冲突，使用next_()保证在不冲突的前提下尽量清晰地表达出函数的功能。
在命令提示符界面使用该函数，如下所示。
>>> n = 2 >>> f = lambda x: next_(n, x) >>> a0 = 1.0 >>> [round(x,4) for x in (a0, f(a0), f(f(a0)), f(f(f(a0))),)] [1.0, 1.5, 1.4167, 1.4142]
首先定义收敛到
的lambda表达式并赋值给变量f，将变量a0（0为下标）作为初始值，然后对一系列递归值求值：
等等。将这些函数放在一个生成器表达式中，便于对返回值做指定精度的四舍五入，从而使计算结果更易读，并便于doctest使用。该序列会快速地向根号2收敛。
我们可以编写一个函数，生成一个含ai（i为下标）的无限长序列，向平方根收敛。
def repeat(f, a): yield a for v in repeat(f, f(a)): yield v
该函数利用近似函数f()和初始值a生成近似值。如果把近似函数替换成前面定义的next_()函数，就可以得到关于参数n平方根的一系列近似值。
其中repeat()函数要求f()函数只有一个参数，而定义的next_()函数有两个参数。可以用一个匿名函数对象lambda x: next_(n, x)绑定其中一个变量，创建next_()函数的部分绑定版本。
Python的生成器函数不能自动实现递归，必须显式迭代递归结果，并一个一个单独生成计算结果。使用return repeat(f, f(a))并不能多次循环生成一系列值，而会结束迭代并返回一个生成器表达式。
有两种方法可以返回一系列值，而不是生成器表达式。
- 编写显式for循环：for x in some_iter: yield x
- 使用yield from语句：yield from some_iter
从递归生成器表达式中返回结果，这两种方法的效果相同，这里倾向于使用yield from语句。不过在有些情况下，yield结合复杂表达式，往往比相应的映射和生成器表达式更清晰。
当然，我们并不想计算无限长序列，只要两次迭代的近似值足够接近，就可以任取其中一个作为最终解。通常用希腊字母ε表示两个值足够接近，这里的含义是计算平方根的误差上限。
在Python中，我们需要设法从无限序列中一次取一个值，通常把复杂的递归包裹在简单的接口函数中，见如下代码片段。
def within(ε, iterable):
def head_tail(ε, a, iterable):
b = next(iterable)
if abs(a-b)
