Due by 11:59pm on Tuesday, September 8.

查看英文原文

初始文件

下载 lab02.zip。 在压缩包中，你会找到本实验问题的初始文件， 以及一份 Ok 自动评分器。

主要内容

如果你需要复习本实验的材料，请参考本节。你可以直接跳到问题部分，遇到困难再回到这里。

lambda <parameters>: <return expression>

# 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)

必答题

Python会输出什么？

Q1: WWPD: Lambda the Free

使用 Ok 的 "Python会输出什么？" 的题目来测试你的学习成果：

python3 ok -q lambda -u --local

对于所有 WWPD 问题，如果你认为答案是 <function...>，请输入 Function；如果出现错误，请输入 Error；如果不会显示任何内容，请输入 Nothing。提醒一下，以下两行代码在 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 exp.
______
3
>>> b = lambda x: lambda: x  # Lambdas can return other lambdas!
>>> c = b(88)
>>> c
______
<function <lambda> at ...
>>> c()
______
88
>>> d = lambda f: f(4)  # They can have functions as arguments as well.
>>> def square(x):
...     return x * x
>>> d(square)
______
16

>>> x = None # remember to review the rules of WWPD given above!
>>> x
>>> lambda x: x
______
Function

>>> z = 3
>>> e = lambda x: lambda y: lambda: x + y + z
>>> e(0)(1)()
______
4
>>> f = lambda z: x + z
>>> f(3)
______
NameError: name 'x' is not defined

>>> 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
______
# print_lambda returned None, so nothing gets displayed

Q2: WWPD: 高阶函数

使用 Ok 的 "Python会输出什么？" 的题目来测试你的学习成果：

python3 ok -q hof-wwpd -u --local

对于所有 WWPD 问题，如果你认为答案是 <function...>，请输入 Function；如果出现错误，请输入 Error；如果不会显示任何内容，请输入 Nothing。

>>> def even(f):
...     def odd(x):
...         if x < 0:
...             return f(-x)
...         return f(x)
...     return odd
>>> steven = lambda x: x
>>> stewart = even(steven)
>>> stewart
______
<function ...>
>>> stewart(61)
______
61
>>> stewart(-4)
______
4

>>> 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)()
______
30
>>> cake = 'cake'
>>> snake(10, 20)
______
30

编程练习

Q3: Lambda 和柯里化

我们可以利用 lambda 表达式将多参数函数转换为一系列单参数的高阶函数。例如，我们可以将函数 f(x, y) 写成另一个函数 g(x)(y)。这被称为柯里化。在处理只接受单参数函数的函数时，这非常有用。稍后我们将看到一些例子。

编写一个函数 lambda_curry2，它将使用 lambda 对任何两个参数的函数进行柯里化。有关柯里化的更多详细信息，请参阅课本。

你的解答应只在 return 语句那一行上。你可以先在没有这个限制的情况下编写它，之后再将其修改为一行。

def lambda_curry2(func):
    """
    Returns a Curried version of a two-argument function FUNC.
    >>> from operator import add, mul, mod
    >>> curried_add = lambda_curry2(add)
    >>> add_three = curried_add(3)
    >>> add_three(5)
    8
    >>> curried_mul = lambda_curry2(mul)
    >>> mul_5 = curried_mul(5)
    >>> mul_5(42)
    210
    >>> lambda_curry2(mod)(123)(10)
    3
    """
    "*** YOUR CODE HERE ***"
    return ______

使用 Ok 来测试你的代码：

python3 ok -q lambda_curry2 --local

Q4: 数数伯爵 (Count van Count)

考虑以下 count_factors 和 count_primes 函数的实现：

def count_factors(n):
    """Return the number of positive factors that n has.
    >>> count_factors(6)
    4   # 1, 2, 3, 6
    >>> count_factors(4)
    3   # 1, 2, 4
    """
    i, count = 1, 0
    while i <= n:
        if n % i == 0:
            count += 1
        i += 1
    return count

def count_primes(n):
    """Return the number of prime numbers up to and including n.
    >>> count_primes(6)
    3   # 2, 3, 5
    >>> count_primes(13)
    6   # 2, 3, 5, 7, 11, 13
    """
    i, count = 1, 0
    while i <= n:
        if is_prime(i):
            count += 1
        i += 1
    return count

def is_prime(n):
    return count_factors(n) == 2 # only factors are 1 and n

这两个函数的实现看起来非常相似！请你编写一个函数 count_cond 来泛化这个逻辑，该函数接受一个带有两个参数的条件判断函数 condition(n, i)。count_cond 返回一个单参数函数，该函数接受 n，并计算从 1 到 n 的所有满足 condition 的数字。

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_factors = count_cond(lambda n, i: n % i == 0)
    >>> count_factors(2)   # 1, 2
    2
    >>> count_factors(4)   # 1, 2, 4
    3
    >>> count_factors(12)  # 1, 2, 3, 4, 6, 12
    6

    >>> is_prime = lambda n, i: count_factors(i) == 2
    >>> count_primes = count_cond(is_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 --local

环境图练习题

这一部分不需要提交。然而，我们仍然鼓励你在纸上完成这些问题，以熟悉环境图，它们可能会以另一种形式出现在考试中。

Q5: Make Adder

为以下代码绘制环境图：

n = 9
def make_adder(n):
    return lambda k: k + n
add_ten = make_adder(n+1)
result = add_ten(n)

一共有 3 个框架(Frame)（包括全局框架(Global Frame)）。此外，请思考以下问题：

1. 在全局框架中，名称 add_ten 指向一个函数对象。该函数对象的内在名称是什么，它的父框架是什么？
2. 框架 f2 标记的名称是什么（add_ten 或 λ）？f2 的父框架是什么？
3. 在全局框架中，变量 result 绑定的值是什么？

Q6: Lambda 环境图解析

尝试为以下代码绘制环境图，并预测 Python 将输出什么。

你不需要通过 Ok 提交或解锁这个问题。 不过，你可以使用 Online Python Tutor 检查你的工作，但请先自己尝试绘制！

>>> a = lambda x: x * 2 + 1
>>> def b(b, x):
...     return b(x + a(x))
>>> x = 3
>>> b(a, x)
______
21 # Interactive solution: https://goo.gl/Lu99QR

Submit

Make sure to submit this assignment by running:

python3 ok --submit

选做题

Q7: 复合恒等函数

编写一个函数，该函数接收两个单参数函数 f 和 g，并返回另一个函数，该函数接受一个参数 x。 如果 f(g(x)) 等于 g(f(x))，则返回函数应返回 True。 可以假设 g(x) 的输出是 f 的有效输入，反之亦然。 请尝试使用下面定义的 compose1 函数来练习更多高阶函数。

def compose1(f, g):
    """Return the composition function which given x, computes f(g(x)).

    >>> add_one = lambda x: x + 1        # adds one to x
    >>> square = lambda x: x**2
    >>> a1 = compose1(square, add_one)   # (x + 1)^2
    >>> a1(4)
    25
    >>> mul_three = lambda x: x * 3      # multiplies 3 to x
    >>> a2 = compose1(mul_three, a1)    # ((x + 1)^2) * 3
    >>> a2(4)
    75
    >>> a2(5)
    108
    """
    return lambda x: f(g(x))

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
    >>> 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 --local

Q8: 我听说你喜欢函数……

定义一个函数 cycle，该函数接收三个函数 f1、f2 和 f3 作为参数。 cycle 将返回另一个函数，该函数接受一个整数参数 n，并返回最终的函数。 这个最终函数接受一个参数 x，并根据 n 的值循环对 x 应用 f1、f2 和 f3。 以下是不同 n 值时，最终函数对 x 的操作方式：

• n = 0，返回 x
• n = 1，对 x 应用 f1，即返回 f1(x)
• n = 2，先对 x 应用 f1，再对结果应用 f2，即返回 f2(f1(x))
• n = 3，依次对 x 应用 f1、f2 和 f3，即返回 f3(f2(f1(x)))
• n = 4，重新开始循环，依次应用 f1、f2、f3，然后再次应用 f1，即返回 f1(f3(f2(f1(x))))
• 以此类推。

提示: 主要的逻辑应放在最内层的函数中。

def cycle(f1, f2, f3):
    """Returns a function that is itself a higher-order function.

    >>> def add1(x):
    ...     return x + 1
    >>> def times2(x):
    ...     return x * 2
    >>> def add3(x):
    ...     return x + 3
    >>> my_cycle = cycle(add1, times2, add3)
    >>> identity = my_cycle(0)
    >>> identity(5)
    5
    >>> add_one_then_double = my_cycle(2)
    >>> add_one_then_double(1)
    4
    >>> do_all_functions = my_cycle(3)
    >>> do_all_functions(2)
    9
    >>> do_more_than_a_cycle = my_cycle(4)
    >>> do_more_than_a_cycle(2)
    10
    >>> do_two_cycles = my_cycle(6)
    >>> do_two_cycles(1)
    19
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python3 ok -q cycle --local