2.3 序列
序列（sequence）是有序的值的集合。序列是计算机科学中一种强大且基础的抽象。序列并非特定内置类型或抽象数据表示的实例，而是多种不同数据类型所共享的一组行为集合。也就是说，序列有很多种，但它们都拥有共同的行为。特别是：
- 长度（Length）：序列的长度是有限的，空序列的长度为 0
- 元素选择（Element selection）：序列拥有与每一个小于其长度的非负整数索引相对应的元素，索引从 0 开始表示第一个元素
Python 包含多种属于序列的原生数据类型，其中最重要的是列表(list)。
2.3.1 列表
列表值是一种长度任意的序列。列表拥有大量的内置行为，以及表达这些行为的特定语法。我们已经见过列表字面量（求值为 list 实例），以及元素选择表达式（求值为列表中的某个值）。内置的 len 函数返回序列的长度。在下例中，digits 是一个包含四个元素的列表。索引 3 处的元素是 8。
>>> digits = [1, 8, 2, 8]
>>> len(digits)
4
>>> digits[3]
8此外，列表可以相加，也可以乘以整数。对于序列而言，加法和乘法并非对元素进行相加或相乘，而是对序列本身进行组合与复制。也就是说，operator 模块中的 add 函数（以及 + 运算符）产生一个由被加参数拼接而成的新列表。operator 中的 mul 函数（以及 * 运算符）接收一个列表和一个整数 k，返回一个由原列表重复 k 次构成的新列表。
>>> [2, 7] + digits * 2
[2, 7, 1, 8, 2, 8, 1, 8, 2, 8]列表中可以包含任何值，包括另一个列表。为了选中包含在列表中的列表里的深层嵌套元素，可以多次应用元素选择操作。
>>> pairs = [[10, 20], [30, 40]]
>>> pairs[1]
[30, 40]
>>> pairs[1][0]
302.3.2 序列遍历
在许多情况下，我们希望遍历序列的元素，并依次对每个元素执行某些计算。这种模式非常常见，以至于 Python 提供了一个额外的控制语句来处理序列数据：for 语句。
考虑计算某个值在序列中出现次数的问题。我们可以使用 while 循环来实现一个计算该次数的函数。
>>> def count(s, value):
"""统计 value 在序列 s 中出现的次数。"""
total, index = 0, 0
while index < len(s):
if s[index] == value:
total = total + 1
index = index + 1
return total
>>> count(digits, 8)
2Python 的 for 语句可以通过直接遍历元素值来简化这个函数体，完全无需引入 index 这个名称。
>>> def count(s, value):
"""统计在序列 s 中出现了多少次值为 value 的元素"""
total = 0
for elem in s:
if elem == value:
total = total + 1
return total
>>> count(digits, 8)
2for 语句由一个形式如下的单子句组成：
for <name> in <expression>:
<suite>for 语句的执行过程如下：
- 求值头部 (header) 的
<expression>，它必须产生一个可迭代 (iterable) 值 - 对该可迭代值中的每个元素，按顺序执行：
- 在当前帧中将
<name>绑定到该值 - 执行语句组
<suite>
- 在当前帧中将
这个执行过程提到了可迭代值。列表是一种序列，而序列是可迭代值。它们的元素按顺序被处理。Python 还包含其他可迭代类型，但我们目前将重点放在序列上；“可迭代”一词的通用定义出现在第 4 章关于迭代器的部分。 这个求值过程的一个重要推论是：在 for 语句执行完毕后，<name> 将被绑定到序列的最后一个元素上。for 循环引入了另一种语句可以更新环境的方式。
序列解包 (Sequence unpacking)。 程序中一种常见的模式是使用一个元素本身也是序列的序列，且所有内部序列的长度固定。for 语句的头部可以包含多个名称，以便将每个元素序列“解包”到各自的元素中。例如，我们可能有一个由双元素列表组成的列表：
>>> pairs = [[1, 2], [2, 2], [2, 3], [4, 4]]并希望找出其中第一个元素和第二个元素相同的“对”的数量。
>>> same_count = 0下面的 for 语句头部有两个名称，它们将分别绑定到每个“对”中的第一个和第二个元素上。
>>> same_count = 0
>>> for x, y in pairs:
if x == y:
same_count = same_count + 1
>>> same_count
2这种将定长序列中的多个值绑定到多个名称的模式称为序列解包；这与我们在将多个值绑定到多个名称的赋值语句中看到的模式相同。
范围（Ranges）：range 是 Python 中另一种内置的序列类型，用于表示整数范围。范围使用 range 创建，它接受两个整数参数：起始数字和目标范围结束数字的后一位。
>>> range(1, 10) # [1, 10)，包括 1，但不包括 10
range(1, 10)对范围调用 list 构造函数会求值得到一个包含该范围所有元素的列表，以便于查看元素。
>>> list(range(5, 8))
[5, 6, 7]如果只给出一个参数，它会被解释为从 0 开始的范围的结束值（后一位）。
>>> list(range(4))
[0, 1, 2, 3]范围常用于 for 头部表达式，以指定语句组应执行的次数。如果 for 头部中的名称在语句组中未被使用，惯例是使用单个下划线字符作为名称：
>>> for _ in range(3):
print('Go Bears!')
Go Bears!
Go Bears!
Go Bears!对解释器而言，这个下划线只是环境中的另一个名称，但在程序员之间，它具有约定俗成的含义，表示该名称不会出现在未来的任何表达式中。
2.3.3 序列处理
序列是如此常见的一种复合数据形式，以至于整个程序通常都围绕着这一单一抽象来组织。将序列作为输入和输出的模块化组件，可以混合搭配以执行数据处理。通过将一系列简单且专注的序列处理操作链接在一起，可以定义复杂的组件。
列表推导式（List Comprehensions）：许多序列处理操作可以表示为：对序列中的每个元素求值一个固定表达式，并将结果值收集到一个结果序列中。在 Python 中，列表推导式就是执行此类计算的表达式。
>>> odds = [1, 3, 5, 7, 9]
>>> [x+1 for x in odds]
[2, 4, 6, 8, 10]上面的 for 关键字并非 for 语句的一部分，而是列表推导式的一部分，因为它被包含在方括号内。子表达式 x+1 会在 x 依次绑定到 odds 的每个元素时被求值，结果值被收集到一个列表中。
另一种常见的序列处理操作是选择满足某些条件的值的子集。列表推导式也可以表达这种模式，例如选择 odds 中所有能整除 25 的元素。
>>> [x for x in odds if 25 % x == 0]
[1, 5]列表推导式的一般形式是：
[<映射表达式> for <名称> in <序列表达式> if <过滤表达式>]要计算列表推导式，Python 首先求值 <序列表达式>，它必须返回一个可迭代值。然后，按顺序对每个元素进行处理：将元素值绑定到 <名称>，求值过滤表达式，如果结果为真，则求值映射表达式。映射表达式的值被收集到一个列表中。
聚合（Aggregation）：序列处理中的第三种常见模式是将序列中的所有值聚合为单个值。内置函数 sum、min 和 max 都是聚合函数的例子。
通过组合“对每个元素求值表达式”、“选择元素子集”和“聚合元素”这几种模式，我们可以使用序列处理方法来解决问题。
完全数 (Perfect Number) 是一个正整数，它等于其所有因子（不包括自身）之和。n 的因子是指小于 n 且能整除 n 的正整数。列出 n 的因子可以用列表推导式表示。
>>> def divisors(n):
return [1] + [x for x in range(2, n) if n % x == 0]
>>> divisors(4)
[1, 2]
>>> divisors(12)
[1, 2, 3, 4, 6]利用 divisors，我们可以用另一个列表推导式计算 1 到 1000 之间的所有完全数。（通常认为 1 也是完全数，尽管它不符合我们要排除自身的 divisors 定义。）
>>> [n for n in range(1, 1000) if sum(divisors(n)) == n]
[1, 6, 28, 496]我们可以重用 divisors 的定义来解决另一个问题：给定面积，求具有整数边长的矩形的最小周长。矩形的面积是高乘以宽。因此，给定面积和高，我们可以计算宽。我们可以断言宽和高都能整除面积，以确保边长是整数。
>>> def width(area, height):
assert area % height == 0
return area // height矩形的周长是其边长之和。
>>> def perimeter(width, height):
return 2 * width + 2 * height具有整数边长的矩形，其高度必须是面积的因子。我们可以通过考虑所有可能的高度来计算最小周长。
>>> def minimum_perimeter(area):
heights = divisors(area)
perimeters = [perimeter(width(area, h), h) for h in heights]
return min(perimeters)
>>> area = 80
>>> width(area, 5)
16
>>> perimeter(16, 5)
42
>>> perimeter(10, 8)
36
>>> minimum_perimeter(area)
36
>>> [minimum_perimeter(n) for n in range(1, 10)]
[4, 6, 8, 8, 12, 10, 16, 12, 12]高阶函数：我们在序列处理中观察到的常见模式可以使用高阶函数来表达。首先，对序列中每个元素求值一个表达式，可以表示为将一个函数应用到每个元素上。
>>> def apply_to_all(map_fn, s):
return [map_fn(x) for x in s]仅选择某些表达式为真的元素，可以表示为对每个元素应用一个函数进行过滤。
>>> def keep_if(filter_fn, s):
return [x for x in s if filter_fn(x)]最后，许多形式的聚合可以表示为：将一个双参数函数重复应用到目前的归约 (reduced) 值和下一个元素上。
>>> def reduce(reduce_fn, s, initial):
reduced = initial
for x in s:
reduced = reduce_fn(reduced, x)
return reduced例如，reduce 可以用来将序列中的所有元素相乘。使用 mul 作为 reduce_fn 并使用 1 作为 initial 值，reduce 可以用来计算数字序列的乘积。
>>> reduce(mul, [2, 4, 8], 1)
64我们同样可以使用这些高阶函数来寻找完全数。
>>> def divisors_of(n):
divides_n = lambda x: n % x == 0
return [1] + keep_if(divides_n, range(2, n))
>>> divisors_of(12)
[1, 2, 3, 4, 6]
>>> from operator import add
>>> def sum_of_divisors(n):
return reduce(add, divisors_of(n), 0)
>>> def perfect(n):
return sum_of_divisors(n) == n
>>> keep_if(perfect, range(1, 1000))
[1, 6, 28, 496]惯用名称（Conventional Names）：在计算机科学中，apply_to_all 更常用的名称是 map（映射），而 keep_if 更常用的名称是 filter（过滤）。Python 中内置的 map 和 filter 是这些函数的泛化版本，它们并不直接返回列表（而是返回迭代器）。这些函数将在第 4 章讨论。上面的定义等同于将 list 构造函数应用于内置 map 和 filter 调用的结果。
>>> apply_to_all = lambda map_fn, s: list(map(map_fn, s))
>>> keep_if = lambda filter_fn, s: list(filter(filter_fn, s))reduce 函数内置于 Python 标准库的 functools 模块中。在这个版本中，initial 参数是可选的。
>>> from functools import reduce
>>> from operator import mul
>>> def product(s):
return reduce(mul, s)
>>> product([1, 2, 3, 4, 5])
120在 Python 程序中，直接使用列表推导式比使用高阶函数更为常见，但这两种序列处理方法都被广泛使用。
2.3.4 序列抽象
我们已经介绍了两种满足序列抽象的原生数据类型：列表（list）和范围（range）。这两个类型都满足我们在本节开头提出的条件：长度和元素选择。Python 还包含另外两种扩展了序列抽象的序列类型行为。 成员资格（Membership）：我们可以测试某个值是否属于序列的成员。Python 有两个运算符 in 和 not in，它们根据元素是否出现在序列中来求值为 True 或 False。
>>> digits
[1, 8, 2, 8]
>>> 2 in digits
True
>>> 1828 not in digits
True切片（Slicing）：序列内部包含更小的序列。序列的切片是原序列中任意一段连续的片段，由一对整数指定。与 range 构造函数一样，第一个整数表示切片的起始索引，第二个整数表示结束索引的后一位。
在 Python 中，序列切片的表达方式与元素选择类似，也是使用方括号。冒号用于分隔起始和结束索引。省略任意一个边界，都默认取极值：省略起始索引默认为 0，省略结束索引默认为序列的长度。
>>> digits[0:2]
[1, 8]
>>> digits[1:]
[8, 2, 8]列举 Python 序列抽象的这些额外行为，让我们有机会反思一下：总体而言，什么才算是一个有用的数据抽象。抽象的丰富性（即包含多少行为）是有代价的。对于抽象的用户来说，额外的行为可能很有帮助。但另一方面，用一种新的数据类型来满足一个丰富抽象的所有要求可能充满挑战。丰富抽象的另一个负面影响是用户需要花更长的时间来学习。
序列之所以拥有如此丰富的抽象，是因为它们在计算中无处不在，以至于学习这少量的复杂行为是值得的。一般来说，大多数用户定义的抽象应尽可能保持简单。
拓展材料：切片符号支持多种特殊情况，例如负的起始值、结束值和步长。在线书籍《Dive Into Python 3》中名为 列表切片 的小节提供了完整的描述。在本章中，我们将仅使用上述的基本特性。
2.3.5 字符串
文本值可能比数字更是计算机科学的基础。一个恰当的例子是，Python 程序本身就是以文本形式编写和存储的。Python 中用于表示文本的原生数据类型称为字符串 (string)，对应构造函数 str。
关于如何在 Python 中表示、表达和操作字符串，有许多细节。字符串是丰富抽象的另一个例子，它要求程序员投入大量精力才能熟练掌握。本节将作为对字符串核心行为的简要介绍。
字符串字面量（string literals）可以表示任意文本，由单引号或双引号包围。
>>> 'I am string!'
'I am string!'
>>> "I've got an apostrophe"
"I've got an apostrophe"
>>> '您好'
'您好'我们在之前的代码中已经见过字符串了，比如文档字符串（docstrings）、print 调用中的文本，以及 assert 语句中的错误消息。
字符串满足我们在本节开头介绍的序列的两个基本条件：它们有长度，且支持元素选择。
>>> city = 'Berkeley'
>>> len(city)
8
>>> city[3]
'k'字符串的元素本身就是只包含单个字符的字符串。字符可以是字母表中的任何单个字母、标点符号或其他符号。与许多其他编程语言不同，Python 没有单独的字符类型；任何文本都是字符串，表示单个字符的字符串长度为 1。
像列表一样，字符串也可以通过加法和乘法进行组合。
>>> 'Berkeley' + ', CA'
'Berkeley, CA'
>>> 'Shabu ' * 2
'Shabu Shabu '成员资格：字符串的行为与其他序列类型有所不同。字符串抽象并不完全符合我们针对列表和范围描述的通用序列抽象。特别是，成员运算符 in 虽然适用于字符串，但其行为与应用于序列时截然不同：它匹配的是子串而不是元素。
>>> 'here' in "Where's Waldo?"
True多行字面量（Multiline Literals）：字符串不局限于单行。三引号可以界定跨越多行的字符串字面量。我们在文档字符串中已经广泛使用了这种三引号。
>>> """The Zen of Python
claims, Readability counts.
Read more: import this."""
'The Zen of Python\nclaims, "Readability counts."\nRead more: import this.'在上面的打印结果中，\n（读作“backslash en”）是一个代表换行符的单个元素。虽然它看起来像两个字符（反斜杠和 "n"），但在计算长度和元素选择时，它被视为单个字符。
字符串强制转换（String Coercion）：可以通过调用 str 构造函数并将对象值作为参数，从 Python 中的任何对象创建一个字符串。字符串的这一特性对于从各种类型的对象构建描述性字符串非常有用。
>>> str(2) + ' is an element of ' + str(digits)
'2 is an element of [1, 8, 2, 8]'拓展材料：计算机中的文本编码是一个复杂的话题。在本章中，我们将忽略字符串底层表示的细节。然而，对于许多应用程序来说，了解计算机如何编码字符串的细节是必不可少的知识。《Dive Into Python 3》中的 字符串章节 提供了关于字符编码和 Unicode 的描述。
2.3.6 树
我们能够将列表作为其他列表的元素使用，这为我们的编程语言提供了一种新的组合手段。这种能力被称为数据类型的闭包性质 (closure property)。通常，如果一种组合数据值的方法产生的结果本身还可以使用相同的方法进行组合，那么该组合方法就具有闭包性质。闭包是任何组合手段威力的关键，因为它允许我们创建层次结构 (hierarchical structures) —— 即由部分组成的结构，而这些部分本身又是由部分组成的，依此类推。
我们可以使用箱式指针（box-and-pointer）记法在环境图中可视化列表。列表被描绘为包含列表元素的相邻方框。像数字、字符串、布尔值和 None 这样的基本值直接显示在元素框内。而像函数值和其他列表这样的复合值则通过箭头来指示。
在列表中嵌套列表会引入复杂性。树（Tree）是一种基础的数据抽象，它为层次化数据的结构和操作赋予了规律性。
树具有一个根标签（root label）和一个分支（branches）序列。树的每个分支本身也是一棵树。没有分支的树称为叶子（leaf）。包含在树内部的任何树都称为该树的子树（sub-tree，例如分支的分支）。每棵子树的根称为该树中的一个节点（node）。
树的数据抽象由构造函数 tree 以及选择函数 label 和 branches 组成。我们从一个简化版本开始。
>>> def tree(root_label, branches=[]):
for branch in branches:
assert is_tree(branch), '分支必须是树'
return [root_label] + list(branches)
>>> def label(tree):
return tree[0]
>>> def branches(tree):
return tree[1:]只有当一棵树具有根标签且所有分支也都是树时，它才是结构良好（well-formed）的。is_tree 函数被用于 tree 构造函数中，以验证所有分支是否结构良好。
>>> def is_tree(tree):
if type(tree) != list or len(tree) < 1:
return False
for branch in branches(tree):
if not is_tree(branch):
return False
return Trueis_leaf 函数检查树是否有分支，若无分支则为叶子节点。
>>> def is_leaf(tree):
return not branches(tree)可以通过嵌套表达式来构造树。下面的树 t 的根标签为 3，并且有两个分支。
>>> t = tree(3, [tree(1), tree(2, [tree(1), tree(1)])])
>>> t
[3, [1], [2, [1], [1]]]
>>> label(t)
3
>>> branches(t)
[[1], [2, [1], [1]]]
>>> label(branches(t)[1])
2
>>> is_leaf(t)
False
>>> is_leaf(branches(t)[0])
True树形递归函数可用于构造树。例如，第 n 个斐波那契树的根标签是第 n 个斐波那契数，并且对于 n > 1，它有两个分支，这两个分支也都是斐波那契树。斐波那契树直观地展示了斐波那契数的树形递归计算过程。
>>> def fib_tree(n):
if n == 0 or n == 1:
return tree(n)
else:
left, right = fib_tree(n-2), fib_tree(n-1)
fib_n = label(left) + label(right)
return tree(fib_n, [left, right])
>>> fib_tree(5)
[5, [2, [1], [1, [0], [1]]], [3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]]树递归函数也可用于处理树。例如，count_leaves 函数用于计算树中叶子的数量。
>>> def count_leaves(tree):
if is_leaf(tree):
return 1
else:
branch_counts = [count_leaves(b) for b in branches(tree)]
return sum(branch_counts)
>>> count_leaves(fib_tree(5))
8分割树（Partition trees）：树也可以用来表示整数的分割。使用最大尺寸为 m 的部分对 n 进行分割的分割树是一棵二叉（两个分支）树，它代表了计算过程中所做的选择。在一棵非叶子的分割树中：
- 左分支（索引 0）包含所有至少使用一个 m 来分割 n 的方式，
- 右分支（索引 1）包含使用最大尺寸为 m-1 的部分进行分割的方式，
- 根标签是 m 分割树叶子上的标签表示从树根到叶子的路径是否代表了对 n 的一次成功分割。
>>> def partition_tree(n, m):
"""返回一棵使用最大为 m 的部分分割 n 的分割树"""
if n == 0:
return tree(True)
elif n < 0 or m == 0:
return tree(False)
else:
left = partition_tree(n-m, m)
right = partition_tree(n, m-1)
return tree(m, [left, right])
>>> partition_tree(2, 2)
[2, [True], [1, [1, [True], [False]], [False]]]从分割树打印分割结果是另一个遍历树的树形递归过程，它将每个分割构造为一个列表。每当到达一个 True 叶子时，就打印该分割。
>>> def print_parts(tree, partition=[]):
if is_leaf(tree):
if label(tree):
print(' + '.join(partition))
else:
left, right = branches(tree)
m = str(label(tree))
print_parts(left, partition + [m])
print_parts(right, partition)
>>> print_parts(partition_tree(6, 4))
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1切片操作也可以用于树的分支。例如，我们要限制树的分支数量。二叉树是指要么是叶子，要么最多有两个二叉树作为分支的树。一种常见的树变换称为二叉化（binarization），它通过将相邻的分支分组，从原始树计算出一棵二叉树。
>>> def right_binarize(tree):
"""构造一棵右分叉的二叉树"""
if is_leaf(tree):
return tree
if len(tree) > 2:
tree = [tree[0], tree[1:]]
return [right_binarize(b) for b in tree]
>>> right_binarize([1, 2, 3, 4, 5, 6, 7])
[1, [2, [3, [4, [5, [6, 7]]]]]]2.3.7 链表
到目前为止，我们只使用了原生类型来表示序列。然而，我们也可以开发并非 Python 内置的序列表示形式。一种由嵌套的“对”构造而成的常见序列表示形式称为链表（linked list）。下面的环境图展示了一个包含 1, 2, 3, 4 的四元素序列的链表表示。
链表是一个包含序列第一个元素（本例中为 1）和序列其余部分（本例中为 2, 3, 4 的表示）的“对”。第二个元素本身也是一个链表。最内层只包含 4 的链表的其余部分是 'empty'，这是一个表示空链表的值。
链表具有递归结构：链表的其余部分要么是一个链表，要么是 'empty'。我们可以定义一个抽象数据表示来验证、构造和选择链表的组件。
>>> empty = 'empty'
>>> def is_link(s):
"""判断 s 是否为链表"""
return s == empty or (len(s) == 2 and is_link(s[1]))
>>> def link(first, rest):
"""用 first 和 rest 构建一个链表"""
assert is_link(rest), " rest 必须是一个链表"
return [first, rest]
>>> def first(s):
"""返回链表 s 的第一个元素"""
assert is_link(s), " first 只能用于链表"
assert s != empty, "空链表没有第一个元素"
return s[0]
>>> def rest(s):
"""返回 s 的剩余元素"""
assert is_link(s), " rest 只能用于链表"
assert s != empty, "空链表没有剩余元素"
return s[1]在上面，link 是构造函数，first 和 rest 是链表抽象数据表示的选择函数。链表的行为条件是：就像“对”一样，其构造函数和选择函数是互逆函数。
- 如果链表
s是第一个元素f和链表r构造的，那么first(s)返回f，而rest(s)返回r
我们可以使用构造函数和选择函数来操作链表。
>>> four = link(1, link(2, link(3, link(4, empty))))
>>> first(four)
1
>>> rest(four)
[2, [3, [4, 'empty']]]我们对这类抽象数据的实现使用了作为双元素 list 值的“对”。值得注意的是，我们之前也能用函数来实现“对”，并且我们可以使用任何“对”来实现链表，因此我们可以仅使用函数来实现链表。
链表可以按顺序存储一系列值，但我们尚未证明它满足序列抽象。利用我们定义的抽象数据表示，我们可以实现表征序列的两个行为：长度和元素选择。
>>> def len_link(s):
"""返回链表 s 的长度"""
length = 0
while s != empty:
s, length = rest(s), length + 1
return length
>>> def getitem_link(s, i):
"""返回链表 s 中索引为 i 的元素"""
while i > 0:
s, i = rest(s), i - 1
return first(s)现在，我们可以使用这些函数将链表作为序列来操作。（我们还不能使用内置的 len 函数、元素选择语法或 for 循环，但很快就可以了。）
>>> len_link(four)
4
>>> getitem_link(four, 1)
2下面的一系列环境图展示了 getitem_link 在链表中寻找索引为 1 的元素 2 的迭代过程。为了简化图表，我们在下面使用 Python 原语定义了链表 four。这种实现选择违反了抽象屏障，但允许我们在这个例子中更容易地检查计算过程。
首先，函数 getitem_link 被调用，创建了一个局部帧。
while 循环头部中的表达式计算结果为 True，导致 while 循环中的赋值语句被执行。函数 rest 返回以 2 开头的子列表。
接下来，局部帧中的 s 将被更新为以原始列表的第二个元素开头的子列表。现在 while 循环头部表达式会产生一个 False 值，跳出 while 循环后 Python 会执行 getitem_link 最后一行的 return 语句。
这个最终的环境图显示了调用 first 的局部帧，其中包含绑定到同一子列表的 s。first 函数将返回列表 s 的首元素 2，这也将作为 getitem_link 的返回值。
这个例子演示了链表计算的一种常见模式，即迭代中的每一步都操作原列表越来越短的后缀。这种为了找到长度和元素而进行的增量处理确实需要消耗一些计算时间。Python 的内置序列类型采用了不同的实现方式，在计算序列长度或检索元素时不会有如此大的开销。该表示的细节超出了本书的讨论范围。 递归操作（Recursive manipulation）：len_link 和 getitem_link 都是以迭代形式实现的。它们逐层剥离嵌套的对，直到到达列表末尾（在 len_link 中）或目标元素（在 getitem_link 中）。我们还可以通过递归来实现长度计算和元素选择。
>>> def len_link_recursive(s):
"""返回链表 s 的长度"""
if s == empty:
return 0
return 1 + len_link_recursive(rest(s))
>>> def getitem_link_recursive(s, i):
"""返回链表 s 中索引为 i 的元素"""
if i == 0:
return first(s)
return getitem_link_recursive(rest(s), i - 1)
>>> len_link_recursive(four)
4
>>> getitem_link_recursive(four, 1)
2这些递归实现沿着“对”链进行，直到到达列表末尾（在 len_link_recursive 中）或目标元素（在 getitem_link_recursive 中）。
递归对于转换和组合链表也很有用。
>>> def extend_link(s, t):
"""返回一个在 s 链表的末尾连接 t 链表后的延长链表"""
assert is_link(s) and is_link(t)
if s == empty:
return t
else:
return link(first(s), extend_link(rest(s), t))
>>> extend_link(four, four)
[1, [2, [3, [4, [1, [2, [3, [4, 'empty']]]]]]]]
>>> def apply_to_all_link(f, s):
"""应用 f 到 s 中的每个元素"""
assert is_link(s)
if s == empty:
return s
else:
return link(f(first(s)), apply_to_all_link(f, rest(s)))
>>> apply_to_all_link(lambda x: x*x, four)
[1, [4, [9, [16, 'empty']]]]
>>> def keep_if_link(f, s):
"""返回 s 中 f(e) 为 True 的元素"""
assert is_link(s)
if s == empty:
return s
else:
kept = keep_if_link(f, rest(s))
if f(first(s)):
return link(first(s), kept)
else:
return kept
>>> keep_if_link(lambda x: x%2 == 0, four)
[2, [4, 'empty']]
>>> def join_link(s, separator):
"""返回由 separator 分隔的 s 中的所有元素组成的字符串"""
if s == empty:
return ""
elif rest(s) == empty:
return str(first(s))
else:
return str(first(s)) + separator + join_link(rest(s), separator)
>>> join_link(four, ", ")
'1, 2, 3, 4'递归构造（Recursive Construction）：当增量式地构造序列时，链表特别有用，这种情况在递归计算中经常出现。
第一章中的 count_partitions 函数通过树形递归过程计算了使用最大尺寸为 m 的部分分割整数 n 的方法的数量。有了序列，我们也可以使用类似的过程显式地枚举这些分割。
我们遵循与计数时相同的问题递归分析：使用最大为 m 的整数分割 n，涉及以下两种情况之一：
- 使用最大为 m 的整数分割 n-m，或者
- 使用最大为 m-1 的整数分割 n
对于基准情况，我们发现 0 有一个空分割，而分割负整数或使用小于 1 的整数是不可能的。
>>> def partitions(n, m):
"""返回一个链表，包含使用最大为 m 的部分对 n 的分割。
每个分割都表示为一个链表
"""
if n == 0:
return link(empty, empty) # 一个包含空分割的链表
elif n < 0 or m == 0:
return empty
else:
using_m = partitions(n-m, m)
with_m = apply_to_all_link(lambda s: link(m, s), using_m)
without_m = partitions(n, m-1)
return extend_link(with_m, without_m)在递归情况中，我们构造两个分割子列表。第一个使用 m，因此我们将 m 添加到结果 using_m 的每个元素前面，形成 with_m。
partitions 它是链表的链表，且每个链表都表示为是 list 值的嵌套对。使用带有适当分隔符的 join_link，我们可以以人类可读的方式显示这些分割。
>>> def print_partitions(n, m):
lists = partitions(n, m)
strings = apply_to_all_link(lambda s: join_link(s, " + "), lists)
print(join_link(strings, "\n"))
>>> print_partitions(6, 4)
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1