## Problem 6: Deep Map Implement `deep_map`, which takes a function `f` and a `link`. It returns a *new* linked list with the same structure as `link`, but with `f` applied to any element within `link` or any `Link` instance contained in `link`. The `deep_map` function should recursively apply `fn` to each of that `Link`'s elements rather than to that `Link` itself. *Hint*: You may find the built-in `isinstance` function useful. You can also use the `type(link) == Link` to check whether an object is a linked list. ```python def deep_map(f, link): """Return a Link with the same structure as link but with fn mapped over its elements. If an element is an instance of a linked list, recursively apply f inside that linked list as well. >>> s = Link(1, Link(Link(2, Link(3)), Link(4))) >>> print(deep_map(lambda x: x * x, s)) <1 <4 9> 16> >>> print(s) # unchanged <1 <2 3> 4> >>> print(deep_map(lambda x: 2 * x, Link(s, Link(Link(Link(5)))))) <<2 <4 6> 8> <<10>>> """ "*** YOUR CODE HERE ***"

以下是`deep_map`函数的实现：

class Link:
    empty = ()
    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_str = ' ' + repr(self.rest)
        else:
            rest_str = ''
        return '<' + str(self.first) + rest_str + '>'

    def __len__(self):
        return 1 + len(self.rest)

    def __getitem__(self, i):
        if i == 0:
            return self.first
        else:
            return self.rest[i-1]

    def __setitem__(self, i, value):
        if i == 0:
            self.first = value
        else:
            self.rest[i-1] = value


def deep_map(f, link):
    """
    Return a Link with the same structure as link but with f mapped over
    its elements. If an element is an instance of a linked list, recursively
    apply f inside that linked list as well.
    """
    if link is Link.empty:
        return Link.empty
    elif isinstance(link, Link):
        return Link(deep_map(f, link.first), deep_map(f, link.rest))
    else:
        return f(link)

我们首先处理递归基，如果传入的`link`为空链表，则直接返回空链表。然后判断`link`是否是链表类型，如果是，则对`link`的第一个元素和剩余部分递归调用`deep_map`函数，并用它们创建一个新的链表返回。如果`link`不是链表类型，则直接将`f(link)`的结果返回。

我们可以测试`deep_map`函数的正确性：

s = Link(1, Link(Link(2, Link(3)), Link(4)))
print(deep_map(lambda x: x * x, s)) # <1 <4 9> 16>
print(s) # <1 <2 3> 4>
t = Link(s, Link(Link(Link(5))))
print(deep_map(lambda x: 2 * x, t)) # <<2 <4 6> 8> <<10>>