列表最常见的两种修改操作是元素赋值和 append method.

>>> s = [1, 3, 4]
>>> t = s  # A second name for the same list
>>> t[0] = 2  # this changes the first element of the list to 2, affecting both s and t
>>> s
[2, 3, 4]
>>> s.append(5)  # this adds 5 to the end of the list, affecting both s and t
>>> t
[2, 3, 4, 5]

列表还有许多其他修改方法：

• append(elem): Add elem 添加到列表末尾。返回 None.
• extend(s)：把可迭代对象中的所有元素添加到列表末尾。 s 添加到列表末尾。返回 None.
• insert(i, elem)：把 elem 插入索引 i. If i 大于或等于列表长度， elem 会被插到末尾。该操作不会替换现有元素，只会加入新元素 elem。返回 None.
• remove(elem)：移除列表中第一次出现的 elem 。返回 None。如果 elem 不在列表中，则报错。
• pop(i)：移除并返回指定索引处的元素 i.
• pop()：移除并返回最后一个元素。

字典也支持元素赋值（经常使用）和 pop （较少使用）。

>>> d = {2: 3, 4: 16}
>>> d[2] = 4
>>> d[3] = 9
>>> d
{2: 4, 4: 16, 3: 9}
>>> d.pop(4)
16
>>> d
{2: 4, 3: 9}

例如，考虑下面这个生成器函数：

def countdown(n):
    print("Beginning countdown!")
    while n >= 0:
        yield n
        n -= 1
    print("Blastoff!")

Calling countdown(k) 会返回一个从指定数字倒数到 0 的生成器对象 k 。由于生成器也是迭代器，可以对结果对象调用 iter ；它只会返回同一个对象。注意，此时函数体尚未执行，不会打印或产出任何数字。

>>> c = countdown(5)
>>> c
<generator object countdown ...>
>>> c is iter(c)
True

那么倒数是怎样发生的？生成器也是迭代器，所以可以调用 next 取得下一个元素！第一次调用 next 时，从函数体第一行开始执行，直到遇到 yield 语句。该语句中表达式的求值结果会被返回。 yield 下面的交互会话接续前面的示例。

>>> next(c)
Beginning countdown!
5

与本课程此前见过的函数不同，生成器函数能够记住状态。后续每次调用 next时，都会从上一次执行的 yield 语句之后继续。与第一次调用一样， next会一直执行到下一个 yield 语句。正因如此， Beginning countdown! 不会再次被打印。

>>> next(c)
4
>>> next(c)
3

接下来 3 次调用 next 会继续依次产出递减整数，直到 0。再调用一次时会抛出 StopIteration 错误，因为已没有值可以产出（也就是在遇到下一个 yield 语句前，函数体已经结束）。

>>> next(c)
2
>>> next(c)
1
>>> next(c)
0
>>> next(c)
Blastoff!
StopIteration

分别调用 countdown 会创建各自拥有独立状态的生成器对象。生成器通常不会重新开始；若要重置序列，请再次调用生成器函数，创建新对象。

>>> c1, c2 = countdown(5), countdown(5)
>>> c1 is c2
False
>>> next(c1)
5
>>> next(c2)
5

总结如下：

• 一个 生成器函数 has a yield 语句，并返回一个 生成器对象.
• 调用 iter 并传入生成器对象，会原样返回该对象，不改变当前状态。
• 在对生成器对象调用 next 之前，生成器函数体不会执行。调用 next 会计算并返回序列中的下一个对象。如果序列已经耗尽，则抛出 StopIteration 。

• 生成器会“记住”状态，供下一次 next 调用使用。因此，

  • 第一次 next 调用按以下过程执行：

    1. 进入函数并运行，直到含有 yield.
    2. 返回 yield 语句中的值，同时保存函数状态供后续调用使用 next calls.

  • 后续的 next 调用按以下过程执行：

    1. 重新进入函数，从 上次执行的 yield 语句之后开始，运行到下一个 yield 语句。
    2. 返回 yield 语句中的值，同时保存函数状态供后续调用使用 next calls.
• 调用生成器函数会返回全新的生成器对象（类似对可迭代对象调用 iter ）。
• 除非定义如此，否则生成器不会重新开始。若要从第一个元素开始，只需再次调用生成器函数创建新生成器。

生成器还有一个有用工具： yield from 语句。 yield from 会依次产出某个迭代器或可迭代对象中的所有值。

>>> def gen_list(lst):
...     yield from lst
...
>>> g = gen_list([1, 2, 3, 4])
>>> next(g)
1
>>> next(g)
2
>>> next(g)
3
>>> next(g)
4
>>> next(g)
StopIteration

>>> for x in "cat":
...     print(x)
c
a
t
>>> [x*2 for x in (1, 2, 3)]
[2, 4, 6]
>>> list(range(4))
[0, 1, 2, 3]

请注意这里的抽象：给定某个可迭代对象，我们有一组明确的操作可以使用。本节将越过抽象屏障，看看可迭代对象在“底层”如何实现。

In Python, 可迭代对象 正式定义为可以传给内置函数 iter 并产生 迭代器的对象. An 迭代器的对象 是另一类对象，可以通过 next 函数逐个产生元素。

• iter(iterable)：返回一个遍历给定可迭代对象元素的迭代器。
• next(iterator)：返回迭代器的下一个元素；若已无元素，则抛出 StopIteration 异常。

例如，数字列表是可迭代对象，因为 iter 会生成遍历该序列的迭代器，我们可以使用 next 逐项访问：

>>> lst = [1, 2, 3]
>>> lst_iter = iter(lst)
>>> lst_iter
<list_iterator object ...>
>>> next(lst)
1
>>> next(lst)
2
>>> next(lst)
3
>>> next(lst)
StopIteration

迭代器非常简单，唯一的机制就是取得下一个元素： next。迭代器无法按索引访问，也不能后退。某个元素一旦被产出，除非事先保存，否则无法再次取得。

注意，迭代器自身也是可迭代对象；对迭代器调用 iter 只会返回同一个迭代器对象。

例如，可以看看对列表使用 iter 和 next 时会发生什么：

>>> lst = [1, 2, 3]
>>> next(lst)             # Calling next on an iterable
TypeError: 'list' object is not an iterator
>>> list_iter = iter(lst) # Creates an iterator for the list
>>> next(list_iter)       # Calling next on an iterator
1
>>> next(iter(list_iter)) # Calling iter on an iterator returns itself
2
>>> for e in list_iter:   # Exhausts remainder of list_iter
...     print(e)
3
>>> next(list_iter)       # No elements left!
StopIteration
>>> lst                   # Original iterable is unaffected
[1, 2, 3]

其中 map 和 filter 等此前学过的函数会返回迭代器对象。

可以看到，与自然界的树不同，树抽象数据类型通常把根画在顶部，把叶节点画在底部。

对于树 t:

• 根标签可以是任意值，表达式 label(t) 会返回它。
• 它的分支也都是树， branches(t) 会返回分支列表。
• 可以用下面的表达式构造一棵完全相同的树： tree(label(t), branches(t)).
• 可以调用接收树作为参数的函数，例如 is_leaf(t).
• 这就是操作树的方式，不需要 t == x 或 t[0] 或 x in t 或 list(t), etc.
• 在不破坏抽象屏障的前提下，没有办法改变一棵树。

下面是一棵示例树 t1，其中分支 branches(t1)[1] 的返回值是 t2.

t2 = tree(5, [tree(6), tree(7)])
t1 = tree(3, [tree(4), t2])

一个 path 是一串树，每棵树都是下一棵的父节点。

items 可能与 inventory是同一个列表对象。请思考：如果你正在遍历 items while inventory ，同时底层又改变了同一个列表，会发生什么？遍历列表时移除多个匹配元素又会怎样？

需要进行哪些递归调用？

make_path(b, p[1:]) 只能在标签为指定值的 b 上调用 p[1]。要么找到这样的分支，要么创建一个。 tree(p[1]).

递归调用返回哪种值？

递归调用返回一棵包含所需标签路径的树。 p[1:].

可能的返回值分别表示什么？

该返回值会成为最终返回树的一个分支。 make_path(t, p).

怎样利用这些返回值完成实现？

把返回值放入分支列表。 new_branches.

既然已经断言 p[0] == label(t), if p 长度为 1，那么 t 已经包含所需标签路径， p因此直接返回即可。 t.

If p[1] 如果下一个标签属于某个现有分支，就应沿该分支创建路径；否则必须创建新分支。

遍历各分支，寻找标签匹配的分支，然后把对该分支递归调用的结果追加到 p[1]。 new_branches.

如果没有分支的标签匹配， p[1]就创建新分支，并使用 tree(p[1]), use make_path 构造其余路径，再把结果追加到分支列表。 new_branches.