实现链表map_link函数：将指定函数应用于链表各元素

嘿，我来帮你搞定这个链表的map_link函数实现！先看看我们已经具备的基础链表操作函数：

empty = []  # 补充empty的定义，原代码中用到但未显式给出

def is_link(s):
    return s == empty or (len(s) == 2 and is_link(s[1]))

def link(first, rest):
    assert is_link(rest)
    return [first, rest]

def first(s):
    assert is_link(s)
    assert s != empty
    return s[0]

def rest(s):
    assert is_link(s)
    assert s != empty
    return s[1]

接下来我们要实现的map_link函数，核心是把指定函数f映射到链表的每一个元素上，返回一个全新的链表，每个元素都是原元素经过f处理后的结果。

函数需求与示例 #

def map_link(lst, f):
    """将函数f映射到链表的每个元素上。
    >>> r = link(1, link(2, link(3, empty)))
    >>> map_link(r, lambda x: x**2)
    [1, [4, [9, []]]]
    """

实现代码 #

我们可以用递归的方式来处理链表，这是链表操作的常规思路：

def map_link(lst, f):
    """将函数f映射到链表的每个元素上。
    >>> r = link(1, link(2, link(3, empty)))
    >>> map_link(r, lambda x: x**2)
    [1, [4, [9, []]]]
    """
    # 递归终止条件：空链表直接返回空
    if lst == empty:
        return empty
    # 非空链表：处理第一个元素，再递归处理剩余部分，最后组合成新链表
    else:
        return link(f(first(lst)), map_link(rest(lst), f))

实现思路解释 #

• 当传入的链表是空链表时，直接返回空链表，这是递归的终止条件；
• 当链表非空时，先通过first(lst)拿到链表的第一个元素，用函数f处理它；然后递归调用map_link处理链表的剩余部分（rest(lst)）；最后用link函数把处理后的第一个元素和剩余部分的处理结果组合成一个新的链表。

这样运行示例中的测试代码，就能得到符合预期的结果啦～

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