Problem 5: Trictionary or Treat (200pts)

Problem

A trictionary is a pair of tree k and v. They have identical structure: each node in k has a corresponding node in v. The labels in k are called keys. Each key may be the label for multiple nodes in k, and the values for that key are the labels of all the corresponding nodes in v.

A lookup function returns one of the values for a key. Specifically, a lookup function for a node in k is a function that takes v as an argument and returns the label for the corresponding node in v.

Implement the generator function lookups, which takes as input a tree k and a key. It yields all lookup functions for nodes in k that have key as their label, the functions could be yielded in any order.

一个 trictionary（树词典）是一对树 k 和 v。 它们具有相同的结构：k 中的每个节点在 v 中都有一个对应的节点。 k 中的标签被称为键。每个键可能是 k 中多个节点的标签， 该键的值是 v 中所有相应节点的标签。

查找函数返回一个键的其中一个值。 具体来说，k 中一个节点的查找函数是一个以 v 作为参数并返回 v 中对应节点的标签的函数。

实现生成器函数 lookups，它接受一棵树 k 和一个键 key 作为输入。 它产出 k 中标签为 key 的所有节点的查找函数，这些函数的产出顺序可以是任意的。

def lookups(k, key):
    """Yield one lookup function for each node of k that has the label key.
    >>> k = tree(5, [tree(7, [tree(2)]), tree(8, [tree(3), tree(4)]), tree(5, [tree(4), tree(2)])])
    >>> v = tree('Go', [tree('C', [tree('C')]), tree('A', [tree('S'), tree(6)]), tree('L', [tree(1), tree('A')])])
    >>> type(lookups(k, 4))
    <class 'generator'>
    >>> sorted([f(v) for f in lookups(k, 2)])
    ['A', 'C']
    >>> sorted([f(v) for f in lookups(k, 3)])
    ['S']
    >>> [f(v) for f in lookups(k, 6)]
    []
    """
    "*** YOUR CODE HERE ***"

Hints

Hint 1: To access corresponding branches in trees k and v that share the same structure, use the same index i: branches(k)[i] and branches(v)[i].

Hint 2: What happens in the following code?

>>> fs = [lambda: i for i in range(0, 5)]
>>> [f() for f in fs] # Why is this [4, 4, 4, 4, 4] instead of [0, 1, 2, 3, 4]?
[4, 4, 4, 4, 4]
>>> fs = [(lambda i: lambda: i)(i) for i in range(0, 5)]
>>> [f() for f in fs] # Why is this [0, 1, 2, 3, 4] instead of [4, 4, 4, 4, 4]?
[0, 1, 2, 3, 4]

Understanding why the snippets above behave differently will help you solve this problem.

• 要访问结构相同的树 k 和 v 中相应的分支，请使用相同的索引 i：branches(k)[i] 和 branches(v)[i]。

• 下面的代码发生了什么？

>>> fs = [lambda: i for i in range(0, 5)]
>>> [f() for f in fs] # 为什么这是 [4, 4, 4, 4, 4] 而不是 [0, 1, 2, 3, 4]？
[4, 4, 4, 4, 4]
>>> fs = [(lambda i: lambda: i)(i) for i in range(0, 5)]
>>> [f() for f in fs] # 为什么这是 [0, 1, 2, 3, 4] 而不是 [4, 4, 4, 4, 4]？
[0, 1, 2, 3, 4]

• 理解为什么上面的代码片段行为不同将有助于您解决此问题。

• 如果无法理解，可以尝试将上述代码中的 list comprehension 变成 for ...: 的形式，将 lambda 写成 def ...:，然后进行分析。

• 如果还不能理解，可以参考这个非官方文档。

Solutions