Problem 3: Accumulate (200pts)

Problem

Let's take a look at how summation and product are instances of a more general function called accumulate:

让我们看看 summation 和 product 是如何成为一个更通用函数 accumulate 的特例的：

def accumulate(combiner, base, n, f):
    """Return the result of combining the first n terms in a sequence and base.
    The terms to be combined are f(1), f(2), ..., f(n).  combiner is a
    two-argument commutative, associative function.

    >>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
    15
    >>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
    26
    >>> accumulate(add, 11, 0, identity) # 11
    11
    >>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
    25
    >>> accumulate(mul, 2, 3, square)    # 2 * 1^2 * 2^2 * 3^2
    72
    >>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
    19
    >>> accumulate(lambda x, y: (x + y) % 17, 19, 20, square)
    16
    """
    "*** YOUR CODE HERE ***"

accumulate has the following parameters:

f and n: the same parameters as in summation and product

combiner: a two-argument function that specifies how the current term is combined with the previously accumulated terms.

base: value at which to start the accumulation.

For example, the result of accumulate(add, 11, 3, square) is

11 + square(1) + square(2) + square(3) = 25

Note: You may assume that combiner is associative and commutative. That is, combiner(a, combiner(b, c)) == combiner(combiner(a, b), c) and combiner(a, b) == combiner(b, a) for all a, b, and c. However, you may not assume combiner is chosen from a fixed function set and hard-code the solution.

After implementing accumulate, show how summation and product can both be defined as simple calls to accumulate:

accumulate 具有以下参数：

f 和 n：与 summation 和 product 中相同的参数。
combiner：一个双参数函数，指定如何将当前项与先前累积的项组合起来。
base：开始累积时的初始值。

例如，accumulate(add, 11, 3, square) 的结果是

11 + square(1) + square(2) + square(3) = 25

注意：您可以假设 combiner 是可结合和可交换的。也就是说，对于所有的 \(a, b, c\)，combiner(a, combiner(b, c)) == combiner(combiner(a, b), c) 且 combiner(a, b) == combiner(b, a)。但是，您不能假设 combiner 是从一个固定函数集中选取的，并对解决方案进行硬编码。

在实现 accumulate 之后，展示如何将 summation 和 product 都定义为对 accumulate 的简单调用：

def summation_using_accumulate(n, f):
    """Returns the sum of f(1) + ... + f(n). The implementation
    uses accumulate.

    >>> summation_using_accumulate(5, square)
    55
    >>> summation_using_accumulate(5, triple)
    45
    >>> from construct_check import check
    >>> # ban iteration and recursion
    >>> check('hw02.py', 'summation_using_accumulate',
    ...       ['Recursion', 'For', 'While'])
    True
    """
    return _______


def product_using_accumulate(n, f):
    """An implementation of product using accumulate.

    >>> product_using_accumulate(4, square)
    576
    >>> product_using_accumulate(6, triple)
    524880
    >>> from construct_check import check
    >>> # ban iteration and recursion
    >>> check('hw02.py', 'product_using_accumulate',
    ...       ['Recursion', 'For', 'While'])
    True
    """
    return _______

Hints

注意 accumulate 函数当 n == 0 时应直接返回 base
后两个函数中应调用 add 和 mul 函数

Solutions

使用 while 循环

def accumulate(combiner, base, n, f):
# 初始化累积结果为 base 值
    result = base

    # 计数器/项数索引 k，从序列的第一项 k=1 开始
    k = 1

    # 使用 while 循环，从 k=1 迭代到 k=n
    while k <= n:
        # 1. 计算当前项的值：f(k)
        current_term = f(k)

        # 2. 使用 combiner 函数将当前项 current 组合到 result 中
        # 新的 result = combiner(旧的 result, 当前项)
        result = combiner(result, current)

        # 3. 递增 k，移至序列的下一项
        k = k + 1

    # 循环结束后，result 就是 base 与所有 f(k) 组合的结果
    return result

def summation_using_accumulate(n, f):
    return accumulate(add, 0, n, f)

def product_using_accumulate(n, f):
    return accumulate(mul, 1, n, f)

accumulate 函数可以使用递归来实现。（压行）

def accumulate(combiner, base, n, f):
    return base if n == 0 else combiner(accumulate(combiner, base, n - 1, f), f(n))