Python并非经典的FP(Functional Programming, 函数式编程)语言，用其原生的map/filter/reduce写法来实现函数式编程显得相当臃肿；好在可以通过第三方库提供的语法糖来简化代码。
本文将简明扼要地示范两个常用库的写法；读完，你就能写出一手优雅而简洁的函数式Python代码了

• 使用PyFunctional来提供类似Streaming API，形成链式调用
• 使用fn.py来简化lambda表达式的书写

背景

FP (Functional Programming, 函数式编程) 是一种有效、简洁、优雅，且对并发相当友好的编程范式。
可惜python并不原生地支持FP；原因之一是Python的作者Guido大爷并非FP的粉丝，下面是老爷子对FP的看法^[1]

I have never considered Python to be heavily influenced by functional languages, no matter what people say or think. I was much more familiar with imperative languages such as C and Algol 68 and although I had made functions first-class objects, I didn't view Python as a functional programming language. However, earlier on, it was clear that users wanted to do much more with lists and functions.

...

It is also worth noting that even though I didn't envision Python as a functional language, the introduction of closures has been useful in the development of many other advanced programming features. For example, certain aspects of new-style classes, decorators, and other modern features rely upon this capability.

Lastly, even though a number of functional programming features have been introduced over the years, Python still lacks certain features found in “real” functional programming languages. For instance, Python does not perform certain kinds of optimizations (e.g., tail recursion). In general, because Python's extremely dynamic nature, it is impossible to do the kind of compile-time optimization known from functional languages like Haskell or ML. And that's fine.

--- Guido van Rossum

经过一段时间的摸索和总结，我找到了一套适用于Python的比较简洁的FP最佳实践。具体来说就是使用文章开头提到的两个库，下面分别演示一下这两个库的基础用法，并结合几个实际工作中的例子略作演示。
注意：本文既然是写BCP，就打算只讲干货，尽量少些奇技淫巧；如果想进一步深入了解；我会在文末给出一些阅读材料

PyFunctional

PyFunctional提供了Streaming API，非常方便序列的链式操作，此外还有提供一些IO小工具。
下面来看几个例子。

IO

pip install pyfunctional

%%bash
mkdir ./res
cat << EOF > ./res/json_lines.json
{"name":"Alice", "age":5}
{"name":"Bob", "age":6}
EOF

from functional import seq # 注意包名不是pyfunctional
seq.jsonl('./res/json_lines.json')
# [{'age': 5, 'name': 'Alice'}, {'age': 6, 'name': 'Bob'}]

seq.jsonl('./res/json_lines.json').to_pandas()

to_pandas.png

Streaming API

# range 的用法
assert seq.range(5) == seq(range(5)) 
assert seq.range(5) == seq([0,1,2,3,4])
assert seq.range(5) == seq(0,1,2,3,4)
assert seq.range(5) == [0,1,2,3,4]

accumulate / aggregate

accumulate是aggregate的一个特例；所以已经deprecated
aggregate支持1～3个参数，分别代表

• arg1: init_value=None， 聚合开始时所用的初始值
• arg2: fn, (current, next) ==> result， 两两聚合所用的函数
• arg3: agg_func=None， 在返回结果前执行的最后一个映射

seq.range(5).aggregate(-2, operator.add, str)
# '8'

Cartesian 笛卡尔积

s1 = range(2)
s2 = set('abc')
seq(s1).cartesian(s2).to_list() # 求s1与s2的笛卡尔积
# [(0, 'a'), (0, 'b'), (0, 'c'), (1, 'a'), (1, 'b'), (1, 'c')]

count / count_by_key / count_by_value

f = X%2==0
seq.range(5).count(f) # 这个f必填
# 3

# count_by_key 已经过时，用 reduce_by_key近似
seq([('a', 1), ('b', 2), ('b', 3), ('b', 4), ('c', 3), ('c', 0)]) .reduce_by_key(operator.add).to_list()
# [('a', 1), ('b', 9), ('c', 3)]

# count_by_value不可用，用Counter近似
from collections import Counter
s = seq(['a', 'a', 'a', 'b', 'b', 'c', 'd'])
Counter(s)
# Counter({'a': 3, 'b': 2, 'c': 1, 'd': 1})

dict

import numpy as np

# 可以直接传固定值
# d = seq([('a', 1), ('b', 2)]).dict('nan')

# 也可以传default_func，就像 defaultdict(default_func) 一样
d = seq([('a', 1), ('b', 2)]).dict(np.random.rand)
d['a'],d['c'],d['d'],d['e'] # 每次求新值的时候，要运行一下defaultdict的init_value函数
# (1, 0.1045269208888322, 0.2721328917391167, 0.8890019300218747)

d['a'],d['c'],d['d'],d['e'] # 多次执行有缓存
# (1, 0.1045269208888322, 0.2721328917391167, 0.8890019300218747)

drop / drop_right / drop_while

seq([1, 2, 3, 4, 5]).drop(2) # 去掉开头的2个元素
seq([1, 2, 3, 4, 5]).drop_right(2) # 去掉结尾的2个元素
seq([1, 2, 3, 4, 5, 9, 2]).drop_while(X < 3) # 一直drop，直到遇到条件为False
# [3, 4, 5, 9, 2]

exists / for_all

seq(1,2).exists(X>=2)
# True

def is_even_log(n):
    print('log: {}'.format(n))
    return n%2==0
seq.range(10).for_all(is_even_log) # for_all是当且仅当序列中的全部元素都能算出True时，才为True；从log看，有lazy_eval
# log: 0
# log: 1
# Out[31]: False

flatmap / flatten

seq([[1, 2], [3, 4], [5, 6]]).flatten() # 将 arr_or_arr 展开打平 
# [1, 2, 3, 4, 5, 6]

arr_of_arr = [[1, 2, 3], [3, 4], [5, 6]]
fn = X
seq(arr_of_arr).flat_map(lambda a: [min(a),]*4)
# 对arr_of_arr中的每个子序列执行fn映射，得到新的子序列（记作ARR）；然后对ARR组成的大序列执行flatten
# [1, 1, 1, 1, 3, 3, 3, 3, 5, 5, 5, 5]

fold_left / fold_right

# 从起始值开始， 逐个调用传入的fold函数
seq.range(3).fold_left('a', lambda c,n: '{}_{}'.format(c,n) ) 
# 'a_0_1_2'

# 从起始值开始， 逐个调用传入的fold函数； 注意lambda中两个参数的顺序互换了
seq.range(3).fold_right('a', lambda n,c: '{}_{}'.format(c,n) ) 
# 'a_2_1_0'

group_by / group_by_key / grouped

seq(["abc", "ab", "z", "f", "qw"]).group_by(len).list()
# [(1, ['z', 'f']), (2, ['ab', 'qw']), (3, ['abc'])]

seq([('a', 1), ('b', 2), ('b', 3), ('b', 4), ('c', 3), ('c', 0)]).group_by_key().list()
# [('a', [1]), ('b', [2, 3, 4]), ('c', [3, 0])]

# group支持相邻元素大致分组，可以用slicing近似（后文有提到）
# 这里的两个list函数，是为了方便观察（不然就打印出一堆generator）
seq([1, 2, 3, 4, 5, 6, 7, 8]).grouped(3).map(list).list()
# [[1, 2, 3], [4, 5, 6], [7, 8]]

init / inits / tail / tails

assert seq.range(5).init() == seq.range(5).drop_right(1)
# 命名很诡异，init不是(initialization, 初始化)，而是除最后一个元素以外的子序列
seq.range(5).init()
# [0, 1, 2, 3]

seq.range(5).inits().list() # inits 是含开头元素的所有子序列
# [[0, 1, 2, 3, 4], [0, 1, 2, 3], [0, 1, 2], [0, 1], [0], []]

seq.range(5).tail() # 除开头元素以外的子序列
# [1, 2, 3, 4]

seq.range(5).tails().list() # 含尾元素在内的所有子序列
# [[0, 1, 2, 3, 4], [1, 2, 3, 4], [2, 3, 4], [3, 4], [4], []]

join

seq([('a', 1), ('b', 2), ('c', 3)]).join([('a', 2), ('c', 5)], "inner") # inner是默认行为，可省略
# [('a', (1, 2)), ('c', (3, 5))]

seq([('a', 1), ('b', 2)]).join([('a', 3), ('c', 4)], "left")
# [('a', (1, 3)), ('b', (2, None))]

seq([('a', 1), ('b', 2)]).join([('a', 3), ('c', 4)], "right")
seq([('a', 1), ('b', 2)]).join([('a', 3), ('c', 4)], "outer")

make_string

其实就是str.join，但是join关键字已经被用了

seq(['a','b',1,{'name':'jack'}]).make_string('@')
# "a@b@1@{'name': 'jack'}"

order_by

from fn import F # 这是fn.py提供的复合函数语法糖，后文有讲
seq(1,'abc',55,9999,718).order_by(F(str)>>len)
# [1, 55, 'abc', 718, 9999]

partition

seq.range(-5,5).partition(X>0) # 返回 (truthy, falsy)
# [[1, 2, 3, 4], [-5, -4, -3, -2, -1, 0]]

reduce_by_key

seq([('a', 1), ('b', 2), ('b', 3), ('b', 4), ('c', 3), ('c', 0)]).reduce_by_key(X+X)
# [('a', 1), ('b', 9), ('c', 3)]

sliding 滑动窗口

第一个参数是size，第二个是step(默认=1)

# 模拟100ms的语音，每25ms为一帧，滑动窗口为10ms
seq.range(100).sliding(25, 10)

# [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24],
# [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34],
# ...

sorted

seq('a1','c9','b3','b2').sorted(key=X[1], reverse=True)
# ['c9', 'b3', 'b2', 'a1']

starmap / smap

starmap是把序列中的元素作为参数，逐个用func作映射

seq([(2, 3), (-2, 1), (0, 10)]).smap(X+X)
# [5, -1, 10]

zip / zip_with_index

seq.range(3).zip('abc').list()
# [(0, 'a'), (1, 'b'), (2, 'c')]

seq(list('abc')).zip_with_index(start=9).list()
# [('a', 9), ('b', 10), ('c', 11)]

fn.py

fn.py提供了一些高级的FP工具，本身也提供了类似于PyFunctional的一部分基础FP功能(e.g. map/reduce/filter)；但是这些功能在fn.py中不支持链式调用语法，不太方便，本文就不讲了
除此之外，fn.py还提供了一些高级的FP特性，包括：

• underscore表达式
• 函数复合管道F()
• 无穷Stream
• Monad Optional
• TCO 尾递归优化
• Immutable容器
• ...

初次看到这些概念的同学可以会对一部分术语感到陌生，但是不用担心，后面我会在例子中讲清楚

underscore表达式

熟悉前端的同学应该听说过，有个Javascript库叫作Underscore.js；它提供了一种用于书写lambda表达式的语法糖^[2]
fn.py也提供了类似的功能

Identity 常函数

先安装： pip install fn

from fn import _ as X # 在ipython环境中，下划线有特征语义，要回避开
f = X # 空的underscore本身就是Identity函数
print(f) # (x1) => x1
print(f(10)) # 10

Arithmetic 基础算术

f = X+2
f(3) # 5

# 还支持 乘方/取模/移位/取反/位运算 ...
(X ** 2)(3) # 9
(X % 2)(3) # 1
(X << 2)(8) # 32
(1 & X)(0) # 0

多参数

(X-X)(5,3) # 2

property/attribute getter

class Foo(object):
    def __init__(self):
        self.attr1 = 10
        self.attr2 = 'mystr'
    @property
    def prop1(self):
        return self.attr2.upper()
    def method1(self):
        return self.attr2.capitalize()
    
foo = Foo()
(X.attr1*-2)(foo) # -20
(X.attr2)(foo) # 'mystr'
(X.prop1)(foo) # 'MYSTR'
(X.method1())(foo) # ArityError, 不支持这样调method，正确用法见下文

method caller

f = X.call('method1')
f(foo) # 'Mystr'

f = X.call('split','-')
f('abc-def') # ['abc', 'def']

d = {'num':32}
f = X.call('update', num=42)
f(d) # None
d # {'num': 42}

str

可以用一种可能读较好的方式把underscore表达式打印出来，还能自动处理优先级

f = X + X * X 
str(f) # '(x1, x2, x3) => (x1 + (x2 * x3))'

函数复合管道F()

from fn import F

f = X * 2
g = X + 10
h = X * 10

func = F(f) << g << h
func(5) # [(?*10) + 10] * 2
# 注意 << 是向内复合，好记：箭头从右向左指，表示先执行右边的，再代入左边的函数

(F(f) << F(g) << F(h))(5)  # 多个F对象也可以复合

# F()中预填入一部分参数，就是partial
import operator
f = F(operator.sub, 10)
f(3) # 7

# Pipe Composition 向外复合
f = F(X**2) >> (X + 10)
f(5) # 35

无穷Stream

这是一个比较难懂的语法，我也没空去读源码搞透彻；大概意思就是一个懒汉式的生成器的串联。

Lazy-evaluated Scala-style streams. Basic idea: evaluate each new element "on demand" and share calculated elements between all created iterators. Stream object supports << operator that means pushing new elements when it's necessary.

--- 官网解释

下面的demo尽量体会一下就好，不求甚解。

from fn import Stream

# 递归slice
s = Stream() << range(10)
list(s[2:9][:3])  # s[2:9]是[2,3,4,5,6,7,8]，对这个Stream再取[:3]就是[2,3,4]

# fibonacci
s = Stream() << [0, 1]
fib = s << iters.map(operator.add, s, iters.drop(1, s))
# 注意最右边的<<是一直在往Stream里面插入新值，导致s的cursor往后走
list(iters.take(5, fib))

Monad Optional^[3]

跟Java8的Optional差不多，用来包裹Nullable对象

基本用法

from fn import monad

monad.Option(10, checker=X > 70) # Empty()
monad.Empty(5) # Empty()
monad.Full(10) # Full(10)
monad.Option.from_value(10) # Full(10)
monad.Option.from_call(X**2, 5) # Full(25)
monad.Option.from_call(X[X], dict(k='v'), 'bad_k', exc=KeyError) # Empty()

# 自动flatten，说明这个库内部还是有优化的
monad.Option(monad.Option(monad.Option(10))) # Full(10)

map/filter, 这个比较实用，用函数式的方法从Nullable中安全地取值

class Request(dict):  # 注意这里有个继承
    def param(self, name):
        return monad.Option(self.get(name, None))  # 注意这里，手动包了一层monad.Option

    # 注意，这个函数跟上面功能相同；只是自动被包裹了一层 Option；不用自己写monad.Option(...)；可读性更好，且对旧代码改动小
    @monad.optionable
    def optParam(self, name):
        return self.get(name, None)
# 定义好对象
req = Request(testing='Fixed', empty='')

# demo1: 顺利取值
(req.param('testing')  # 拿到monad参数
 .map(operator.methodcaller('strip'))  # 去掉首尾空白字符
 .filter(len)  # 去掉空串
 .map(operator.methodcaller('upper'))  # 转大写
 .get_or('empty_value')  # 取出值来
)
# 'FIXED'

# demo2: 注解式写法的optParam跟上面等效
(req.optParam('testing')  # optParam函数用的是注解式写法
 .map(operator.methodcaller('strip')).filter(len)
 .map(operator.methodcaller('upper')).get_or('empty_value'))
# 'FIXED'

# demo3: 用filter滤掉指定的值后，变成Empty
(req.param('empty').map(operator.methodcaller('strip'))
 .filter(len)  # 去掉空串, 变成Monad(None)
 .map(operator.methodcaller('upper')).get_or('empty_value'))
# 'empty_value'

# demo4: 一开始就到Optional(None)，即Empty；后面的链式map/filter步骤skip
(req.param('missing')  # missing字段不存在，拿到的是Monad.Empty
 .map(operator.methodcaller('strip')).filter(len)
 .map(operator.methodcaller('upper')).get_or('empty_value'))
# 'empty_value'

or_call调用，通过函数来取fallback值

# demo1: 直接取到值
r = dict(type='jpeg')
# 注意第一步就用monad.Option给包裹起来了，后面才能方便的链式调用or_call/map等方法
(monad.Option(r.get('type', None))  # 直接得到Full值，下面的or_call被跳过
 .or_call(from_mimetype, r)
 .or_call(from_extension, r)
 .map(operator.methodcaller('upper'))
 .get_or('unknown'))
# 'JPEG'
 
# demo2: 直接用返回值None表示Empty
from_mimetype = X.call('get', 'mimetype', None) # 可以直接返回值（None）表示Empty
r = dict(mimetype='png')
(monad.Option(r.get('type', None))  # monad.Empty
 .or_call(from_mimetype, r) # 上面是Emtpy，触发这一步or_call的执行,得monad.Full('png')
 .or_call(from_extension, r) # 已经是Full值，这个or_call被跳过
 .map(operator.methodcaller('upper'))
 .get_or('unknown'))
 
# demo3: 显式地返回Empty
def from_extension(r):
    return (monad.Option(r.get('url', None)).map(X.call('split', '.')[-1]))
r = dict(url='image.gif')
(monad.Option(r.get('type', None))  # monad.Empty
 .or_call(from_mimetype, r) # 这一步调用返回None,还是Empty
 .or_call(from_extension, r)  # 这个函数是显式地返回了Empty，跟上面的demo等效,得monad.Full('gif')
 .map(operator.methodcaller('upper'))
 .get_or('unknown'))
 
# demo4: 最后的fallback
r = dict()
(monad.Option(r.get('type', None)) # 这次r是空字典，get到的是Option(None)，即Empty
 .or_call(from_mimetype, r) # 没有mimetype信息，返回的是None，仍然Empty
 .or_call(from_extension, r)  # 同上，仍然Emtpy
 .map(operator.methodcaller('upper')) # Empty对象跳过map映射
 .get_or('unknown')) # 取到fallback值

TCO(Tail Call Optimization, 尾递归优化)

对很多问题来说，递归是一种很直观/顺手的写法，描述能力强，不费脑细胞。
然而，递归由于需要额外的函数调用开销，性能一般比循环的写法差一些；而且函数栈的尝试是有限的，超过之后就会报错。
在某些语言中，内置了尾调用优化（建议读一读）的特性：当最后一个语句是纯粹的递归调用时，栈深度不变，只改动参数表，性能上相当于goto语句。
Python并非经典的函数式语言，并没有内置TCO机制；但是可以用fn.py来近似。

准备工作

!pip install memory_profiler
%load_ext memory_profiler
import sys
sys.getrecursionlimit() # 1000, 下面的python原生写法中，如果超过这个深度会报错

用经典的递归写法实现fibonacci，测时间&内存开销

%%time
def factorial_normal_recurive(n): # 最直观的写法， f(n) = f(n-1) * n
    if n==1:
        return 1
    else:
        return factorial_normal_recurive(n-1) * n

%memit factorial_normal_recurive(900)
# peak memory: 38.27 MiB, increment: 0.86 MiB
# CPU times: user 46 ms, sys: 56.5 ms, total: 103 ms
# Wall time: 242 ms

写成尾递归，执行时间快一点

%%time
def factorial_tail_recursive(n, acc=1): # 尾递归，把子递归的结果直接返回； f(n,acc) = f(n-1, acc*n)
    if n==1:
        return acc
    else:
        return factorial_tail_recursive(n-1, acc*n)
%memit factorial_tail_recursive(900)
# peak memory: 39.48 MiB, increment: 1.18 MiB
# CPU times: user 41.6 ms, sys: 30.4 ms, total: 72 ms
# Wall time: 208 ms

开启fn.py的TCO，调用栈深度可以超过解释器的限制；而且会被翻译成循环/goto调用，性能也更好（这个没测）

# 为了方便TCO, 原先函数的返回语句要写成以下3种格式之一：
# (False, result) means that we finished
# (True, args, kwargs) means that we need to call function again with other arguments
# (func, args, kwargs) to switch function to be executed inside while loop # f1和f2相互递归调用时用到

%%time
from fn import recur
@recur.tco
def factorial_tco(n, acc=1): # 跟尾递归同理，但是写成了fn.py指定的格式；便于开启TCO自动优化
    if n==1:
        return False, acc
    else:
        return True, (n-1, acc*n)
%memit factorial_tco(90000) # 注意，这里的尾调用已经被优化成了循环，所以可以加大深度超过解释器的限制
# 性能不用看，这次测试的是90000，比上面几次实验大多了
# peak memory: 44.66 MiB, increment: 5.17 MiB
# CPU times: user 3.11 s, sys: 36.4 ms, total: 3.15 s
# Wall time: 3.3 s

Immutable容器

众所周知，python中的str是immutable的，字符串无法inplace modify，只能通过赋值指向新的地址。^[4]

strA='hello'
print(id(strA)) # 4367427544
strA+=' world'
print(id(strA)) # 4373528112
print(strA) # hello world

这种immutable的设计，正好契合了FP中“无副作用的函数”的理念。

SkewHeap / PairingHeap

基础用法

from fn.immutable import SkewHeap, PairingHeap, LinkedList, Stack, Queue, Vector, Deque

heap = SkewHeap()
for i in [9,3,5,2]:
    heap = heap.insert(i) # 注意是Immutable，不能inplace改，只能赋值改引用
list(heap) # 不指定cmp时，用的是自然排序
# [2, 3, 5, 9]

ele, remain = heap.extract()
ele, list(remain)
# (2, [3, 5, 9])

指定key/cmp

from collections import namedtuple
Student = namedtuple('Student', ['age','name'])
s1 = Student(7, 'Tora')
s2 = Student(5, 'Ponyo')
s3 = Student(6, 'Sousuke')

heap = SkewHeap(key=operator.attrgetter('age')) # 指定key
for s in [s1,s2,s3]:
    heap = heap.insert(s)
list(heap)
# [Student(age=5, name='Ponyo'),
#  Student(age=6, name='Sousuke'),
#  Student(age=7, name='Tora')]

heap = SkewHeap(cmp=X.age-X.age) # 指定cmp
for s in [s1,s2,s3]:
    heap = heap.insert(s)
list(heap)
# [Student(age=5, name='Ponyo'),
#  Student(age=6, name='Sousuke'),
#  Student(age=7, name='Tora')]

支持存储Pair的堆

ph = PairingHeap() # 支持存Pair的堆
ph = ph.insert((15,'a'))
ph = ph.insert((12,'b'))
ph = ph.insert((13,'c'))
list(ph)
# [(12, 'b'), (13, 'c'), (15, 'a')]

Else

除了堆以外，还对常见的各种数据结构进行了Immutable封装；不多说了，详见官网文档

来几枚大栗子

朕累了，写不动了；以后遇到合适的例子就补到这里。

tired_meow.jpeg

More

感兴趣的同学可以自己探索以下资源

• 一个轻量级的FP库 Streamz
• PyFunctional文档
• 我用Jupyter Notebook写的fn.py/PyFunctionalDemo

1. 摘自StackOverflow上的一条回答 ↩

2. ES6中的lambda表达式可能会好写一点，我了解不多，欢迎感兴趣的同学评论留言 ↩

3. Monad和Optional不是一码事；前于前者可以看阮一峰的这篇文章，后者可以参考Java8 Optional来理解 ↩

4. 关于python中的可变/不可变类型，这篇文章总结得不错 ↩