Skip to content

Problem 6: Multiadder (100pts)

Problem

We call a pure function 1-order numeric function if it takes in a number and returns a number.For example, abs(x) is a 1-order numeric function that returns the absolute value of x.

If a function takes in a number and returns an 1-order numeric function, then we call it a 2-order numeric function. Similarly, if a function takes in a number and returns a 2-order numeric function, then we call it a 3-order numeric function. An n-order numeric function is a function that takes in a number and returns an (n-1)-order numeric function.

For an n-order numeric function f, we can obtain a numeric result by giving it n arguments in a call expression. For example, if f is 4-order numeric, then f(2)(0)(2)(5) should give us a number. Here we call 2, 0, 2, 5, in the order they appear in the call expression, the argument sequence of the call expression.

Implement function multiadder, such that:

  1. multiadder takes in a positive integer n
  2. multiadder returns an n-order numeric function
  3. Providing any argument sequence of length n to multiadder(n) gives the sum of the argument sequence. For example, multiadder(4) should return a 4-order numeric function, and multiadder(4)(2)(0)(2)(5) should be 9, which is the sum of 2, 0, 2, 5.

如果一个纯函数接受一个数字并返回一个数字，我们称它为“1 阶数值函数”。 例如，abs(x) 是一个 1 阶数值函数，返回 x 的绝对值。

如果一个函数接受一个数字并返回一个 1 阶数值函数，那么我们称它为 2 阶数值函数。 类似地，如果一个函数接受一个数字并返回一个 2 阶数值函数，那么我们称它为 3 阶数值函数。 一个 n 阶数值函数是一个接受一个数字并返回一个（n-1）阶数值函数的函数。

对于一个 n 阶数值函数 f，我们可以通过在调用表达式中提供 n 个参数来获得一个数值结果。 例如，如果 f 是 4 阶数值函数，那么 f(2)(0)(2)(5) 应该给我们一个数字。 在这里，我们称 2, 0, 2, 5（按它们在调用表达式中出现的顺序）为该调用表达式的参数序列。

实现函数 multiadder，使得：

  1. multiadder 接受一个正整数 n
  2. multiadder 返回一个n 阶数值函数
  3. 向 multiadder(n) 提供任何长度为 n 的参数序列会得到该参数序列的和。 例如，multiadder(4) 应该返回一个4 阶数值函数，而 multiadder(4)(2)(0)(2)(5) 应该是 9，即 2, 0, 2, 5 的和。
def multiadder(n):
    """Return a function that takes N arguments, one at a time, and adds them.

    >>> f = multiadder(3)
    >>> f(5)(6)(7) # 5 + 6 + 7
    18
    >>> multiadder(1)(5)
    5
    >>> multiadder(2)(5)(6) # 5 + 6
    11
    >>> multiadder(4)(5)(6)(7)(8) # 5 + 6 + 7 + 8
    26
    >>> from construct_check import check
    >>> # Make sure multiadder is a pure function.
    >>> check(HW_SOURCE_FILE, 'multiadder',
    ...       ['Nonlocal', 'Global'])
    True
    """
    "*** YOUR CODE HERE ***"

Hints

  • Hint1: Where does the recursion happen? What is the base case?
  • Hint2: It is guaranteed that n >= 1

  • 递归发生在何处？基本情况是什么？

  • 始终有 n >= 1

  • 你可能需要一个辅助函数，可以增加一个参数，用来记录你要输出的结果。

Solutions

我们可以增加一个参数来记录输出的和。

定义一个辅助函数，在接受全部参数前返回一个函数。

def multiadder(n):
    def helper(k, sum):
        """
        k: 还需要接收的参数个数
        sum: 当前已接收参数的累加和
        """
        # 接受全部参数后，返回和
        if k == 0:
            return sum
        # 接受下一个参数，剩余参数 -1，同时增加和
        else:
            return lambda x: helper(k - 1, sum + x)

    # 共需接受 n 个参数，初始的和为 0
    return helper(n, 0)