Skip to content

Problem 1.1: Function as Lists (200pts)

Problem

In this problem, you need to implement a abstract data type (ADT) for functions using lists. Here, a function is represented as a list of pairs, where each pair consists of an input and its corresponding output.

For example, the list [] represents an empty function, while the list [[0, 1], [1, 2], [2, 3]] represents a function defined as \(\{0 \mapsto 1, 1 \mapsto 2, 2 \mapsto 3\}\).

Specifically, you need to implement the following functions:

在本问题中，您需要使用列表来实现一个用于函数的抽象数据类型 (ADT)。在这里，一个函数表示为一个对（pair）的列表，其中每对都由一个输入及其对应的输出组成。

例如，列表 [] 表示一个空函数，而列表 [[0, 1], [1, 2], [2, 3]] 表示定义为 \(\{0 \mapsto 1, 1 \mapsto 2, 2 \mapsto 3\}\) 的函数。

具体来说，您需要实现以下函数：

def fn_empty():
    """Return an empty function.

    >>> fn_empty()
    []
    """
    "*** YOUR CODE HERE ***"


def fn_remap(fn, x, y):
    """Return a new function that is the same as fn except that it maps x to y.

    >>> f = fn_remap(fn_empty(), 1, 2)
    >>> f
    [[1, 2]]
    >>> fn_remap(f, 1, 3)
    [[1, 3]]
    >>> fn_remap(f, 2, 3)
    [[1, 2], [2, 3]]
    """
    "*** YOUR CODE HERE ***"


def fn_domain(fn):
    """Return a sorted list of all the inputs (domain) of fn.
    Note that if fn maps x to None, then x is not in the domain of fn.

    >>> fn_domain(fn_remap(fn_remap(fn_empty(), 1, 2), 2, 3))
    [1, 2]
    >>> fn_domain(fn_remap(fn_remap(fn_empty(), 2, 3), 1, 2))
    [1, 2]
    >>> fn_domain(fn_empty())
    []
    >>> fn_domain(fn_remap(fn_empty(), 1, None))
    []
    """
    "*** YOUR CODE HERE ***"


def fn_call(fn, x):
    """Return the result of applying fn to x.
    If fn does not map x to a value, return None.

    >>> fn_call(fn_remap(fn_empty(), 1, 2), 1)
    2
    >>> fn_call(fn_remap(fn_remap(fn_empty(), 1, 2), 2, 3), 2)
    3
    >>> fn_call(fn_remap(fn_remap(fn_empty(), 1, 2), 2, 3), 1)
    2
    >>> fn_call(fn_empty(), 1) is None
    True
    """
    "*** YOUR CODE HERE ***"

Hints

Hint:

You may need to use deepcopy in fn_remap to avoid modifying the original function. Also, you may need sorted in fn_domain to return the domain in sorted order. For example,

>>> sorted([3, 1, 2])
[1, 2, 3]
>>> a = [[1, 2]]
>>> b = deepcopy(a)
>>> b[0] = 1
>>> a
[[1, 2]]
>>> b
[1]

  • 您可能需要在 fn_remap 中使用 deepcopy 以避免修改原始函数。

  • 此外，您可能需要在 fn_domain 中使用 sorted 以返回排序后的定义域（domain）。

Solutions

Generated by AI.

fn_empty 别想多了。

def fn_empty():
    return []

对于 fn_remap，注意不要改变 fn 元素的顺序。

def fn_remap(fn, x, y):
    ans = []
    # 遍历 fn 中的每一对 x, y
    for pair in fn:
        # 如果 x 重复
        if (pair[0] == x):
            # 添加修改后的 x, y
            ans.append([x, y])
        else:
            # 添加原有的 x, y
            ans.append(pair)
    # 判断是否需要额外加上 x, y
    if [x, y] in ans:
        return ans
    else:
        return ans + [[x, y]]

遍历有函数值的 x，然后使用 sorted 排序。

def fn_domain(fn):
    return sorted([pair[0] for pair in fn if pair[1] is not None])
    # 也可以写作 [pair[0] for pair in fn if pair[1]]

遍历所有 x, y，当找到 x 时输出 y。

def fn_call(fn, x):
    for pair in fn:
        if pair[0] == x:
            return y
    return None

压行（损失效率）

def fn_remap(fn, x, y):
    return a if (a := [(i if i[0] != x else [x, y]) for i in fn]) and [x, y] in a else a + [[x, y]]

def fn_call(fn, x):
    return y[0] if (y := [i[1] for i in fn if i[0] == x]) else None