Homework 2 | CS 61A Spring 2024
Homework 2: Higher-Order Functions
Due by 11:59pm on Thursday, February 1
截止日期为 2 月 1 日（星期四）晚上 11:59
Instructions 指令
Download hw02.zip. Inside the archive, you will find a file called hw02.py, along with a copy of the ok autograder.
下载 hw02.zip。压缩包内包含一个名为 hw02.py 的文件，以及一份 ok 自动评分器的副本。
Submission: When you are done, submit the assignment by uploading all code files you've edited to Gradescope. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on Gradescope. See Lab 0 for more instructions on submitting assignments.
提交：完成后，通过将您编辑的所有代码文件上传到 Gradescope 提交作业。您可以在截止日期之前提交多次；只有最终提交会被评分。请检查您是否已成功在 Gradescope 上提交了代码。有关提交作业的更多说明，请参见实验 0。
Using Ok: If you have any questions about using Ok, please refer to this guide.
使用 Ok：如果您对使用 Ok 有任何疑问，请参考本指南。
Readings: You might find the following references useful:
阅读材料：您可能会发现以下参考资料有用：
Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. This homework is out of 2 points.
评分：作业的评分基于正确性。每个错误的问题将使总分减少一分。此作业满分为 2 分。
Required Questions 必填问题
Getting Started Videos 入门视频
These videos may provide some helpful direction for tackling the coding problems on this assignment.
这些视频可能为解决此作业中的编码问题提供一些有用的指导。
To see these videos, you should be logged into your berkeley.edu email.
要查看这些视频，您应该登录到您的 berkeley.edu 邮箱。
Several doctests refer to these functions:
多个 doctest 参考了这些函数：
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
Write a function called product that returns the product of the first n terms of a sequence. Specifically, product takes in an integer n and term, a single-argument function that determines a sequence. (That is, term(i) gives the ith term of the sequence.) product(n, term) should return term(1) * ... * term(n).
编写一个名为 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 ***"
Use Ok to test your code:
使用 Ok 来测试您的代码：
python3 ok -q product
Q2: Accumulate
Let's take a look at how product is an instance of a more general function called accumulate, which we would like to implement:
让我们来看看 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 has the following parameters:
accumulate 具有以下参数：
fuse: a two-argument function that specifies how the current term is fused with the previously accumulated terms
fuse: 一个具有两个参数的函数，指定当前项如何与之前累积的项融合start: value at which to start the accumulation
start: 开始累积的值n: a non-negative integer indicating the number of terms to fuse
n: 一个非负整数，表示要融合的项数term: a single-argument function;term(i)is theith term of the sequence
term：一个单参数函数；term(i)是序列的第i项
Implement accumulate, which fuses the first n terms of the sequence defined by term with the start value using the fuse function.
实现 accumulate ，它将由 term 定义的序列的前 n 项与 start 值使用 fuse 函数融合。
For example, the result of accumulate(add, 11, 3, square) is
例如， 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
Assume that
fuseis commutative,fuse(a, b) == fuse(b, a), and associative,fuse(fuse(a, b), c) == fuse(a, fuse(b, c)).
假设fuse是可交换的，fuse(a, b) == fuse(b, a)，并且是结合的，fuse(fuse(a, b), c) == fuse(a, fuse(b, c))。
Then, implement summation (from lecture) and product as one-line calls to accumulate.
然后，将 summation （来自讲座）和 product 实现为对 accumulate 的一行调用。
Important: Both summation_using_accumulate and product_using_accumulate should be implemented with a single line of code starting with return.
重要提示： 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)
55
>>> summation_using_accumulate(5, triple)
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)
576
>>> product_using_accumulate(6, triple)
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 ____
Use Ok to test your code:
使用 Ok 来测试您的代码：
python3 ok -q accumulate
python3 ok -q summation_using_accumulate
python3 ok -q product_using_accumulate
Q3: Make Repeater
Implement the function make_repeater that takes a one-argument function f and a positive integer n. It returns a one-argument function, where make_repeater(f, n)(x) returns the value of f(f(...f(x)...)) in which f is applied n times to x. For example, make_repeater(square, 3)(5) squares 5 three times and returns 390625, just like square(square(square(5))).
实现函数 make_repeater ，该函数接受一个单参数函数 f 和一个正整数 n 。它返回一个单参数函数，其中 make_repeater(f, n)(x) 返回在 f 应用 n 次于 x 的 f(f(...f(x)...)) 的值。例如， 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 ***"
Use Ok to test your code:
使用 Ok 来测试您的代码：
python3 ok -q make_repeater
Check Your Score Locally
You can locally check your score on each question of this assignment by running
您可以通过运行来在本地检查此作业每个问题的分数
python3 ok --score
This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.
这并不会提交作业！当您对自己的分数满意时，请将作业提交到 Gradescope 以获得学分。
Submit 提交
Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.
通过将您编辑的任何文件上传到相应的 Gradescope 作业来提交此作业。实验 00 有详细的说明。
In addition, all students who are not in the mega lab must complete this attendance form. Submit this form each week, whether you attend lab or missed it for a good reason. The attendance form is not required for mega section students.
此外，所有不在大型实验室的学生必须填写此考勤表。无论您是否参加实验室，或因正当理由缺席，每周都需提交此表格。大型部分的学生不需要填写考勤表。
Exam Practice
Here are some related questions from past exams for you to try. These are optional. There is no way to submit them.
以下是一些来自过去考试的相关问题供您尝试。这些是可选的。无法提交它们。
Note that exams from Spring 2020, Fall 2020, and Spring 2021 gave students access to an interpreter, so the question format may be different than other years. Regardless, the questions below are good problems to try without access to an interpreter.
请注意，2020 年春季、2020 年秋季和 2021 年春季的考试为学生提供了一个解释器，因此问题格式可能与其他年份不同。无论如何，下面的问题都是在没有访问解释器的情况下尝试的好题目。
- Fall 2019 MT1 Q3: You Again [Higher-Order Functions]
2019 年秋季 MT1 Q3: 你又来了 [高阶函数] - Spring 2021 MT1 Q4: Domain on the Range [Higher-Order Functions]
春季 2021 MT1 Q4：范围上的域 [高阶函数] - Fall 2021 MT1 Q1b: tik [Functions and Expressions]
秋季 2021 MT1 Q1b: tik [函数和表达式]