Problem 1: Functions (500pts)

Essentially, a function is a set of ordered pairs, where the first element of each pair is called the input and the second element is called the output. For example, a function \(f\) can be defined as \(\{0 \mapsto 1, 1 \mapsto 2, 2 \mapsto 3, \cdots\}\), which is an increment function that adds 1 to its input.

In this problem:

• You first need to implement an abstract data type (ADT) for functions using lists of pairs, simulating the behavior of an actual function.
• After that, the evil TA will come and replace your list implementation with a different one, keeping the same abstract interface but breaking everything inside. Then, you should only work with the abstract interface to solve some harder problems.

Note that in this problem, we only consider functions on integers, i.e., both inputs and outputs of the functions are integers.

本质上，一个函数是一个有序对的集合，其中每个对的第一个元素称为输入，第二个元素称为输出。 例如，函数 \(f\) 可以定义为 \(\{0 \mapsto 1, 1 \mapsto 2, 2 \mapsto 3, \cdots\}\)，这是一个对输入加 1 的增量函数。

在这个问题中：

• 您首先需要使用列表来实现一个用于函数的抽象数据类型 (ADT)，其中列表存储输入-输出对，以模拟实际函数的行为。
• 之后，邪恶的助教会介入，用不同的实现来替换您的列表实现，同时保持相同的抽象接口，但会破坏内部的一切。 届时，您应该只使用抽象接口来解决一些更困难的问题。

请注意，在本问题中，我们只考虑定义在整数上的函数，即函数的输入和输出都是整数。