2.3 序列

序列是值的有序集合。 序列是计算机科学中一个强大的、基本的抽象概念。 序列不是特定内置类型或抽象数据表示的实例，而是在几种不同类型的数据之间共享的行为集合。 也就是说，序列有很多种，但它们都有共同的行为。 特别是,

长度。 序列的长度是有限的。 空序列的长度为0。

元素的选择。 序列有一个元素对应于任何小于其长度的非负整数索引，第一个元素从0开始。

Python包括几种原生数据类型，它们是序列，其中最重要的是列表。

2.3.1 列表

列表值是可以具有任意长度的序列。列表有大量的内建行为，以及表达这些行为的特定语法。我们已经看到了计算结果为列表实例的列表字面量，以及计算结果为列表中的值的元素选择表达式。内置的len函数返回序列的长度。下面，digits是一个包含四个元素的列表。下标3的元素是8。

>>> digits = [1, 8, 2, 8]
>>> len(digits)
4
>>> digits[3]
8

此外，列表可以相加并乘以整数。对于序列，加法和乘法并不添加或相乘元素，而是组合和复制序列本身。也就是说，operator模块中的add函数(以及+操作符)产生了一个连接所添加参数的列表。操作符中的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]
30

2.3.2 序列迭代

在许多情况下，我们希望遍历序列的元素，并依次为每个元素执行一些计算。这种模式非常常见，因此Python有一个额外的控制语句来处理顺序数据：for语句。

考虑计算一个值在序列中出现多少次的问题。我们可以使用while循环实现一个函数来计算这个计数。

>>> def count(s, value):
        """Count the number of occurrences of value in sequence s."""
        total, index = 0, 0
        while index < len(s):
            if s[index] == value:
                total = total + 1
            index = index + 1
        return total

>>> count(digits, 8)
2

Python for语句可以通过直接遍历元素值而根本不引入名称索引来简化函数体。

>>> def count(s, value):
        """Count the number of occurrences of value in sequence s."""
        total = 0
        for elem in s:
            if elem == value:
                total = total + 1
        return total

>>> count(digits, 8)
2

for语句由单个子句组成，其形式如下：

for <name> in <expression>:
    <suite>

for语句由以下过程执行：

1. 求头文件<表达式>的值，它必须产生一个可迭代值。

2. 对于该可迭代值中的每个元素值，按顺序：

   1. 在当前框架中绑定到该值。

   2. 执行<套件>。

这个执行过程引用可迭代值。 列表是序列的一种类型，而序列是可迭代值。 它们的元素按照它们的顺序来考虑。 Python还包括其他可迭代类型，但我们现在只关注序列; 术语“iterable”的一般定义出现在第4章的迭代器部分。

这个评估程序的一个重要结果是：<名称>将在执行for语句后绑定到序列的最后一个元素。 for循环引入了另一种通过语句更新环境的方式。

序列拆封。 程序中的一种常见模式是，有一个本身是序列的元素序列，但所有元素的长度都固定。 for语句可以在其头文件中包含多个名称，以“解包”每个元素序列到其各自的元素中。 例如，我们可能有一个包含两元素列表的列表。

>>> pairs = [[1, 2], [2, 2], [2, 3], [4, 4]]

并希望找到具有相同的第一个和第二个元素的对的数目。

>>> same_count = 0

下面的for语句头中有两个名字，它将把每个名字x和y分别绑定到每对元素中的第一个和第二个元素。

>>> for x, y in pairs:
        if x == y:
            same_count = same_count + 1

>>> same_count
2

这种将多个名称绑定到固定长度序列中的多个值的模式称为序列解包;这与我们在赋值语句中看到的将多个名称绑定到多个值的模式相同。

范围。range是Python中另一种内置的序列类型，它表示一个整数范围。使用range创建范围，range接受两个整数参数:第一个数字和所需范围内最后一个数字之外的一个。

>>> range(1, 10)  # Includes 1, but not 10
range(1, 10)

在一个范围上调用list构造函数将计算出具有与该范围相同元素的列表，因此可以很容易地检查元素。

>>> range(1, 10)  # Includes 1, but not 10
range(1, 10)

如果只给出了一个参数，则将其解释为从0开始的范围内超出最后一个值的参数。

>>> list(range(5, 8))
[5, 6, 7]

Ranges通常以表达式的形式出现在for头文件中，以指定套件应该被执行的次数:通常的惯例是，如果名称在套件中未使用，则在for头文件中使用单个下划线字符：

>>> for _ in range(3):
        print('Go Bears!')

Go Bears!
Go Bears!
Go Bears!

就解释器而言，这个下划线只是环境中的另一个名称，但在程序员中有一个常规的含义，表示这个名称不会出现在任何未来的表达式中。

2.3.3 序列处理

序列是一种非常常见的复合数据形式，整个程序通常都是围绕这个单一的抽象来组织的。 具有输入和输出序列的模块化组件可以混合和匹配来执行数据处理。 可以通过将序列处理操作的管道链接在一起来定义复杂的组件，每个操作都是简单且有重点的。

列表推导式。 许多序列处理操作可以通过计算序列中每个元素的固定表达式并在结果序列中收集结果值来表示。 在Python中，列表推导式是执行此类计算的表达式。

>>> odds = [1, 3, 5, 7, 9]
>>> [x+1 for x in odds]
[2, 4, 6, 8, 10]

上面的for关键字不是for语句的一部分，而是列表推导式的一部分，因为它包含在方括号中。子表达式x+1在x绑定到每个概率元素的情况下依次求值，结果值被收集到一个列表中。

另一个常见的序列处理操作是选择满足某些条件的值子集。列表推导式也可以表示这种模式，例如，选择平均除25的概率的所有元素。

>>> [x for x in odds if 25 % x == 0]
[1, 5]

列表推导式的一般形式是：

[<map expression> for <name> in <sequence expression> if <filter expression>]

要对列表推导式求值，Python要对序列表达式求值，该表达式必须返回一个可迭代值。 然后，对于order中的每个元素，将元素值绑定到<name>，并计算过滤器表达式，如果它产生一个真值，则计算映射表达式。 映射表达式的值被收集到一个列表中。

聚合。 序列处理中的第三种常见模式是将序列中的所有值聚合为单个值。 内置函数sum、min和max都是聚合函数的例子。

通过结合对每个元素求表达式、选择元素子集和聚合元素的模式，我们可以使用序列处理方法解决问题。

完全数是一个等于它的因数之和的正整数。 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通常也被认为是一个完全数，但它不符合我们对除数的定义。)

>>> [n for n in range(1, 1000) if sum(divisors(n)) == n]
[6, 28, 496]

我们可以用除数的定义来解决另一个问题，求出边长为整数的矩形的最小周长，给定它的面积。矩形的面积是它的高乘以它的宽。因此，给定面积和高度，我们可以计算宽度。我们可以断言宽度和高度都平均地划分区域，以确保边长是整数。

>>> 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)]

最后，许多形式的聚合可以表示为重复地对到目前为止的简化值和每个元素应用一个双参数函数。

>>> def reduce(reduce_fn, s, initial):
        reduced = initial
        for x in s:
            reduced = reduce_fn(reduced, x)
        return reduced

例如，reduce可用于将序列中的所有元素相乘。使用mul作为reduce_fn, 1作为初始值，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]

传统的名字。在计算机科学界，apply_to_all更常见的名称是map，而keep_if更常见的名称是filter。在Python中，内置的map和filter是这些不返回列表的函数的泛化。这些函数将在第4章中讨论。上面的定义等价于对内置map和filter调用的结果应用list构造函数。

>>> 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 序列的抽象

我们引入了满足序列抽象的两种原生数据类型：列表和范围。两者都满足本节开始时的条件：长度和元素选择。Python还包括两个序列类型的行为，它们扩展了序列抽象。

成员资格。可以测试值是否属于序列。Python有两个操作符in和not in，根据元素是否出现在序列中，计算结果为True或False。

>>> digits
[1, 8, 2, 8]
>>> 2 in digits
True
>>> 1828 not in digits
True

切片。序列中包含更小的序列。序列的片是原始序列的任意连续空间，由一对整数指定。与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中有很多关于字符串如何表示、表达和操作的细节。 字符串是丰富抽象的另一个例子，它需要程序员做出实质性的承诺来掌握。 本节将简要介绍基本的字符串行为。

字符串字面值可以表示由单引号或双引号包围的任意文本。

>>> 'I am string!'
'I am string!'
>>> "I've got an apostrophe"
"I've got an apostrophe"
>>> '您好'
'您好'

我们已经在代码中看到了字符串，如文档字符串、print调用和assert语句中的错误消息。

字符串满足我们在本节开始时介绍的序列的两个基本条件：它们有长度并支持元素选择。

>>> city = 'Berkeley'
>>> len(city)
8
>>> city[3]
'k'

字符串的元素本身就是只有一个字符的字符串。字符是字母表中的任何一个字母、标点符号或其他符号。与许多其他编程语言不同，Python没有单独的字符类型;任何文本都是字符串，表示单个字符的字符串长度为1。

与列表一样，字符串也可以通过加法和乘法来组合。

>>> 'Berkeley' + ', CA'
'Berkeley, CA'
>>> 'Shabu ' * 2
'Shabu Shabu '

成员资格。字符串的行为与Python中的其他序列类型不同。字符串抽象不符合我们为列表和范围描述的完整序列抽象。特别是，成员操作符in适用于字符串时与应用于序列时的行为完全不同。它匹配子字符串而不是元素。

>>> 'here' in "Where's Waldo?"
True

多行文字。字符串不局限于一行。三引号分隔跨多行的字符串文字。我们已经在文档字符串中广泛地使用了这种三重引用。

>>> """The Zen of Python
claims, Readability counts.
Read more: import this."""
'The Zen of Python\nclaims, "Readability counts."\nRead more: import this.'

在上面打印的结果中，\n(发音为“反斜杠en”)是表示新行的单个元素。尽管它以两个字符(反斜杠和“n”)出现，但出于长度和元素选择的目的，它被认为是单个字符。

字符串强制。Python中的任何对象都可以通过调用带有对象值作为参数的str构造函数来创建字符串。字符串的这个特性对于从各种类型的对象构造描述性字符串很有用。

>>> str(2) + ' is an element of ' + str(digits)
'2 is an element of [1, 8, 2, 8]'

进一步阅读。在计算机中对文本进行编码是一个复杂的课题。在本章中，我们将抽象出字符串如何表示的细节。然而，对于许多应用程序来说，计算机如何编码字符串的具体细节是必不可少的知识。Python 3的strings章节提供了字符编码和Unicode的描述。

2.3.6 树

我们使用列表作为其他列表的元素的能力在我们的编程语言中提供了一种新的组合方法。 这种能力称为数据类型的闭包属性。 通常，如果组合的结果本身可以使用相同的方法组合，那么组合数据值的方法具有闭包属性。 闭包是任何组合方式的关键，因为它允许我们创建层次结构——由部件组成的结构，部件本身也由部件组成，等等。

我们可以使用框-指针表示法在环境图中可视化列表。 列表被描述为包含列表元素的相邻框。 原始值如数字、字符串、布尔值和None出现在元素框中。 复合值，如函数值和其他列表，由箭头指示。

在列表中嵌套列表会带来复杂性。 树是一种基本的数据抽象，它赋予分层值的结构和操作规则性。

树有一个根标签和一系列的分支。一棵树的每一根树枝都是一棵树。 没有树枝的树叫做叶子。 一个树中包含的任何树都称为该树的子树(例如一个分支的分支)。 树的每个子树的根称为树中的一个节点。

树的数据抽象由构造函数tree和选择器label和branches组成。

我们从一个简化的版本开始。

>>> def tree(root_label, branches=[]):
        for branch in branches:
            assert is_tree(branch), 'branches must be trees'
        return [root_label] + list(branches)

>>> def label(tree):
        return tree[0]

>>> def branches(tree):
        return tree[1:]

只有具有根标签且所有分支也是树时，树才是格式良好的。在tree构造函数中应用is_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 True

is_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

分区树。树还可以用来表示整数的分区。对于n的分区树，使用最大为m的部分是一棵二叉树(两个分支)，它表示在计算过程中所做的选择。在非叶分区树中：

• 左(索引0)分支包含至少使用一个m的所有分区n的方式

• 右(索引1)分支包含最多使用m-1部分的分区

• 根标签为m

划分树叶子上的标签表示从树的根到叶子的路径是否表示n的成功划分。

>>> def partition_tree(n, m):
        """Return a partition tree of n using parts of up to m."""
        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]]]

从分区树打印分区是另一个遍历树的树递归过程，将每个分区构造为一个列表。每当到达一个真叶时，就打印分区。

>>> 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

切片也可以用在树枝上。例如，我们可能想要对树中的分支数量进行限制。一个二叉树可以是一个叶子树，也可以是一个最多由两棵二叉树组成的序列。一种称为二值化的常见树转换，通过将相邻的分支分组，从原始树计算二值树。

>>> def right_binarize(tree):
        """Construct a right-branching binary 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中的序列表示。由嵌套对构造的序列的公共表示称为链表。下面的环境图演示了包含1、2、3和4的4个元素序列的链表表示。

链表是一对包含序列的第一个元素(在本例中是1)和序列的其余元素(在本例中是2、3、4的表示)。第二个元素也是链表。仅包含4个链表的最内部链表的其余部分是“空”，一个表示空链表的值。

链表具有递归结构：链表的其余部分是链表或“空”。我们可以定义一个抽象的数据表示来验证、构造和选择链表的组件。

>>> empty = 'empty'
>>> def is_link(s):
        """s is a linked list if it is empty or a (first, rest) pair."""
        return s == empty or (len(s) == 2 and is_link(s[1]))

>>> def link(first, rest):
        """Construct a linked list from its first element and the rest."""
        assert is_link(rest), "rest must be a linked list."
        return [first, rest]

>>> def first(s):
        """Return the first element of a linked list s."""
        assert is_link(s), "first only applies to linked lists."
        assert s != empty, "empty linked list has no first element."
        return s[0]

>>> def rest(s):
        """Return the rest of the elements of a linked list s."""
        assert is_link(s), "rest only applies to linked lists."
        assert s != empty, "empty linked list has no rest."
        return s[1]

上面，link是一个构造函数，first和rest是链表的抽象数据表示的选择器。链表的行为条件是，与pair一样，它的构造函数和选择器是逆函数。

• 如果一个链表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']]]

这种抽象数据的实现使用的是一对两个元素列表的值。值得注意的是，我们还能够使用函数实现对，并且可以使用任何对实现链表，因此我们可以仅使用函数实现链表。

链表可以按顺序存储一个值序列，但是我们还没有证明它满足序列抽象。使用我们定义的抽象数据表示，我们可以实现表征序列的两个行为：长度和元素选择。

>>> def len_link(s):
        """Return the length of linked list s."""
        length = 0
        while s != empty:
            s, length = rest(s), length + 1
        return length

>>> def getitem_link(s, i):
        """Return the element at index i of linked list s."""
        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原语定义了链接列表4，以简化图。这种实现选择违反了抽象障碍，但是允许我们更容易地检查这个示例的计算过程。

首先，调用函数getitem_link，创建一个本地框架。

while头文件中的表达式计算为true，这将导致执行while套件中的赋值语句。rest函数返回以2开头的子列表。

接下来，本地名称s将被更新，以引用以原始列表的第二个元素开始的子列表。现在计算while头表达式会得到一个假值，因此Python在getitem_link的最后一行的return语句中计算表达式。

这个最终的环境图显示了调用first的本地框架，其中包含绑定到同一子列表的名称。 第一个函数选择值2并返回它，它也将从getitem_link返回。

此示例演示了一种使用链表进行计算的常见模式，其中迭代中的每一步都操作原始链表的一个越来越短的后缀。 这种寻找链表长度和元素的增量处理确实需要一些时间来计算。 Python的内置序列类型以不同的方式实现，在计算序列长度或检索其元素方面不会有很大的成本。 这种表示的细节不在本文的讨论范围之内。

递归操作。 len_link和getitem_link都是迭代的。 它们剥离嵌套对的每一层，直到到达列表的末尾(在len_link中)或所需的元素(在getitem_link中)。 我们还可以使用递归实现长度和元素选择。

>>> def len_link_recursive(s):
        """Return the length of a linked list s."""
        if s == empty:
            return 0
        return 1 + len_link_recursive(rest(s))

>>> def getitem_link_recursive(s, i):
        """Return the element at index i of linked list s."""
        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):
        """Return a list with the elements of s followed by those of 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):
        """Apply f to each element of 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):
        """Return a list with elements of s for which f(e) is 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):
        """Return a string of all elements in s separated by separator."""
        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'

递归结构。 链表在递增构造序列时特别有用，这种情况在递归计算中经常出现。

第1章中的count_partitions函数通过树递归过程计算了使用最大大小为m的部分对整数n进行分区的方法数量。 有了序列，我们还可以使用类似的过程显式地枚举这些分区。

我们按照计数时所做的相同的递归分析来处理这个问题：使用整数到m的分区n涉及到

1. 使用整数到m的分区n-m

2. 或使用整数到m-1的分区n

对于基本情况，我们发现0有一个空分区，而分区一个负整数或使用小于1的部分是不可能的。

>>> def partitions(n, m):
        """Return a linked list of partitions of n using parts of up to m.
        Each partition is represented as a linked list.
        """
        if n == 0:
            return link(empty, empty) # A list containing the empty partition
        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，因此我们在结果using_m的每个元素前加上m，形成with_m。

分区的结果是高度嵌套的：一个链表的链表，每个链表都表示为嵌套的列表值对。使用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