函数式编程

函数式Python内建支持的一种封装，我们通过把大段代码拆成函数，通过一层一层的函数调用，就可以把复杂任务分解成简单的任务，这种分解称之为面向过程的程序设计。函数就是面向过程的程序设计的基本单元。

而函数式编程—-Functional Programming，虽然也可以归结到面向过程的程序设计，但是其思想更接近数学计算。

我们首先要弄清楚计算机和计算的概念。在计算机的层次上，CPU执行的是加减乘除的指令代码，以及各种条件判断和跳转指令，所以，汇编语言是最贴近计算机的语言。而计算则是指数学意义上的计算，越是抽象的计算，离计算机硬件越远。

对应到编程语言，就是越低级的语言，越贴近计算机，抽象程度低，执行效率高，比如C语言；越高级的语言，越贴近计算，抽象程度高，执行效率低，比如Lisp语言。

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

函数式编程的一个特点就是，允许函数本身作为参数传入另一个函数，还允许返回一个函数！Python对函数式编程提供部分支持，由于Python允许使用变量，因此，Python不是纯函数编程式编程语言。

高阶函数

高阶函数—-Higher-order function。

变量可以指向函数

以Python内置的求绝对值的函数abs()为例子，调用该函数的代码如下：

1 2	>>> abs(-10) 10

如果只写abs:

1 2	>>> abs <built-in function abs>

可见，abs是函数本身，abs(-10)是函数调用。

要获得函数调用结果，我们可以把结果赋值给变量：

1
2
3

>>> x=abs(-123)
>>> x
123

但是如果把函数本身赋值给变量呢：

1
2
3

>>> x=abs
>>> x(-123)
123

结论：函数本身也可以赋值给变量，即变量可以指向函数。如果一个变量指向了函数，那么，可以通过变量来调用这个函数。

函数名也是变量

函数名其实就是指向函数的变量！！！对于abs()这个函数，完全可以把函数名abs看成变量，他指向一个可以计算绝对值的函数。如果把abs指向其他对象，会发生什么？？

>>> abs=1
>>> abs(-1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'int' object is not callable

此时，abs这个变量已经不指向求绝对值函数，而是指向一个整数1。

传入函数

既然变量可以指向函数，函数的参数能接收变量，那么一个函数就可以接收另一个函数作为参数，这种函数被称为高阶函数：

1
2
3

>>> def add(x,y,f):
...     return f(x)*f(y)
...

当我们调用add(-4,2,abs)时，参数x,y,f分别接收-4,2,abs,验证一下：

1 2	>>> add(-4,2,abs) 8

编写高阶函数，就是让函数能够接收别的函数。

小结
把函数作为参数传入，这样的函数称之为高阶函数，函数式编程就是指这种高度抽象的编程范式。

map/reduce

Python中内建了map()和reduce()函数。

map()函数接收两个参数，一个是函数，一个是Iterable，map将传入的函数依次作用到序列的每个元素，并把结果作为新的Iterator返回。举例如下：我们有一个函数f(x)=x^2，要把这个函数作用在一个list[1,2,3,4,5,6,7,8,9]上就可以用map实现：

>>> L=[1,2,3,4,5,6,7,8,9]
>>> def f(x):
...     return x*x
...
>>> h=map(f,L)
>>> list(h)
[1, 4, 9, 16, 25, 36, 49, 64, 81]

map()传入的第一个参数是f，也就是函数对象本身。由于结果r是一个Iterator，Iterator是惰性序列，因此需要list()函数让它把整个序列都计算出来并返回一个list。

但是其实用循环也可以实现上述功能：

>>> L=[]
>>> for x in [1,2,3,4,5,6,7,8,9]:
...     L.append(f(x))
...
>>> L
[1, 4, 9, 16, 25, 36, 49, 64, 81]

这样也可以实现这个功能，但是循环中不能看出 ‘把f(x)作用于L上的每一个元素并生成一个新的list’ 的功能。所以map作为高阶函数，事实上吧运算规则抽象化了，因此，我们不仅可以计算简单的平法，也可以计算更加复杂的任意函数。比如把list 所有数字转为字符串：

1 2	>>> list(map(str,L)) ['1', '4', '9', '16', '25', '36', '49', '64', '81']

reduce把一个函数作用在一个序列[x1,x2,x3,...]上，这个函数必须接收两个参数，reduce把结果继续和序列的下一个元素做累积计算，其效果就是：

>>> from functools import reduce
>>> def add(x,y):
...     return x+y
...
>>> reduce(add,[1,2,3,4,5,6,7,8,9])
45

求和运算推荐用sum()函数，但是如果把序列[1,3,5,7,9]换为13579，就可以用reduce：

>>> def f(x,y):
...     return 10*x+y
...
>>> reduce(f,[1,3,5,7,9])
13579

这个例子本身没有什么实用性，但是考虑到字符串str是一个序列，对上面个的例子进行改动并配合map()函数，我们就可以把str转为int的函数：

>>> from functools import reduce
>>> def f(x,y):
...     return 10*x+y
...
>>> def char2num(s):
...     return {'0':0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9}[s]
...
>>> reduce(f,map(char2num,'13579'))
13579

还可以用lambda函数进一步简化：

>>> from functools import reduce
>>> def char2num(s):
...     return {'0':0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9}[s]
...
>>> def str2int(s):
...     return reduce(lambda x,y:x*10+y,map(char2num,s))
...
>>> str2int('13579')
13579

filter

Python内建的filter函数用于过滤序列。

和map类似，filter函数也接收一个函数和一个序列。不同的是filter把传入的函数依次作用于每个元素，然后根据返回值是Trueor False决定保留还是丢弃该元素。在一个list中，删掉偶数，保留奇数，可以这么写：

>>> def is_odd(s):
...     return s%2==1
...
>>> list(filter(is_odd,[1,2,3,4,5,6,7,8,9]))
[1, 3, 5, 7, 9]

把一个序列中的空字符串删掉，可以这么写：

>>> def not_empty(s):
...     return s and s.strip()
...
>>> list(filter(not_empty,['A','B',None]))
['A', 'B']

用filter求素数：

计算素数的一个方法是埃氏筛法，它的算法理解起来非常简单：
首先，列出从2开始的所有自然数，构造一个序列：2,3,4,5,6,7,8,9,10,...
取序列的第一个数2，他一定是素数，然后用2把序列的2的倍数筛掉：
3,5,7,9,11,13,...
取新数列的第一个数3，它一定是素数，然后用3把序列的3的倍数筛掉：
5,7,11,13,17,19,...
不断筛选下去，最终会得到所有的素数。

首先构造一个从3开始的奇数序列：

>>> def _odd_iter():
...     n=1
...     while True:
...             n=n+2
...             yield n
...

这是一个生成器，并且是一个无限序列。然后定义一个筛选函数：

1
2
3

>>> def _not_divisible(n):
...     return lambda x:x%n>0
...

最后定义一个生成器，不断返回下一个素数：

>>> def primes():
...     yield 2
...     it=_odd_iter()
...     while True:
...             n=next(it)
...             yield n
...             it=filter(_not_divisible(n),it)
...

这个生成器先返回第一个素数2，然后利用filter不断产生筛选后的新的序列。由于primes也是一个无限序列，所以退出时需要一个退出循环的条件：

>>> for n in primes():
...     if n<1000:
...             print(n)
...     else:
...             break
...

sorted

排序算法

排序也是在程序中经常遇到的算法，无论使用冒泡排序还是快速排序，排序的核心是比较两个元素的大小。如果是数字，我们可以直接比较，但是如果是字符串或者两个dict时，直接比较数学书的大小是没有意义的，因此，比较的过程必须通过函数抽象出来。

Python内置的sorted()函数就可以对list进行排序：

1 2	>>> sorted([23,43,5,-5,122]) [-5, 5, 23, 43, 122]

此外，sorted()函数也是一个高阶函数，它还可以接收一个key来实现自定义的排序，比如按照绝对值大小排序：

1 2	>>> sorted([23,43,5,-7,122],key=abs) [5, -7, 23, 43, 122]

key指定的函数作用于list上的每一个元素，并根据key函数的返回值进行排序。对比原始的list和经过key=abd 处理过的list:

list=[23,43,5,-7,122]
key=[23,43,5,7,122]

然后sorted()函数按照key进行排序，并按照对应关系返回list相应的元素。

我们再来看一个字符串排序的例子：

1 2	>>> sorted(['bob','james','curry','Kobe']) ['Kobe', 'bob', 'curry', 'james']

默认情况下，对字符串的排序，是按照ASCII的大小比较的，由于'Z'<'a'，所以大写字母Z是排在小写字母a前面的。

当我们提出排列时忽略大小写，按照字母排序，要实现这个算法，不必对现有代码加大改动，只要我们能用一个key函数把字符串映射为忽略大小写排序即可。忽略大小写来比较两个字符串，实际上就是先把字符串都变成大写（小写）再比较

这样我们给sorted()传入key函数，即可忽略大小写的排序：

1 2	>>> sorted(['bob','james','curry','Kobe'],key=str.lower) ['bob', 'curry', 'james', 'Kobe']

要进行反向排序，不必改动key函数，可以传入第三个参数reverse=True：

1 2	>>> sorted(['bob','james','curry','Kobe'],key=str.lower,reverse=True) ['Kobe', 'james', 'curry', 'bob']

sorted()也是一个高阶函数。用sorted()排序的关键是实现一个映射函数。

返回函数

函数作为返回值

高阶函数除了可以接受函数作为参数外，还可以把函数作为结果返回。

我们来实现一个可变参数的求和。通常情况下，求和函数式这样定义的：

>>> def cal_sum(*args):
...     ax=0
...     for x in args:
...             ax=ax+n
...     return ax
...

但是，如果不需要立即求和，而是在后面的代码中根据需要再进行计算怎么办？可以不返回求和的结果，而是返回求和的函数：

>>> def lazy_sum(*args):
...     def sum():
...             ax=0
...             for n in args:
...                     ax=ax+n
...             return ax
...     return sum
...

当我们调用lazy_sum()时，返回的并不是求和结果，而是求和函数，调用函数f时，才真正计算求和的结果：

>>> f=lazy_sum(1,2,3,4,5,6)
>>> f
<function lazy_sum.<locals>.sum at 0x000001BA761FF378>
>>> f()
21

在这个例子中，我们在函数lazy_sum中又定义了sum，并且，内部函数sum可以引用外部函数lazy_sum的参数和局部变量，当lazy_sum返回函数sum时，相关参数和变量都保存在返回的函数中，这种程序结构称为‘闭包’（Closure）。

请再注意一点，当我们调用lazy_sum时，每次调用都会返回一个新的函数，即使传入相同的参数。

闭包

注意到返回的函数在其内部引用了局部变量args，所以，当一个函数返回了一个函数后，其内部的局部变量还被新函数引用，所以，闭包用起来简单，实现起来不容易。另一个需要注意的问题是，返回的函数并没有立刻被执行，而是在调用了f()之后才执行：

>>> def count():
...     fs=[]
...     for i in range(1,4):
...             def f():
...                     return i*i
...             fs.append(f)
...     return fs
...
>>> f1,f2,f3=count()
>>> f1
<function count.<locals>.f at 0x000001BA761FF730>
>>> f1()
9
>>> f2()
9
>>> f3()
9

在上面的例子中，每次循环都创建了一个新的函数，然后，把创建的三个函数都返回了。调用三个函数结果不是1，4，9而都是9。原因在于返回的函数引用了局部变量i，但是它不是立刻执行，等到三个函数都返回时，引用的变量i变为3，因此最终的结果为9

返回闭包时牢记的一点是，返回函数不要引用任何循环变量，或者后续会发生变化的变量。如果一定要引用循环变量时，可以新建一个函数，用该函数的参数绑定循环变量的当前值，无论该循环变量后续如何更改，已经绑定到函数参数的值不变：

>>> def count():
...     def f(j):
...             def g():
...                     return j*j
...             return g
...     fs=[]
...     for i in range(1,4):
...             fs.append(f(i))
...     return fs
...
>>> f1,f2,f3=count()
>>> f1()
1
>>> f2()
4
>>> f3()
9

小结
一个函数可以返回一个计算结果也可以返回一个函数。返回一个函数时，牢记该函数并未执行，返回函数中不要引用任何可能会变化的变量。

匿名函数

当我们传入函数时，有些时候，不需要显示的定义函数，直接传入匿名函数更方便。在Python中，对匿名函数提供了优先支持。以map()函数为例，计算f(x)=x^2时，除了定义一个函数外，还可以传入匿名函数：

1 2	>>> list(map(lambda x:x*x,[1,2,3,4,5,6,7,8,9])) [1, 4, 9, 16, 25, 36, 49, 64, 81]

通过对比可以看出，匿名函数lambda x:x*x实际上就是：

1 2	>>> def f(x): ... return x*x

关键字lambda表示匿名函数，冒号前面的x表示函数参数。

匿名函数有个限制，就是只能有一个表达式，不用写return，返回值就是该表达式的结果。用匿名函数有个好处，因为函数没有名字，不必担心函数名冲突。此外，匿名函数也是一个函数对象，也可以把匿名函数赋值给一个变量，再利用变量来调用该函数：

>>> f=lambda x:x*x+x
>>> f
<function <lambda> at 0x00000230CEB4F510>
>>> f(16)
272

同样，也可以把匿名函数作为返回值返回：

1 2	>>> def build(x,y): ... return lambda:xx+yy

装饰器

由于函数也是一个对象，而且函数对象可以被赋值变量，所以，通过变量能调用该函数。

>>> def now():
...     print('2016-11-23')
...
>>> f=now
>>> f()
2016-11-23

函数对象有一个__name__属性，可以拿到函数的名字：

>>> now.__name__
'now'
>>> f.__name__
'now'

现在，假定我们要增强now()的功能，比如，在函数调用前后自动打印日志，但又不希望修改now()的定义，这种在代码运行期间动态增加功能的方式，称之为“装饰器”（Decorator）

本质上，decorator就是一个返回函数的高阶函数。所以我们要定义一个能打印日志的decorator如下：

>>> def log(func):
...     def wrapper(*args,**kw):
...             print('call %s():' %func.__name__)
...             return func(*args,**kw)
...     return wrapper
...

观察上面的log，因为他是一个decorator，所以接受一个函数作为参数，并返回一个函数。我们借助Python的@语法，把decorator置于函数的定义处，调用now函数，不仅会运行now函数本身，还会在运行该函数前打印一行日志：

>>> @log
... def now():
...     print('2016-04-09')
...
>>> now()
call now():
2016-04-09

把@log放到now()函数的定义处，相当于执行了语句：

now=log(now)

由于log()是一个decorator，返回一个函数，所以，原来的now()函数仍然存在，只是现在同名的now变量指向了信道函数，于是调用now()将执行新函数，即在log()函数中返回的wrapper()函数。

wrapper()函数的参数定义是(*args,**kw)，因此，wrapper()函数可以接受任意参数的调用。在wrapper()函数内，首先打印日志，再紧接着调用原始函数。

如果decorator本身需要传入参数，那就需要编写一个返回decorator的高阶函数，写出来很复杂，比如要自定义log的文本：

>>> def log(text):
...     def decorator(func):
...             def wrapper(*args,**kw):
...                      print('%s %s():' % (text, func.__name__))
...                     return func(*args,**kw)
...             return wrapper
...     return decorator
...

这个三层嵌套的decorator用法如下：

>>> @log('execute')
... def now():
...     print('2015-3-25')
...
>>> now()
execute now():
2015-3-25

和两层嵌套的decorator相比，3层嵌套的decorator的效果是这样的：

now=log(‘execute’)(now)

上面的语句中，首先执行log('execute')，返回的是decorator函数，再调用返回的函数，参数是now的函数，返回值最终是wrapper的函数。以上两种decorator的定义都没有问题，但还差最后一步。我们讲了函数也是对象，有__name__等属性，但你去看经过decorator装饰之后的函数，它们的__name__属性已经从原来的now变为了wrapper：

1 2	>>> now.__name__ 'wrapper'

因为返回的那个wrapper()函数的名字就是wrapper，所以，需要把原始函数的__name__等属性复制到wrapper()函数中，否则，有些依赖函数签名的代码执行就会出错。

不需要编写wrapper.__name__=func.__name__这样的代码，Python内置的functools.wraps就是干这个事情的，所以一个完整的decorator如下：

>>> import functools
>>> def log(func):
...     @functools.wraps(func)
...     def wrapper(*args,**kw):
...             print('call %s():' % func.__name__)
...             return func(*args,**kw)
...     return wrapper
...

或者针对带参数的decorator：

import functools
def log(text):
    def decorator(func):
        @functools.wraps(func)
        def wrapper(*args, **kw):
            print('%s %s():' % (text, func.__name__))
            return func(*args, **kw)
        return wrapper
    return decorator

小结
在面对对象的设计模块中，decorator被称为装饰模式。OOP的装饰模式需要通过继承和组合来实现，而Python除了能支持OOP的decorator外，直接从语法层次支持decorator。Python的decorator可以用函数实现，也可以用类实现。

decorator可以增强函数的功能，定义起来虽然有点复杂，但使用起来非常灵活和方便。

偏函数

Python的fucntools模块提供了很多有用的功能，其中一个就是偏函数(Partial function)。要注意，这里的偏函数和数学上的偏函数不一样。在介绍函数参数的时候，我们讲到，通过设定参数的默认值，可以降低函数调用的难度。而偏函数也可以做到这一点。

如int()函数可以把字符串装换为整数，当仅传入字符串时，int()函数默认按照十进制装换：

1 2	>>> int('12354') 12354

但int()函数还提供额外的base参数，默认值为10，如果传入base参数，就可以做N进制装换：

>>> int('12354',base=16)
74580
>>> int('12354',base=12)
24688

假设要装换大量二进制字符，每次都传入int(x,base=2)非常麻烦，我们可以定义一个int2()函数，默认把base=2传进去：

>>> def int2(x,base=2):
...     return int(x,base)
...
>>> int2('111001')
57
>>> int2('111001100101010')
29482

functools.partial就是帮我们创建一个偏函数的，不需要我们自己定义int2()，可以直接使用下面的代码创建一个新的函数int2：

>>> import functools
>>> int2=functools.partial(int, base=2)
>>> int2('111001')
57

所以简单总结functllos.partial的作用就是，把一个函数的某些参数给固定住，返回一个新的函数，调用这个新函数会更简单。注意到上面的int2函数，仅仅是把base参数重新设定位2，但可以在函数调用时传入其他值：

1 2	>>> int2('1111111100',base=4) 349520

最后，创建偏函数时，实际上可以接收函数对象，args,*kw三个参数，当传入int2=functools.partial(int, base=2)实际上固定了int()函数的关键字参数base，也就是int2('10010')相当于：

kw={‘base’ : 2}
int(‘10010’,**kw)

当传入max2 = functools.partial(max, 10)实际上会把10作为*args的一部分自动加到左边，也就是max2(5,6,7)相当于：

args=(10,5,6,7)
max(*args)