实验 2：高阶函数与 Lambda 表达式

截止时间：6 月 30 日（星期二）晚上 11:59。

起始文件

下载 lab02.zip.

出勤要求

要获得实验课学分，除了到场参加实验课外，你还需要提交实验题目。

如果你因合理原因（例如生病或时间冲突）缺席实验课，或者由于某种原因未能完成签到，请在一周内发送邮件至 cs61a@berkeley.edu ，以补记出勤学分。

主题

如果需要复习本实验涉及的知识，可以阅读这一部分。你也可以直接跳到 题目部分 ，遇到困难时再回来查阅。

短路求值

你认为把下面的内容输入 Python 后会发生什么？

1 / 0

在 Python 中试一试！你应该会看到一个 ZeroDivisionError。那么下面这个表达式呢？

True or 1 / 0

它的求值结果是 True ，这是因为 Python 的 and 和 or 运算符会进行 短路求值。也就是说，它们不一定会对每个操作数都求值。

运算符 检查条件： 从左向右求值，直到： 示例
与（AND） 所有值都为真 遇到第一个假值 False and 1 / 0 求值结果为 False
或（OR） 至少有一个值为真 遇到第一个真值 True or 1 / 0 求值结果为 True

当运算符遇到一个足以确定整个表达式结果的操作数时，就会发生短路求值。例如， and 一遇到第一个假值就会停止求值，因为此时已经能确定并非所有值都为真。

如果 and 和 or 没有 短路求值发生短路，它们就返回最后一个值。也可以这样记： and 和 or 总是返回自己最后求值的那个对象，无论是否发生短路。请注意，使用除 and 和 or 以外的值时，它们的返回值不一定是布尔值。 True 和 False.

高阶函数

变量是绑定到值的名称。值既可以是像 3 或 'Hello World'这样的基本值，也可以是函数。由于函数的参数可以是任意值，其他函数也能作为参数传入；这正是高阶函数的基础。

高阶函数是能够操作其他函数的函数：它可以接收函数作为参数、返回一个函数，或同时做到两者。本实验将介绍高阶函数的基础，下一个实验会进一步探索它的多种应用。

函数作为参数

在 Python 中，函数对象也是值，因此可以在程序中传递。我们已经知道，可以使用 def 语句创建函数：

def square(x):
    return x * x

上面的语句创建了一个内部名称为 square 的函数对象，同时把它绑定到当前环境中的名称 square 。现在来试试把它作为参数传递。

首先编写一个接收另一个函数作为参数的函数：

def scale(f, x, k):
    """ Returns the result of f(x) scaled by k. """
    return k * f(x)

现在可以调用 scale ，向它传入 square 以及其他参数：

>>> scale(square, 3, 2) # Double square(3)
18
>>> scale(square, 2, 5) # 5 times 2 squared
20

请注意，在对 scale的调用体中，内部名称为 square 的函数对象被绑定到形参 f。随后，我们在 square 的函数体中调用 scale ，调用方式是 f(x).

正如上面关于 lambda 表达式的一节所示，我们也可以把 lambda 表达式直接传入调用表达式！

>>> scale(lambda x: x + 10, 5, 2)
30

在这个调用表达式对应的帧中，名称 f 绑定到由 lambda 表达式创建的函数。 lambda x: x + 10.

返回函数的函数

函数既然是值，自然也可以作为返回值。下面来看一个例子：

def multiply_by(m):
    def multiply(n):
        return n * m
    return multiply

在这个例子中，我们在 multiply 的函数体内定义了函数 multiply_by ，随后将其返回。来看看实际效果：

>>> multiply_by(3)
<function multiply_by.<locals>.multiply at ...>
>>> multiply(4)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'multiply' is not defined

调用 multiply_by 确实会返回一个函数。但直接调用 multiply 却会报错，尽管这是我们给内部函数取的名字。原因是名称 multiply 只存在于执行 multiply_by.

那么该怎样使用这个内部函数呢？有两种方式：

>>> times_three = multiply_by(3) # Assign the result of the call expression to a name
>>> times_three(5) # Call the inner function with its new name
15
>>> multiply_by(3)(10) # Chain together two call expressions
30

关键在于，既然 multiply_by 返回的是函数，就可以像使用任何其他函数一样使用它的返回值。

YouTube 视频链接


Lambda 表达式

Lambda 表达式通过指定参数和返回表达式这两部分内容，求值得到一个函数。

lambda <parameters>: <return expression>

虽然 lambda 表达式和 def 语句都能创建函数对象，但二者存在一些重要区别。 lambda 表达式与其他表达式的工作方式相同：数学表达式只会求值得到一个数，不会改变当前环境；类似地， lambda 表达式会求值得到一个函数，但不会改变当前环境。下面仔细比较一下。

lambda def
类型 表达式 ，会求值得到一个值。 语句 ，会改变环境。
执行结果 创建一个没有内部名称的匿名 lambda 函数。 创建一个带有内部名称的函数，并在当前环境中把它绑定到该名称。
对环境的影响 对 lambda 表达式求值 不会 创建或修改任何变量。 执行 def 语句既会创建新的函数对象， 和 也会把它绑定到当前环境中的一个名称。
用法 lambda 表达式可以用在任何需要表达式的位置，例如赋值语句中，或作为调用表达式的运算符、操作数。 执行 def 语句后，新函数会绑定到一个名称。在需要表达式的地方，应使用这个名称来引用该函数。
示例 
# A lambda expression by itself does not alter
# the environment
lambda x: x * x

# We can assign lambda functions to a name
# with an assignment statement
square = lambda x: x * x
square(3)

# Lambda expressions can be used as an operator
# or operand
negate = lambda f, x: -f(x)
negate(lambda x: x * x, 3)
 
def square(x):
    return x * x

# A function created by a def statement
# can be referred to by its intrinsic name
square(3)

YouTube 视频链接

必做题

Python 会显示什么？

Important: 对于所有 WWPD 题，如果你认为答案是 Function ，请输入 <function...>, Error ；如果会报错，输入 Nothing ；如果没有任何显示，则输入

问题 1：WWPD——真值终将胜出

使用 Ok 完成下面的“Python 会显示什么？”（WWPD）题，检查你对知识的掌握情况：

python3 ok -q short-circuit -u

>>> True and 13

______
13

>>> False or 0

______
0

>>> not 10

______
False

>>> not None

______
True
>>> True and 1 / 0

______
Error (ZeroDivisionError)

>>> True or 1 / 0

______
True

>>> -1 and 1 > 0

______
True

>>> -1 or 5

______
-1

>>> (1 + 1) and 1

______
1

>>> print(3) or ""

______
3
''
>>> def f(x):
...     if x == 0:
...         return "zero"
...     elif x > 0:
...         return "positive"
...     else:
...         return ""
>>> 0 or f(1)

______
'positive'

>>> f(0) or f(-1)

______
'zero'

>>> f(0) and f(-1)

______
''

问题 2：WWPD——高阶函数

使用 Ok 完成下面的“Python 会显示什么？”（WWPD）题，检查你对知识的掌握情况：

python3 ok -q hof-wwpd -u

>>> def cake():
...    print('beets')
...    def pie():
...        print('sweets')
...        return 'cake'
...    return pie
>>> chocolate = cake()

______
beets

>>> chocolate

______
Function

>>> chocolate()

______
sweets
'cake'

>>> more_chocolate, more_cake = chocolate(), cake

______
sweets

>>> more_chocolate

______
'cake'

>>> def snake(x, y):
...    if cake == more_cake:
...        return chocolate
...    else:
...        return x + y
>>> snake(10, 20)

______
Function

>>> snake(10, 20)()

______
sweets
'cake'

>>> cake = 'cake'
>>> snake(10, 20)

______
30

问题 3：WWPD——Lambda

使用 Ok 完成下面的“Python 会显示什么？”（WWPD）题，检查你对知识的掌握情况：

python3 ok -q lambda -u


提醒一下：在交互式 Python 解释器中执行下面两行代码时，不会显示任何输出： 
>>> x = None
>>> x
>>>
>>> lambda x: x  # A lambda expression with one parameter x

______
<function <lambda> at ...>

>>> a = lambda x: x  # Assigning the lambda function to the name a
>>> a(5)

______
5

>>> (lambda: 3)()  # Using a lambda expression as an operator in a call expression.

______
3

>>> b = lambda x, y: lambda: x + y  # Lambdas can return other lambdas!
>>> c = b(8, 4)
>>> c

______
<function <lambda> at ...

>>> c()

______
12

>>> d = lambda f: f(4)  # They can have functions as arguments as well.
>>> def square(x):
...     return x * x
>>> d(square)

______
16
>>> higher_order_lambda = lambda f: lambda x: f(x)
>>> g = lambda x: x * x
>>> higher_order_lambda(2)(g)  # Which argument belongs to which function call?

______
Error

>>> higher_order_lambda(g)(2)

______
4

>>> call_thrice = lambda f: lambda x: f(f(f(x)))
>>> call_thrice(lambda y: y + 1)(0)

______
3

>>> print_lambda = lambda z: print(z)  # When is the return expression of a lambda expression executed?
>>> print_lambda

______
Function

>>> one_thousand = print_lambda(1000)

______
1000

>>> one_thousand # What did the call to print_lambda return?

______
# print_lambda returned None, so nothing gets displayed

编程练习

问题 4：复合恒等函数

请编写一个函数，接收两个单参数函数 f 和 g，并返回另一个 函数 ；返回的函数只有一个参数 x。当 True 时，返回的函数应返回 f(g(x)) 是否等于 g(f(x)) 和 False ，否则返回另一结果。可以假设 g(x) 的输出一定可以作为 f 的有效输入，反之亦然。

def composite_identity(f, g):
    """
    Return a function with one parameter x that returns True if f(g(x)) is
    equal to g(f(x)). You can assume the result of g(x) is a valid input for f
    and vice versa.

    >>> add_one = lambda x: x + 1        # adds one to x
    >>> square = lambda x: x**2          # squares x [returns x^2]
    >>> b1 = composite_identity(square, add_one)
    >>> b1(0)                            # (0 + 1) ** 2 == 0 ** 2 + 1
    True
    >>> b1(4)                            # (4 + 1) ** 2 != 4 ** 2 + 1
    False
    """
    "*** YOUR CODE HERE ***"

使用 Ok 测试你的代码：

python3 ok -q composite_identity

问题 5：条件计数

观察下面对 count_fives 和 count_primes 的实现，它们使用了下方实现的 sum_digits 和 is_prime 函数：

def count_fives(n):
    """Return the number of values i from 1 to n (including n)
    where sum_digits(n * i) is 5.

    >>> count_fives(10)  # Among 10, 20, 30, ..., 100, only 50 (10 * 5) has digit sum 5
    1
    >>> count_fives(50)  # 50 (50 * 1), 500 (50 * 10), 1400 (50 * 28), 2300 (50 * 46)
    4
    """
    i = 1
    count = 0
    while i <= n:
        if sum_digits(n * i) == 5:
            count += 1
        i += 1
    return count

def count_primes(n):
    """Return the number of prime numbers up to and including n.

    >>> count_primes(6)   # 2, 3, 5
    3
    >>> count_primes(13)  # 2, 3, 5, 7, 11, 13
    6
    """
    i = 1
    count = 0
    while i <= n:
        if is_prime(i):
            count += 1
        i += 1
    return count

这些实现非常相似！请编写函数 count_cond来概括其中的逻辑。它接收一个双参数谓词函数 condition(n, i). count_cond ，并返回一个接收参数 n的单参数函数；该函数统计从 1 到 n 中满足 condition 调用条件的数字数量。

注意： 这里说 condition 是谓词函数，是指该函数会返回布尔值 True 或 False.

def sum_digits(y):
    """Return the sum of the digits of non-negative integer y."""
    total = 0
    while y > 0:
        total, y = total + y % 10, y // 10
    return total

def is_prime(n):
    """Return whether positive integer n is prime."""
    if n == 1:
        return False
    k = 2
    while k < n:
        if n % k == 0:
            return False
        k += 1
    return True

def count_cond(condition):
    """Returns a function with one parameter N that counts all the numbers from
    1 to n that satisfy the two-argument predicate function Condition, where
    the first argument for condition is n and the second argument is the
    number from 1 to n.

    >>> count_fives = count_cond(lambda n, i: sum_digits(n * i) == 5)
    >>> count_fives(10)   # 50 (10 * 5)
    1
    >>> count_fives(50)   # 50 (50 * 1), 500 (50 * 10), 1400 (50 * 28), 2300 (50 * 46)
    4

    >>> is_i_prime = lambda n, i: is_prime(i) # need to pass 2-argument function into count_cond
    >>> count_primes = count_cond(is_i_prime)
    >>> count_primes(2)    # 2
    1
    >>> count_primes(3)    # 2, 3
    2
    >>> count_primes(4)    # 2, 3
    2
    >>> count_primes(5)    # 2, 3, 5
    3
    >>> count_primes(20)   # 2, 3, 5, 7, 11, 13, 17, 19
    8
    """
    "*** YOUR CODE HERE ***"

使用 Ok 测试你的代码：

python3 ok -q count_cond

问题 6：字符串变换器

请使用一个 lambda 表达式补全下面的函数。函数体应只包含一条 return 语句。

from operator import add, sub

def caesar_generator(num, op):
    """Returns a one-argument Caesar cipher function. The function should "rotate" a
    letter by an integer amount 'num' using an operation 'op' (either add or
    sub).

    You may use the provided `letter_to_num` and `num_to_letter` functions,
    which will map all lowercase letters a-z to 0-25 and all uppercase letters
    A-Z to 26-51.

    >>> letter_to_num('a')
    0
    >>> letter_to_num('c')
    2
    >>> num_to_letter(3)
    'd'

    >>> caesar2 = caesar_generator(2, add)
    >>> caesar2('a')
    'c'
    >>> brutus3 = caesar_generator(3, sub)
    >>> brutus3('d')
    'a'
    """
    "*** YOUR CODE HERE ***"
    return ______

使用 Ok 测试你的代码：

python3 ok -q caesar_generator

在本地检查得分

你可以运行以下命令，在本地检查本次作业每道题的得分：

python3 ok --score

这不会提交作业！ 确认得分符合预期后，请将作业提交到 Gradescope，以获得作业学分。

提交作业

请上传所有你修改过的文件，将本次作业提交到 对应的 Gradescope 作业入口。 Lab 00 中提供了详细说明。

正确完成所有题目可得 1 分。 Please ensure your TA has taken your attendance before leaving.

可选题

以下题目为选做题。即使不完成，你仍能获得本次作业的学分；不过它们很适合用来练习，建议还是做一做！

问题 7：回文数

如果一个数从前向后读和从后向前读完全相同，就称为回文数。请填补空白“_”，使函数能够判断一个数是否为回文数。按照考试题的要求，请不要修改函数中除空白之外的任何部分。

def is_palindrome(n):
    """
    Fill in the blanks '_____' to check if a number
    is a palindrome.

    >>> is_palindrome(12321)
    True
    >>> is_palindrome(42)
    False
    >>> is_palindrome(2015)
    False
    >>> is_palindrome(55)
    True
    """
    x, y = n, 0
    f = lambda: _____
    while x > 0:
        x, y = _____, f()
    return y == n

使用 Ok 测试你的代码：

python3 ok -q is_palindrome