我们在惰性求值中,我们介绍了「惰性列表」的概念,这个概念,其实在Python种也有部分原生支持。这就是很受新手困扰的生成器迭代器了。但之前,我们首先要回顾一下关于列表的功能。

从二元元组到列表

首先,我们可以用\(\lambda\)演算定义一个二元的元组,或者叫pair:

  1. pair: \(\lambda a b f.f a b\)
  2. first: \(\lambda p. p(\lambda a b. a)\)
  3. second: \(\lambda p. p(\lambda a b.b)\)

具体实现如下:

pair = lambda a: lambda b: lambda f: f(a)(b)
first = lambda p: p(lambda a: lambda b: a)
second = lambda p: p(lambda a: lambda b: b)

我们可以定义测试一下:

>>> p = pair(1)(2)
>>> first(p)
1
>>> second(p)
2

当然有了pair,定义一个列表就不是难事,即下面的方式组合就好(我们还是用python自带的元组表示):

(1, (2, 3, (4, ()))))

我们将在后面的章节里分别用元组/类型的方式来定义列表。但在这篇文章里,我们先回到之前python的自带的概念来,看函数式编程如何处理遍历问题的。

列表操作

列表操作,是函数式编程的一个重要概念,实时上它是通过递归来实现对一个线性结果的遍历。比如下面的类C风格的代码:

ls = [1, 2, 3, 4]

for i in range(0, len(ls)):
    ls[i] = ls[i] + 1

这里出现了两个副作用,一个是i的自增,另一个是对ls的原地操作。而且,它们也用到了变量的概念。当然,这种写法其实无可厚非,可维护性也尚可,算是可以容忍的副作用。当然我们最简单的实现,相当于大家都知道是列表表达式(当然,事实上它还是有副作用的):

[i + 1 for i in ls]

当然,大部分人也见过列表表达式的完整操作,可以自带筛选:

[i + 1 for in in ls if i % 2 == 0]

这就是函数式编程遍历数据最简单的操作,当然,它们还有一个名字,就是mapfilter,在Python中,它们返回的就是可迭代对象(我们可以调用list转换成列表):

map(lambda x: x + 1, ls) # [i + 1 for i in ls]
filter(lambda x: x % 2 == 0, ls) # [i for i in ls if x % 2 == 0]

另一个常用的列表操作是reduce,它起到的是聚合作用,我们只要定义一个二元运算,就可以将列表从头合并到尾聚合操作。

reduce操作视图解决的问题就是遍历后汇总值的过程。譬如,我们要实现ls的求和,在一般的过程式编程中,我们会使用如下的方法:

res = 0

for i in ls:
    res += i # 或者和下面更类似的写法 res = res + i

而,使用reduce,我们仅需要如下代码即可完成。

from functools import reduce

reduce(lambda x: x + y, ls)

具体的计算过程如下:

  1. 获取ls第一个值1和第二个值2,套用lambda x, y: x + y,得到3
  2. 获取ls第三个值3,套用第一步的结果3lambda得到6
  3. 获取ls第三个值4,套用第二步的结果6lambda得到10
  4. 完成计算返回结果。

但,其实如果查看Pythonreduce函数的参数,我们会发现它还可以带入初始值,当带入初始值时,在各类函数式语句中,一般把它叫做fold_left/foldl函数。这个有没有初始值效果会不一样很多。第一个就是处理列表是空的问题:

reduce(lambda x, y: x + y, []) # 报错
reduce(lambda x, y: x + y, [], 0) # return 0

我们甚至可以把这个和前面的过程式编程的各种元素对应起来,0相当于res = 0lambda x, y: x + y表达的就是res = res + i。但是,其实foldlreduce更强大的层面,在于,这个运算本身可以涉及不同类型。我们采用类型标志,就会发现reduce函数本身的运算只能是Callable[[S, S], S]/(S, S) -> S,但其实我们在很多场景中,需要的是一个类型装换。比如:

  1. [1, 2, 3, 4] => "1234"
  2. [1, 2, 3, 4] => [[1], [2], [3], [4]]

如果单纯使用reduce我们无法操作这种涉及类型转换的内容,foldl带入的二元运算类型标注则是Callable[[S, T], S]/(S, T) -> S。这就让我们可以通过设定一个另一个类型的初始值,来实现这件事,比如上面转换成字符串的例子,我们很容易找到下面的二元运算(注意前后顺序):

lambda x, y: x + str(y)

而初始值仅需设定一个空的""字符串即可,即如下实现(尝试自己实现一下[1, 2, 3, 4] => [[1], [2], [3], [4]]吧!):

reduce(lambda x, y: x + str(y), ls, "")

总结

本篇文章中,我们回顾了Python原生的列表,以及介绍函数式编程通过列表表达式/列表操作来实现过程式中常见的数据遍历的问题来规避for/while中不可避免的副作用。我们接下来将会使用pair的概念从头实现一个列表,然后我们就进入到正式的惰性列表的概念中,看看惰性列表如何处理这类问题,以及用函数式思考流式处理、线程的概念。