WHsT

WHsT

WHsT's name is .
Twitter: @xukiro, GitHub: whst

用函数模拟数据结构 (in Py3)

Note: 为简便起见,本文中出现的部分概念被简化了。阅读本文你需要会使用 Python

常见的数据结构,诸如链表、树、图等,都由节点构成。以最简单的链表为例,在 C/C++ 中需要定义类似这样的结构:

1
2
3
4
struct Node {
T data;
Node *next;
};

由于习惯,很多人可能会潜移默化地认为实现链表必须依赖 class/struct 这样的定义。事实上,在函数是 first-class citizen 的语言中,我们完全可以只使用函数来实现这样的结构。不仅如此,甚至可以只使用函数为节点提供「面向对象」风格的操作。

不少语言可以实现这一点。函数式语言自然不用说,这里我们用 Python3 来实现和 Lisp 中类似的表结构。

由于 Python 更多是以 OOP 的方式出现在我们眼前,充分挖掘它的函数式特性也许会颇为 exotic 吧 ;-P


0. Lisp 中表的结构

先科普一下 Lisp 中的表是怎么构成的。
在 Lisp 中,cons 函数用于产生一个 pair(类似 Python 的二元组),car 和 cdr 函数分别 用来取出数对的第一和第二个成员。用 Python 语法表示就类似这样:

1
2
3
p = cons(x, y) # 构造节点 (x, y) 命名为 p
car(p) # 返回 x
cdr(p) # 返回 y

Lisp 就是用这种「二元组」当成链表的节点来用的,例如表 (1 2 3) 可以这样构成:cons(1, cons(2, (cons(3, None)))
它在内存中就像这样:

(1, *)-> (2, *)-> (3, *)-> None

由于 Lisp 不是纯函数式语言,因此它允许状态的存在,也就是说允许对变量赋值。set-car 函数和 set-cdr 函数分别用来设置一个节点的两个部分指向什么。例如:

1
2
3
p = cons(3, 8) # p is (3, 8)
set_car(p, 4) # p becomes (4, 8)
set_cdr(p, 9) # p becomes (4, 9)

1. 定义 cons 函数!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def cons(x, y):
def set_x(v):
nonlocal x
x = v
def set_y(v):
nonlocal y
y = v

def dispatch(m):
if m == 'car':
return x
if m == 'cdr':
return y
if m == 'set_car':
return set_x
if m == 'set_cdr':
return set_y
raise ValueError("Undefined operation: CONS: " + str(m))

return dispath

在这个实现中,cons 接受两个参数,返回 dispatch 函数。在这种定义之下,假如我们有 n = cons(x, y),现在 n 实际上是一个函数,那如何把 n 当成一个对象使用呢?

首先我们来看怎么得到传给 cons 的两个参数。dispatch 在接受到 ‘car’ 时返回 x,接受到 ‘cdr’ 时返回 y. 换句话说可以把 n('car') 理解成 OOP 常见的形式 n.get_car(),cdr 类似。

而设置成员值稍稍有些不同,dispatch 函数在接收到 ‘set_car’ / ‘set_cdr’ 的时候返回两个函数。我们以 set_x 为例研究:它其实就是一个函数,把参数 v 的值赋给 x 和 y. 但是注意 Python 有个特性:在函数中赋值相默认等同于建立了新的局部变量。因此需要用 nonlocal x 告诉解释器,我们是要改变外层变量 x 的值,而不是建立局部变量 x。不知读者是否注意到了 n('set_car')(val) 很像 OOP 中的 n.set_car(val)

2. 添加一些辅助函数!

首先定义几个对于类型判断的小函数。

1
2
3
4
5
6
def is_null(z):
return z == None
def is_number(z):
return isinstance(z, (int, long, float, complex))
def is_atom(z):
return is_number(z) or isinstance(z, string)

is_null 判断参数是否是 None(等同于 Lisp 中的空表), is_number 判断参数是否是数,包括整数、长整数、浮点数、复数。
is_atom 判断参数是否是「原子」。在 Lisp 中,除用 cons 构成的 pair 和空表以外的数据都算原子。这里我们假设所有用到的数据类型只有数、字符串、None、cons 组成的 pair。

另外,虽然上面的「OOP 风格函数」确实工作得很好,Lisp 里却很少采用这种风格。我们还是入乡随俗地将 car 等操作定义成普通函数:

1
2
3
4
5
6
7
8
def car(z):
return z('car')
def cdr(z):
return z('cdr')
def set_car(z, new_value):
z('set_car')(new_value)
def set_cdr(z, new_value):
z('set_cdr')(new_value)

再定义一个生成参数为闭区间内整数的 range 函数。尽管 Python 允许以自定义函数覆盖默认函数,这里我们还是避免这种做法——给列表有关的操作都加上 list 前缀:

1
2
3
4
def list_range(a, b):
if a > b:
return None
return cons(a, list_range(a + 1, b))

以及一个把表转换成可打印字符串的函数:

1
2
3
4
def list_to_str(l):
if is_null(l):
return ''
return str(car(l)) + ' ' + list_to_str(cdr(l))

3. 休息一下 测试一番~

有了上面这些代码,我们测试一下构建的链表:

1
2
3
4
Python 3.6.0 (default, Mar  4 2017, 12:32:34) ...
>>> from lisp import *
>>> print(list_to_str(list_range(1, 10)))
1 2 3 4 5 6 7 8 9 10

Hooray! It works!

4. 折叠、映射与过滤

fold、map、filter 是函数式语言中对可迭代对象的常见的操作,让我们来实现它们。

如果你不清楚什么是 fold 或者 reduce,请查阅资料自行了解这个概念。基本上 Python 的 reduce 函数就相当于左折叠,即 reduce(f, xs, v) <====> fold_l(f, v, xs)

由于单链表取头节点很方便,右折叠(fold-right)是最容易实现的:

1
2
3
4
def fold_r(f, zero, xs):
if is_null(xs):
return zero
return f(car(xs), fold_r(f, zero, cdr(xs)))

利用右折叠我们已经可以实现 map 和 filter:

1
2
3
4
5
6
7
8
def list_map(proc, xs):
f = lambda x, acc: cons(proc(x), acc)
return fold_r(f, None, xs)

def list_filter(pred, xs):
def step(x, acc):
return cons(x, acc) if pred(x) else acc
return fold_r(step, None, xs)

左折叠(fold-left)可以直接用右折叠实现,这种实现方法看上去奇技淫巧:

1
2
3
4
5
def fold_l(f, zero, xs):
def step(x, g):
return lambda a: g(f(a, x))
identity = lambda x: x
return fold_r(step, identity, xs)(zero)

至于这个巧妙的构造的原理,暂时留给读者思考(如果有时间就更新在博客上给出解释)。

有了 fold,我们可以用一种更简洁的方式实现 list_to_str

1
2
def list_to_str(xs):
return fold_r(lambda x, acc: str(x) + ' ' + acc, '', xs)

5. 大功告成

测试一下我们写的这几个函数吧:

1
2
3
4
5
6
7
8
9
10
11
12
>>> from lisp import *
>>> xs = list_range(1, 10) # xs = 1,2,3,…,10
>>> list_to_str(list_map(lambda x: x*x, xs)) # 平方数
'1 4 9 16 25 36 49 64 81 100 '
>>> list_to_str(list_filter(lambda x: x%2, xs)) # 奇数
'1 3 5 7 9 '
>>> sub = lambda x, y: x - y
>>> ys = list_range(1, 3) # ys = 1,2,3
>>> fold_l(sub, 0, ys) # (((0 - 1) - 2) - 3)
-6
>>> fold_r(sub, 0, ys) # (1 - (2 - (3 - 0)))
2

不过有必要说明的是,这种实现只是为了显示「函数的威力」,这里的威力是逻辑上的威力。实际生产环境中当然不可能用这样低效率的代码了。

这里贴上完整代码片段:

1
2
3
4
5
6
7
8
9
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#! /usr/bin/env python3

def cons(x, y):
def set_x(v):
nonlocal x
x = v
def set_y(v):
nonlocal y
y = v

def dispatch(m):
if m == 'car':
return x
if m == 'cdr':
return y
if m == 'set_car':
return set_x
if m == 'set_cdr':
return set_y
raise ValueError("Undefined operation: CONS: " + str(m))

return dispatch

def car(z):
return z('car')
def cdr(z):
return z('cdr')
def set_car(z, new_value):
z('set_car')(new_value)
def set_cdr(z, new_value):
z('set_cdr')(new_value)

def is_null(z):
return z == None
def is_number(z):
return isinstance(z, (int, long, float, complex))
def is_atom(z):
return is_number(z) or isinstance(z, string)

def list_range(a, b):
if a > b:
return None
return cons(a, list_range(a + 1, b))

def list_to_str(l):
if is_null(l):
return ''
return str(car(l)) + ' ' + list_to_str(cdr(l))

# 1:2:3:[] --> f(1, f(2, f(3, zero)))
def fold_r(f, zero, xs):
if is_null(xs):
return zero
return f(car(xs), fold_r(f, zero, cdr(xs)))

def fold_l(f, zero, xs):
def step(x, g):
return lambda a: g(f(a, x))
identity = lambda x: x
return fold_r(step, identity, xs)(zero)

def list_map(proc, xs):
f = lambda x, acc: cons(proc(x), acc)
return fold_r(f, None, xs)

def list_filter(pred, xs):
def step(x, acc):
return cons(x, acc) if pred(x) else acc
return fold_r(step, None, xs)

def list_to_str(xs):
return fold_r(lambda x, acc: str(x) + ' ' + acc, '', xs)


if __name__ == '__main__':
xs = list_range(1, 10)
print(list_to_str(list_map(lambda x: x*x, xs))) # Squares
print(list_to_str(list_filter(lambda x: x%2, xs))) # Odd numbers
sub = lambda x,y: x-y
ys = list_range(1, 3)
print(fold_l(sub, 0, ys)) # (((0 - 1) - 2) - 3)
print(fold_r(sub, 0, ys)) # (1 - (2 - (3 - 0)))

前面我们的代码为了易于读懂,尽量避免了匿名函数的使用。如果我们全部用匿名函数 + 手动 currying,可以看起来更怪异一点(不过没有 set_car 和 set_cdr,貌似 Python 的匿名函数里无法实现赋值):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#!/usr/bin/env python3

cons = lambda x: lambda y: lambda isCar: x if isCar else y
car = lambda node: node(True)
cdr = lambda node: node(False)

null = lambda obj: obj == None
number = lambda obj: isinstance(obj, (int, float, complex))

id = lambda x: x

foldr = lambda f: lambda zero: lambda xs:\
zero if null(xs) else f (car(xs)) (foldr (f) (zero) (cdr(xs)))
foldl = lambda f: lambda zero: lambda xs:\
foldr (lambda x: lambda g: lambda a: g (f(a)(x))) (id) (xs) (zero)

display = lambda xs: print() if null(xs) else\
(print(car(xs), end = ' '), display(cdr(xs)))

map = lambda proc: lambda xs:\
foldr (lambda x: lambda ac: cons(proc(x))(ac)) (None) (xs)
filter = lambda pred: lambda xs:\
foldr (lambda x: lambda ac:\
cons(x)(ac) if pred(x) else ac) (None) (xs)

range = lambda a: lambda b: None if a > b else cons(a)(range(a + 1)(b))


说句题外话,Python 确实是一门挺好玩的语言。有很多有趣的 feature,可惜语法有些丑。也难怪有人说 Python 是一种实现得不太好的 Lisp。