【Python环境】如何使用正确的姿势进行高效Python函数式编程？

关于函数式编程

有哪些函数式语言？

其实函数是语言很早就出现了，上世纪30年代出现的Lambda和50年代的LISP，比面向过程和对象的语言出现的更早，现代的Clojure，Erlang，Haskeel也为很多人所熟知，保持着很强的活力，Scala作为Spark和Kafka的实现语言也是相当的火。

什么是函数式语言？

和面向过程的编程语言(例如C等)和面向对象的语言(例如C++/Java等)相比，函数式语言是一种声明式的编程规约范式。 简单例子如下：

一个复杂些的例子：

计算如下字符串的值：

expr = "28+32+++32++39” ==> 28+32+32+39 ==> 131

命令式的语言采用一个初始值，然后一直去是修改它，最终获得结果。

而函数式风格通过函数的组合调用，通过函数的一层层转换输入输出最终获得结果。

作为一种风格，很多人的代码里面可能已经有一些是函数式的了。

函数式编程的特点

函数式编程有如下特点：

• 函数即为数据，第一等公民
• 高阶函数
• 纯函数： 避免状态，无副作用
• 不可变数据结构
• 强编译器
• 尾递归消除(TRE)
• 延迟，模式匹配(Pattern Match)，Monads

这个议题除了Monads，其他都有所覆盖。

回到Python，Python其实是一个具备了很强函数式能力的命令式编程语言，通过语言或者库的支持，对以上几乎所有特征都有所支持（除了强编译器）。

一些函数语言编译执行器可以在强预设下做很强的优化，例如直接并发，延迟处理或者次序调换等。 而Python却没有这一点支持，归根结底是因为Python从一开始就是按照命令式语言进行设计的。 Guido大叔曾经说过这样一段话：

"I have never considered Python to be heavily influenced by functional languages, ... I had made functions first-class objects, I didn't view Python as a functional programming language..."

尽管如此，函数式编程风格依然是一种非常不错的风格。 主要有几个原因：

1. 更好的测试性(因为无状态)，也更可靠
2. 更擅长流式与并发操作(例如Scala)
3. 一些偏主观的观点： 例如函数式编程风格有的时候提供了一种更加简洁巧妙的解决方案。 代码更少，可读性更好。

纯函数

第一等公民

就像Guido所说，Python中的函数已经是第一等公民了。皆可以作为变量，也可以作为参数传入传出，也可以随时Lambda定义，或者放入数据，所有操作符也都是已经函数化的了。

通过fn库，函数定义的方式可以进一步简化为Scala风格：

纯函数

无副作用

无副作用体现在对输入的数据本身无修改，对函数内部外部无状态修改。

如下的例子都是一些反例。

修改了输入

修改了外界状态

修改了输出，影响了原输入

真正纯的无状态和副作用的函数应该如下：

但是这可能比较复杂，性能也不太好。 这就要引入函数编程里的可持久化数据结构。

可持久化数据结构

一种支持修改，在不修改原版本的情况下，返回一个修改版本的数据结构。

Persistent Data

高阶函数

高阶函数就是接受或者返回函数的函数。

Python已有不错的支持：

• map，filter，groupby，reduce
• functools module
• list comprehension
• decorators

Map

map是函数式编程语言中很重要的高阶函数，接受函数对输入进行转换。

Filter

reduce接受函数对输入进行过滤。

List Comprehension

Map/Filter在函数式编程中非常重要，然后Python里面list Comprehension可能适用的更加广泛，过滤转换，最终构造出list，set，dict等都非常简单。

然而List Comprehension一些特性也需要注意，首先是第一层才是不可修改的，对于初学者而言，读取方式也稍微奇怪(先for，再if，最后看开头)，另外内部存在for/if，并没有函数模块化。

Groupby

Groupby接受函数对数据进行分组：

Reduce

Reduce接受二元函数对数据进行聚集：

Reduce的实现可以理解为如下：

相对应的sum，mul也可以直接使用reduce来完成

Partial

首先一个简单问题，如何构造一个默认是降序排列的Sorted2函数，如下：

一般的实现：

而使用Partial则简单的多。

Partial还可以用来预先参数绑定。 例如：

Compose

Compose是常用来构建更高级函数的工具：

Currying

Currying是对Partial的更进一步的扩展：

toolz.curried里面所有的函数都已经Curry化了。

Currying对于简化参数化Decorator也是非常有用的。 例如：

递归相关技术

关于递归

一些函数式语言里面没有loop，只能用递归。 而通常都支持尾递归消除(将递归转化为内部loop)

用递归的理由

代码逻辑更清晰。例如：

不用递归的原因

三个原因使得递归没有大量被使用，因为：

1. 递归调用有递归层数限制(Python是1000)，超过会栈溢出。
2. 重复计算。 fib(n-2)与fib(n-1)是存在重复计算的。
3. 递归调用常常需要不同情况进行跳转，需要大量使用overloading或者pattern match的技术。

关于尾递归消除(优化)

尾递归优化可以消除递归层数的限制，要求递归只存在于函数调用的最后一行，并且没有进一步计算。

如下是反例：

通常使用一个帮助函数，将计算放在计算放在参数传递时，是常用技巧：

Trampoline

然而坏消息是： Python并不支持尾递归消除！(Guido： 怪我咯！)

但并不用担心，Tranpline就是用来解决这个问题的。 添加fn.recur的decorator，对于要结束递归的分支，返回False开头的tuple，否则返回True开头的tuple即可。

消除重复计算

Python自带的lru_cache即可消除重复计算的问题：

另外推荐(cy)toolz里面的memoize，支持更多功能，例如cache可以让代码更简洁。

支持重载

Python语言本身是不支持函数重载的，但其语言自身函数功能也很强大：未命名参数，命名参数，变参，命名变参，解包机制等。

让Python支持类似于C++/Java等里面的重载，只需要引入multipledispatch.dsipatch即可，需要注意一开始的初始化。

重载使得递归的逻辑更加简洁

Haskell类强大的pattern match功能不仅支持类型重载，也支持参数特征匹配。 这在Python中通过库也是支持的。 至于实现机制，有兴趣的朋友可以看一下Python AST。

延迟

遍历器带来的延迟计算是Python核心惯用法。 常见的例子有：

• xrange
• tuple comprehension
• itertools 模块
• dict.iter* 方法
• generator
• for-loop 协议

fn.Stream

提供了进一步的语法糖，例如给跌代添加切片功能。

Generator对于实现无限迭代器是很方便的。

fn.Stream也支持通过流方式来实现。

更多迭代器可以在(cy)toolz.itertoolz中可以找到：

• 统计： count，groupby，frequency
• 过滤： unique，partition
• 选择： take，drop，first，last，n_th etc。
• merge_sorted

并行

值得一提的是函数式编程天生就是支持并行的。

Map

因为传递的函数是无状态无副作用的，所以可以直接并发执行，加快执行效率。

Reduce

同理，Reduce也是可以并发执行来进行二元聚集最终实现Log级别的性能优化。

Python多进程与分布式策略

算法大师Knuth说过："97%过早优化是罪恶之源"，在选择多进程或者分布式的时候考虑是否是唯一选择。 可能的其他选项有：

1. 选择不同的Python解释器： Cython，PyPy，numba等
2. 某些情况下分布式增加的管理复杂度不如单点增加多核来的有效。
3. 通过GPU提高计算效率是数据科学领域的一个趋势。
4. IO密集型并一定普遍适用于增加多进程的情况。

Python并发选择

GIL的原因，计算密集型是的多线程没有意义。

Python自带multiprocessing库提供了很不错的高阶接口。

分布式通用领域计算模型的选择有Spark，Hadoop，Celery等

对于数据科学方面，分布式numpy和全局数据矩阵发展的也非常快。

Python并发分布式库可较为成熟，供选择的也很多：

• 自带的Multiprocessing/RPC库
• IPython Cluster
• scikit-learn 并行算法
• Python Parallel(只有Py2)，Celery
• 更多： joblib等

并发计算与数据分发

并行计算只需要替换现有默认函数为并发函数即可。 例如Pool.map取代模块的map。

然而并发与分布式计算需要考虑如何把数据传入传出模块，一般的数据都是可以的。 然而Closure默认不能pickle化，这种情况下需要使用copy_reg扩展或者使用dill库。

IPython Cluster因为使用dill库，并不存在这个问题。

如下图是自带多进程库，IPython Cluster与Celery的一个比较，其中橙色勾表示需要一些额外代码来支持，叉表示需要较多额外工作支持。

总结

通过来强深入浅出的介绍，大家了解了如何使用Python进行高逼格函数式编程的技术，工具和实践。 使用Python也可以享受函数编程所带来的高模块，可复用，并发流处理等方面的好处。