Homework 2: Higher-Order Functions

约 2192 字大约 7 分钟

CS61ABerkeleyPython

2024-11-11

Instructions

下载 hw02.zip。在存档中，您将找到一个名为 hw02.py 的文件，以及 ok 自动评分器的副本。

如果官方链接失效，你也可以通过我的 github 仓库 CS61A_Fall2024来获取我的代码。

重要

请注意，该代码包含答案，因此如果你想独立完成请务必提前将 hw02.py 中的答案删除！

提交：完成后，通过将您编辑的所有代码文件上传到 Gradescope 来提交作业。您可以在截止日期前多次提交；只有最后一次提交才会被评分。检查您是否已成功在 Gradescope 上提交了代码。有关提交作业的更多说明，请参阅实验 0。

使用 Ok：如果您对使用 Ok 有任何疑问，请参阅本指南。

阅读材料：您可能会发现以下参考资料很有用：

第 1.6 节评分：作业根据正确性进行评分。每个错误的问题都会使总分减少一分。这项作业满分为 2 分。

Required Questions

几个文档测试引用了这些功能：

from operator import add, mul

square = lambda x: x * x

identity = lambda x: x

triple = lambda x: 3 * x

increment = lambda x: x + 1

Higher-Order Functions

Q1: Product

编写一个名为 product 的函数，返回序列前 n 个项的乘积。具体来说， product 接受整数 n 和 term ，后者是一个确定序列的单参数函数。（也就是说， term(i) 给出序列的第 i 个项。） product(n, term) 应该返回 term(1) * ... * term(n) 。

def product(n, term):
    """Return the product of the first n terms in a sequence.

    n: a positive integer
    term:  a function that takes one argument to produce the term

    >>> product(3, identity)  # 1 * 2 * 3
    6
    >>> product(5, identity)  # 1 * 2 * 3 * 4 * 5
    120
    >>> product(3, square)    # 1^2 * 2^2 * 3^2
    36
    >>> product(5, square)    # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
    14400
    >>> product(3, increment) # (1+1) * (2+1) * (3+1)
    24
    >>> product(3, triple)    # 1*3 * 2*3 * 3*3
    162
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python ok -q product

点击查看答案

def product(n, term):
    """Return the product of the first n terms in a sequence.

    n: a positive integer
    term:  a function that takes one argument to produce the term

    >>> product(3, identity)  # 1 * 2 * 3
    6
    >>> product(5, identity)  # 1 * 2 * 3 * 4 * 5
    120
    >>> product(3, square)    # 1^2 * 2^2 * 3^2
    36
    >>> product(5, square)    # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
    14400
    >>> product(3, increment) # (1+1) * (2+1) * (3+1)
    24
    >>> product(3, triple)    # 1*3 * 2*3 * 3*3
    162
    """
    "*** YOUR CODE HERE ***"
    res = 1
    i = 1
    while i <= n:
        res  *= term(i)
        i += 1
    return res

Q2: Accumulate

让我们看一下 product 是如何成为我们想要实现的更通用的 accumulate 函数的一个实例的：

def accumulate(fuse, start, n, term):
    """Return the result of fusing together the first n terms in a sequence 
    and start.  The terms to be fused are term(1), term(2), ..., term(n). 
    The function fuse 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 (fuse is never used)
    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
    >>> # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1)
    >>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
    19
    """
    "*** YOUR CODE HERE ***"

accumulate 具有以下参数：

fuse ：一个双参数函数，指定当前项如何与先前累积的项融合
start ：开始累积的值
n ：一个非负整数，表示要融合的项数
term ：一个单参数函数；term(i) 是序列的第 i 个项实现 accumulate ，使用 fuse 函数将 term 定义的序列的前 n 个项与 start 值融合。

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

add(11,  add(square(1), add(square(2),  square(3)))) =
    11 +     square(1) +    square(2) + square(3)    =
    11 +     1         +    4         + 9            = 25

假设 fuse 是可交换的， fuse(a, b) == fuse(b, a) ，并且是结合的， fuse(fuse(a, b), c) == fuse(a, fuse(b, c)) 。

然后，将 summation （来自讲座）和 product 实现为一行调用以进行 accumulate 。

提示

summation_using_accumulate 和 product_using_accumulate 都应使用以 return 开头的一行代码来实现。

def summation_using_accumulate(n, term):
    """Returns the sum: term(1) + ... + term(n), using accumulate.

    >>> summation_using_accumulate(5, square) # square(1) + square(2) + ... + square(4) + square(5)
    55
    >>> summation_using_accumulate(5, triple) # triple(1) + triple(2) + ... + triple(4) + triple(5)
    45
    >>> # This test checks that the body of the function is just a return statement.
    >>> import inspect, ast
    >>> [type(x).__name__ for x in ast.parse(inspect.getsource(summation_using_accumulate)).body[0].body]
    ['Expr', 'Return']
    """
    return ____

def product_using_accumulate(n, term):
    """Returns the product: term(1) * ... * term(n), using accumulate.

    >>> product_using_accumulate(4, square) # square(1) * square(2) * square(3) * square()
    576
    >>> product_using_accumulate(6, triple) # triple(1) * triple(2) * ... * triple(5) * triple(6)
    524880
    >>> # This test checks that the body of the function is just a return statement.
    >>> import inspect, ast
    >>> [type(x).__name__ for x in ast.parse(inspect.getsource(product_using_accumulate)).body[0].body]
    ['Expr', 'Return']
    """
    return ____

使用 Ok 来测试你的代码：

python ok -q accumulate
python ok -q summation_using_accumulate
python ok -q product_using_accumulate

点击查看答案

def accumulate(fuse, start, n, term):
    """Return the result of fusing together the first n terms in a sequence 
    and start.  The terms to be fused are term(1), term(2), ..., term(n). 
    The function fuse 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 (fuse is never used)
    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
    >>> # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1)
    >>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
    19
    """
    "*** YOUR CODE HERE ***"
    res = start 
    i = 1
    while i <= n:
        res = fuse(res, term(i))
        i += 1
    return res

点击查看答案

def summation_using_accumulate(n, term):
    """Returns the sum: term(1) + ... + term(n), using accumulate.

    >>> summation_using_accumulate(5, square) # square(1) + square(2) + ... + square(4) + square(5)
    55
    >>> summation_using_accumulate(5, triple) # triple(1) + triple(2) + ... + triple(4) + triple(5)
    45
    >>> # This test checks that the body of the function is just a return statement.
    >>> import inspect, ast
    >>> [type(x).__name__ for x in ast.parse(inspect.getsource(summation_using_accumulate)).body[0].body]
    ['Expr', 'Return']
    """
    return accumulate(add, 0, n, term)


def product_using_accumulate(n, term):
    """Returns the product: term(1) * ... * term(n), using accumulate.

    >>> product_using_accumulate(4, square) # square(1) * square(2) * square(3) * square()
    576
    >>> product_using_accumulate(6, triple) # triple(1) * triple(2) * ... * triple(5) * triple(6)
    524880
    >>> # This test checks that the body of the function is just a return statement.
    >>> import inspect, ast
    >>> [type(x).__name__ for x in ast.parse(inspect.getsource(product_using_accumulate)).body[0].body]
    ['Expr', 'Return']
    """
    return accumulate(mul, 1, n, term)

实现 make_repeater 函数，该函数接受一个参数函数 f 和一个正整数 n 。它返回一个参数函数，其中 make_repeater(f, n)(x) 返回 f(f(...f(x)...)) 的值，其中 f 被应用到 x n 次。例如，make_repeater(square, 3)(5) 将 5 的平方计算三次并返回 390625，就像 square(square(square(5))) 一样。

def make_repeater(f, n):
    """Returns the function that computes the nth application of f.

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    8
    >>> make_repeater(triple, 5)(1) # 3 * (3 * (3 * (3 * (3 * 1))))
    243
    >>> make_repeater(square, 2)(5) # square(square(5))
    625
    >>> make_repeater(square, 3)(5) # square(square(square(5)))
    390625
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python ok -q make_repeater

点击查看答案

def make_repeater(f, n):
    """Returns the function that computes the nth application of f.

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    8
    >>> make_repeater(triple, 5)(1) # 3 * (3 * (3 * (3 * (3 * 1))))
    243
    >>> make_repeater(square, 2)(5) # square(square(5))
    625
    >>> make_repeater(square, 3)(5) # square(square(square(5)))
    390625
    """
    "*** YOUR CODE HERE ***"
    def repeater(x):
        i = 0
        res = x 
        while i < n:
            res = f(res)
            i += 1
        return res 
    return repeater

Check Your Score Locally

您可以通过运行来在本地检查此作业的每个问题的分数：

python ok --score

我的得分：

PS D:\Github\CS61A_Fall2024\hw\hw02> python ok --score 
=====================================================================
Assignment: Homework 2
OK, version v1.18.1
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Scoring tests

---------------------------------------------------------------------
Doctests for product

>>> from hw02 import *
>>> product(3, identity)  # 1 * 2 * 3
6
>>> product(5, identity)  # 1 * 2 * 3 * 4 * 5
120
>>> product(3, square)    # 1^2 * 2^2 * 3^2
36
>>> product(5, square)    # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
14400
>>> product(3, increment) # (1+1) * (2+1) * (3+1)
24
>>> product(3, triple)    # 1*3 * 2*3 * 3*3
162
Score: 1.0/1

---------------------------------------------------------------------
Doctests for accumulate

>>> from hw02 import *
>>> 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 (fuse is never used)
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
>>> # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1)
>>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
19
Score: 1.0/1

---------------------------------------------------------------------
Doctests for summation_using_accumulate

>>> from hw02 import *
>>> summation_using_accumulate(5, square) # square(1) + square(2) + ... + square(4) + square(5)
55
>>> summation_using_accumulate(5, triple) # triple(1) + triple(2) + ... + triple(4) + triple(5)
45
>>> # This test checks that the body of the function is just a return statement.
>>> import inspect, ast
>>> [type(x).__name__ for x in ast.parse(inspect.getsource(summation_using_accumulate)).body[0].body]
['Expr', 'Return']
Score: 1.0/1

---------------------------------------------------------------------
Doctests for product_using_accumulate

>>> from hw02 import *
>>> product_using_accumulate(4, square) # square(1) * square(2) * square(3) * square()
576
>>> product_using_accumulate(6, triple) # triple(1) * triple(2) * ... * triple(5) * triple(6)
524880
>>> # This test checks that the body of the function is just a return statement.
>>> import inspect, ast
>>> [type(x).__name__ for x in ast.parse(inspect.getsource(product_using_accumulate)).body[0].body]
['Expr', 'Return']
Score: 1.0/1

---------------------------------------------------------------------
Doctests for make_repeater

>>> from hw02 import *
>>> add_three = make_repeater(increment, 3)
>>> add_three(5)
8
>>> make_repeater(triple, 5)(1) # 3 * (3 * (3 * (3 * (3 * 1))))
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 3)(5) # square(square(square(5)))
390625
Score: 1.0/1

---------------------------------------------------------------------
Point breakdown
    product: 1.0/1
    accumulate: 1.0/1
    summation_using_accumulate: 1.0/1
    product_using_accumulate: 1.0/1
    make_repeater: 1.0/1

Score:
    Total: 5.0

Backup... 100% complete
Backup past deadline by 186 days, 18 hours, 13 minutes, and 11 seconds
Backup successful for user: zhiyong947@gmail.com
URL: https://okpy.org/cal/cs61a/fa24/hw02/backups/jLYx7y

OK is up to date
PS D:\Github\CS61A_Fall2024\hw\hw02>

这不会提交作业！当您对分数满意时，请将作业提交给 Gradescope 以获得学分。

Homework 2: Higher-Order Functions

Instructions

Required Questions

Higher-Order Functions

Q1: Product

Q2: Accumulate

Q3: Make Repeater

Check Your Score Locally