Python 标准库中的functools和itertools模块，提供了一些函数式编程的工具函数。
functools 高阶函数
cache 与 lru_cache
用户缓存函数值的装饰器，可以缓存函数的调用结果。其中lru_cache函数可以设置一个缓存的最大容量，使用 LRU 算法淘汰长期不用的缓存。cache函数容量没有限制，相当于lru_cache(maxsize=None)。
@lru_cache(maxsize=3)
def fib(n):
if n <= 1:
return n
return fib(n - 1) fib(n - 2)
assert [fib(n) for n in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
@cache
def factorial(n):
return 1 if n == 0 else n * factorial(n - 1)
assert [factorial(n) for n in range(10)] == [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]partial 固定函数的一部分参数
partial() 会被“冻结了”一部分函数参数和/或关键字的部分函数应用所使用，从而得到一个具有简化签名的新对象。 例如，partial() 可用来创建一个行为类似于 int() 函数的可调用对象，其中 base 参数默认为二：
代码语言：javascript复制from functools import partial
basetwo = partial(int, base=2)
basetwo.__doc__ = 'Convert base 2 string to an int.'
assert basetwo('10010') == 18reduce
Python2 中的reduce函数是一个内置函数，在 Python3 中被移入了functools模块中。
原因是reduce函数的效率没有寻常的 for 循环高，而往往使用了reduce函数的代码也不是特别容易理解（对比map和filter）。
assert reduce(lambda x, y: x y, [1, 2, 3, 4, 5]) == 15itertools 实用的迭代器
itertools模块是 Python 参考 APL，Haskell，SML 等编程语言的启发，实现的个快速、高效利用内存的核心工具集。
在算法实现中利用好itertools模块，可以有效提高代码编写速度、可维护性和算法的效率。
islice
首先介绍一下islice函数，可用于迭代器切片。
assert list(islice('ABCDEFG', 3)) == ['A', 'B', 'C']无穷迭代器
count
count函数可以生成一个无穷的迭代器，每次调用返回一个整数，从 0 开始，每次增 1。
可以指定初始值，步长和生成数量。
count函数很适合替代while True:n =1的循环。
def gen_primes():
primes = []
for n in count(2):
if not any(n % p == 0 for p in primes):
primes.append(n)
yield n
assert list(islice(gen_primes(), 10)) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]cycle
cycle函数可以不断地迭代一个序列，直到迭代完成，然后重新开始迭代。
assert list(islice(cycle("ABC"), 6)) == ["A", "B", "C", "A", "B", "C"]repeat
repeat函数会不断地重复生成一个元素。
assert list(map(pow, range(6), repeat(3))) == [0, 1, 8, 27, 64, 125]有限数量的迭代器
accumulate
accumulate可以简单地理解为一个累加器。在很多需要计算列表的前缀和的算法中很有用。
assert list(islice(accumulate(count()), 5)) == [0, 1, 3, 6, 10]chain
chain函数可以理解为合并多个序列的迭代器。
st(chain("ABC", "DEF")) == ["A", "B", "C", "D", "E", "F"]dropwhile
dropwhile可以删除序列中的前缀元素，直到某个条件不满足。
assert list(dropwhile(lambda x: x < 5, [1, 4, 6, 4, 1])) == [6, 4, 1]filterfalse
filterfalse可以过滤出一个序列中不满足某个条件的元素。
assert list(filterfalse(lambda x: x % 2 == 0, range(10))) == [1, 3, 5, 7, 9]pairwise
pairwise类似于一个容量为 2 的滑动窗口，每次迭代返回一对元素。
asset list(pairwise([1, 2, 3, 4, 5])) == [(1, 2), (2, 3), (3, 4), (4, 5)]takewhile
takewhile遍历一个序列，直到第一个不满足某个条件的元素。
assert list(takewhile(lambda x: x < 5, [1, 4, 6, 4, 1])) == [1, 4]排列组合迭代器
product
product可以得到多个序列的笛卡尔积。
assert list(product("ABCD", "xy")) == [('A', 'x'), ('A', 'y'), ('B', 'x'), ('B', 'y'), ('C', 'x'), ('C', 'y'), ('D', 'x'), ('D', 'y')]permutations
permutations可以得到一个序列的全排列。
assert list(permutations([1, 2, 3])) == [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
assert list(permutations([1, 2, 3], 2)) == [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]combinations
combinations可以得到一个序列的组合。
assert list(combinations(range(4),2)) == [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]combinations_with_replacement
combinations_with_replacement可以得到一个序列的可重复组合。
list(combinations_with_replacement([1,2,3],2)) == [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]总结
使用 Python 实现算法相比其他语言的一个优势就是标准库中的itertools，可以节省大量编写 for 循环和递归函数的时间。
