Python中两段map相关代码执行结果不同的原因探究

问题场景 #

在实现二叉树前序遍历的preorder函数中，两段处理分支的代码表现截然不同：第一段代码返回错误结果[1]，第二段则返回正确的前序遍历结果。代码如下：

def preorder(t):
    """Return a list of the entries in this tree in the order that they
    would be visited by a preorder traversal (see problem description).

    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> preorder(numbers)
    [1, 2, 3, 4, 5, 6, 7]
    >>> preorder(tree(2, [tree(4), tree(6)]))
    [2, 4, 6]
    """
    order = [label(t)]

    # 第一段代码：执行后返回错误结果[1]
    # map(lambda x:order.extend(x), list(map(preorder, branches(t))))
    
    # 第二段代码：执行后返回正确前序遍历结果[1,2,3,4,5,6,7]
    # orders = list(map(preorder, branches(t)))
    # for elem in orders:
    #     order.extend(elem)
    
    return order

def tree(label, branches=[]):
    """Construct a tree with the given label value and a list of branches."""
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [label] + list(branches)

def label(tree):
    """Return the label value of a tree."""
    return tree[0]

def branches(tree):
    """Return the list of branches of the given tree."""
    return tree[1:]

核心原因 #

两段代码的差异本质是Python3中map()的惰性特性：

• 第一段代码中，map(lambda x:order.extend(x), ...)创建了一个惰性迭代器，但没有对这个迭代器做任何遍历操作（比如转成list、用for循环迭代）。这意味着lambda函数里的order.extend(x)根本没有被执行，order里始终只有根节点的标签值，所以返回[1]。哪怕内层的list(map(preorder, branches(t)))已经计算出了所有分支的遍历结果，但外层map的lambda逻辑完全没触发。

• 第二段代码做了两步关键操作：

  1. 先把map(preorder, branches(t))转成list，这一步会强制遍历迭代器，执行所有分支的preorder调用，得到完整的分支遍历结果列表。
  2. 通过for循环遍历这个列表，逐个调用order.extend(elem)，把分支的遍历结果追加到主列表里，最终得到正确的前序遍历结果。

验证修正 #

如果要让第一段代码生效，需要强制消费外层的map迭代器，比如转成list：

list(map(lambda x:order.extend(x), list(map(preorder, branches(t)))))

这样lambda里的逻辑才会被执行，order会被正确填充。

内容的提问来源于stack exchange，提问作者hyc050104