Python 开发指南:函数式编程(递归、lambda 表达式、柯里化与闭包)
函数式编程的思想非常适合编写无状态的流数据处理系统。
递归
像广义的链表,树都可以认为是递归定义的,使用递归逻辑来处理递归数据类型再合适不过了。除此之外,一些回溯问题,动态规划问题也非常适合用递归去解决。这里举一个简单的例子:我们仅需要简短几句就能描述出快速排序的逻辑。
# 每一轮迭代只关注三个部分: 比seq[mid]更小的数,和seq[mid]相等的数,比seq[mid]更大的数。
def quicksort(seq: list) -> list:
if len(seq) seq[mid]:
r.append(i)
else:
m.append(i)
return quicksort(l) + m + quicksort(r)
递归的核心思想是将看似复杂的问题分解成重复子问题的组合。同时,临界条件已经暗示了程序将在何时退出结束,因此也就不再需要信号量,break
,continue
这样的机制了。
如果递归返回的要么是一个简单值,要么是对自身的递归调用而没有其它动作,则它可被称之尾递归。当前的 quicksort
实现并不是尾递归,因为它在返回时还进行了列表组合。理论上,尾递归函数只需要一个栈帧,因此不会出现栈溢出的问题。所有的尾递归都可以被解析为等价的 while 或者 for 循环,这部分研究可被称之尾递归优化。
所有 非尾递归函数 理论上都存在栈溢出的风险,这是相比于 for, while 这种命令式迭代的一个明显缺陷,但递归胜在更加简洁的表述。
lambda 表达式
在 Python 中,函数标识符可以被认为是 表达式,表达式就像变量那样可以在程序的任意一处传递。比如:
def f(): print("method")
invokable = f
print(callable(invokable)) # True
invokable()
而对于一些 简单表达式,通常使用 lambda 表达式声明,使用 lambda:
关键字。如:
f1 = lambda: print("hello") # 不接受参数的 lambda 表达式
f2 = lambda x, y: print(f"x={x}, y={y}") # 接受参数的 lambda 表达式
f3 = lambda x, y: x + y # 具备返回值的 lambda 表达式
简单表达式自身的运算结果即返回值 ( 没有则认为返回 None
),因此不需要显式声明 return
关键字。
函数式转换子
除了前文的列表推导式之外,list -> list
的映射还存在另外一种编写风格。这里主要介绍常用的五种转换子:map
,reduce
,set
,filter
,zip
。
map()
和 filter()
是基础且常用的算子,运算将分别产生 map 和 filter 对象,它们本质上是一次性消费数据的迭代器,需要额外转换为列表。前者用于列表映射,后者用于列表元素过滤。比如:
list = [1,2,3,4,5]
xs = map(lambda x: x + 1,list)
print(*xs) # 2, 3, 4, 5, 6
xxs = list(xs) # 转换为 list
print(xxs)
ys= filter(lambda x: x > 1,list)
print(*ys) # 2, 3, 4, 5
yys = list(ys) # 转换为 list
print(yys)
zip()
,故名思意,能够按序将两个列表的元素缝合为二元组,并产生一个 zip 对象,需要额外转换为列表,理由同上。若缝合的两个列表长度不一致,较长列表的后面元素会被丢弃。
key = ["c", "j", "g", "p"]
value = ["c++", "java", "golang"]
kws = zip(key,value)
print(*kws) # ('c', 'c++') ('j', 'java') ('g', 'golang')
xs = list(kws) # 转换为 list
print(xs) # [('c', 'c++') ('j', 'java') ('g', 'golang')]
归并算子 reduce()
需要从 functools
库中引入。如果我们操作的是 可折叠数据结构 ( 比如将类型记作 A
,B
,而我们定义了 [A] + [A] = [B]
的法则 ),那么使用 reduce()
算子可以快速实现规约 ( 用 SQL 的话说是聚合函数 )。事实上,前文提到的 sum()
,max()
,min()
都可以认为是归并算子的特例。
class Foo:
def __init__(self, v_):
self.v = v_
from functools import reduce
xs = [Foo(1), Foo(2), Foo(3)]
merge = lambda foo1, foo2: Foo(foo1.v + foo2.v)
fooN = reduce(merge, xs)
print(fooN.v)
set()
算子用于去除列表中重复的元素,或者将该方法理解成是列表向集合的强制转换函数。放入的元素必须是 hashable type,见前文的集合。
class Foo:
def __init__(self,v_):
self.v = v_
def __hash__(self): return hash(self.v,)
def __eq__(self, other): return self.v == other.v
xs = [2,2,3,4,5,Foo(1),Foo(1)]
x = set(xs)
print(x)
柯里化与闭包
柯里化是记忆参数以及推迟函数执行的重要手段。它的核心思路是使用嵌套闭包构建一个高阶函数。比如:
def telnet(host):
def _port(port):
print(f"connect to {host}:{port}")
return _port
# telnet("192.168.229.140")(6379)
server = telnet("192.168.229.140")
server(6379)
假定 telnet
是用于服务器连接的函数,当程序需要连接同一个机器的不同端口时,函数柯里化可以实现复用配置路径 ( 或称复用输入参数 ) 的效果:
master = telnet("192.168.229.140")
master(6379) # host = 192.168.229.140, port = 6379
master(8080) # host = 192.168.229.140, port = 6379
follower = telnet("192.168.229.141")
follower(6379) # host = 192.168.229.141, port = 6379
follower(8080) # host = 192.168.229.141, port = 6379
通过嵌套闭包定义的方式实现柯里化很麻烦,并且参数确认的顺序是固定的。python 提供了函数柯里化的更简单方式,这需要引入 functools.partial()
函数将严格求值的函数变为 thunk。
def telnet(host, port): print(f"connect to {host}:{port}")
# 第一个参数填写的是函数标识名,表示传递函数本身。
# partial(telnet, host="192.168.229.150")(port=6379)
leader = partial(telnet, host="192.168.229.150")
leader(port=6379)
在这个例子中,telnet()
是一个普通的函数,而 partial()
函数将允许以任意次序对其进行柯里化。额外地,这里的参数需要以 **kwargs
的形式进行指定。
函数组合
给定两个函数 f
和 g
,它们有两种基本的组合方式:
compose(f,g)
,等价于 f(g())
,其中 g
的返回值作为 f
的入参。andThen(f,g)
,等价于 g(f())
,其中 f
的返回值作为 g
的入参。其命名借鉴于 Java/Scala 的函数式接口,法则 compose(f,g) == andThen(g,f)
总是成立。它们在 Python 中可以如下定义:
def compose(f, g):
def closure(*args, **kwargs): return f(g(*args, **kwargs))
return closure
def andThen(f, g):
def closure(*args, **kwargs): return g(f(*args, **kwargs))
return closure
f = compose(lambda t: t[0] + t[1], lambda x, y: (x + 1, y + 1))
print(f(2, 3)) # 7
g = andThen(lambda x, y: (x + 1, y + 1), lambda t: t[0] + t[1])
print(g(2,3))
这种思想常用于 map
算子融合,来自 1989 年 Philip Wadler 的论文《 Theorems for free 》,名为免费定理,论文可以去参考 free.dvi (ttic.edu)。比如:
lambda_1 = lambda x: x + 1
lambda_2 = lambda x: x * 2
xs = [1, 2, 3, 4, 5]
y1s = map(lambda_2, map(lambda_1, xs)) # 先执行 λ1,再执行 λ2,列表转换了两次,额外生成了一个保存中间结果的列表。
y2s = map(andThen(lambda_1,lambda_2),xs) # 先组合 andThen(λ1, λ2),再一次性进行转换,不需要保存中间结果。
print(*y1s)
print(*y2s)
作者:花花子
来源:稀土掘金