作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，日拱一卒，我是梁唐。
函数式编程是Python这门语言当中的一个很大的特性，也是让Python的使用变得非常好用和灵活的原因之一。但很多Python的使用者对于函数式编程的理解和掌握并不到位，所以在实现Python代码的时候还是秉持着C系的风格，错过了很多简洁代码提升效率的机会。
因此想要学好Python，深入这门语言，函数式编程是必须攻克的堡垒之一。要做到这点呢，光靠看一些教程或者是博客收效甚微，还是需要亲身实践，进行一定量的练习。
这一次伯克利的实验课就是一个很好的练习的机会，虽然我们上不了这样全球顶级的名校，但这并不妨碍我们学习它们公开的知识。
本系列会持续更新，想要一起学习的同学不妨在评论区打个卡。
课程链接：https://www.bilibili.com/video/BV16W411W76H
实验原始文档：https://inst.eecs.berkeley.edu//~cs61a/sp18/lab/lab02/#what-would-python-display
好了，废话不多说，让我们一起开始本次的实验吧。
和之前一样，我们需要先打开原始文档，找到对应的压缩包进行下载，或者也可以通过我的GitHub获取。压缩包解压之后，会有这么几个文件：
这中间我们要改动的只有lab02.py和lab02_extra.py，其他文件不需要动，都是测试相关的文件。
一切准备就绪，我们可以开始实验了。
必做题
What Would Python Display?
读程序给结果
Q1: WWPD: Lambda the Free
使用ok命令进行答题：python3 ok -q lambda -u
一共有14题，横线即为我们要填的结果。如果结果是一个函数，填写Function，如果运行会报错填写Error，如果输出为空，填写Nothing
这几道题不算难，掌握了labmda的用法，以及函数式编程的思想还是比较好做的。中间有两道题可能会稍微有点绕，如果实在想不明白，把代码复制出来在Python中运行一下就知道了。
代码语言：javascript复制>>> lambda x: x # A lambda expression with one parameter x
______
>>> a = lambda x: x # Assigning the lambda function to the name a
>>> a(5)
______
>>> (lambda: 3)() # Using a lambda expression as an operator in a call exp.
______
>>> b = lambda x: lambda: x # Lambdas can return other lambdas!
>>> c = b(88)
>>> c
______
>>> c()
______
>>> d = lambda f: f(4) # They can have functions as arguments as well.
>>> def square(x):
... return x * x
>>> d(square)
______
>>> z = 3
>>> e = lambda x: lambda y: lambda: x y z
>>> e(0)(1)()
______
>>> f = lambda z: x z
>>> f(3)
______
>>> 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?
______
>>> higher_order_lambda(g)(2)
______
>>> call_thrice = lambda f: lambda x: f(f(f(x)))
>>> call_thrice(lambda y: y 1)(0)
______
>>> print_lambda = lambda z: print(z) # When is the return expression of a lambda expression executed?
>>> print_lambda
______
>>> one_thousand = print_lambda(1000)
______
>>> one_thousand
______
Q2: WWPD: Higher Order Functions
一样是填空题，命令python3 ok -q hof -u
如果结果是一个函数，填写Function，如果运行会报错填写Error，如果输出为空，填写Nothing
一共有11题，里面有两题对新手来说可能有点绕，如果想不明白可以先运行得到答案，再反向思考原因。
代码语言：javascript复制>>> 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
______
>>> stewart(61)
______
>>> stewart(-4)
______
>>> def cake():
... print('beets')
... def pie():
... print('sweets')
... return 'cake'
... return pie
>>> chocolate = cake()
______
>>> chocolate
______
>>> chocolate()
______
>>> more_chocolate, more_cake = chocolate(), cake
______
>>> more_chocolate
______
>>> def snake(x, y):
... if cake == more_cake:
... return lambda y: x y
... else:
... return x y
>>> snake(10, 20)
______
>>> snake(10, 20)(30)
______
>>> cake = 'cake'
>>> snake(10, 20)
______
Coding Practice
Q3: Lambdas and Currying
我们可以把一个多个参数的函数转化成一系列高阶的单个参数的函数，这也是lambda表达式的优势所在。在处理单个参数的函数时，这非常有用，之后我们将会有一些样例来展示这点。
编写函数lambda_curry2，它可以用lambda表达式curry任意两个参数的函数。你可以看一下下面的测试案例，帮助理解：
>>> from operator import add
>>> curried_add = lambda_curry2(add)
>>> add_three = curried_add(3)
>>> add_three(5)
答案
其实没有太多可说的，理解了题目含义和lambda表达式的用法，不难写出来
代码语言：javascript复制def lambda_curry2(func):
"""
Returns a Curried version of a two-argument function FUNC.
"""
"*** YOUR CODE HERE ***"
return lambda x: lambda y: func(x, y)
Optional Questions
Environment Diagram Practice
Q4: Lambda the Environment Diagram
尝试画出下列代码运行时python的环境示意图并且预测Python的输出结果，本题不需要测试，你可以通过这个网站检查自己的答案是否正确：https://pythontutor.com/composingprograms.html#mode=edit
代码语言：javascript复制>>> a = lambda x: x * 2 1
>>> def b(b, x):
... return b(x a(x))
>>> x = 3
>>> b(a, x)
______
答案
其实所谓的环境示意图，就是函数之间的调用结构图。这个图在老师的上课视频中有展示过很多次，没有看过视频的同学可能不清楚。
其实没必要纠结图怎么画，只要能理清楚代码中的调用关系，知道答案是怎么获得的即可。
给大家看下最后的结果：
Q5: Make Adder
画出下方代码的环境示意图：
代码语言：javascript复制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），并且思考下列问题：
- 在Global frame中，
add_ten指向一个函数对象，这个函数对象的名称是什么？哪一个frame是它的parent？ - 在
framef2中，frame的名称是什么？是add_ten还是 λ？f2的parent frame是哪个？ - global frame下
result变量绑定的值是什么？
答案
想要回答这些问题，我们需要理清楚这些函数和frame之间的关系。
首先第一个问题，add_ten指向的函数对象是make_adder函数的执行结果，这个执行结果我们读代码可以知道，是一个lambda函数。所以add_ten指向的函数名称应该是lambda。其次这个lambda的parent frame是哪个，就要看它是在哪个frame中创建的。
显然是在make_adder中创建的，make_adder又是在global下运行的，所以它的frame是f1。
第二个问题，f2的名称是什么，首先我们要清楚f2是什么时候创建的，答案是add_ten(n)执行的时候。由于我们前面分析了add_ten的名称是lambda，所以这个frame的名称也应该是lambda而不是add_ten。f2的parent frame当然是创建它的f1，即make_adder运行时的frame。
最后一个问题，result的绑定值是什么，即询问最后的返回结果，经过推算可以知道是21。
如果有什么不清楚的，可以参考下图，推理一下应该就都清楚了。
More Coding Practice
注意：接下来的问题回答在lab02.extra.py 中
Q6: Composite Identity Function
编写一个函数接收两个单参数的函数f和g，并且返回另外一个函数，拥有一个参数x。这个返回的函数在f(g(x)) = g(f(x))时返回True。你可以假设g(x)的输出是f的有效输入，反之亦然。你可以使用下面给定的compose1函数
代码框架：
代码语言：javascript复制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 ***"
测试命令：python3 ok -q composite_identity
答案
题意很明确，我们要返回一个只接收一个参数x判断f(g(x)) == g(f(x))的逻辑。f和g都有了，其实实现非常简单，一行代码搞定：
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.
"""
"*** YOUR CODE HERE ***"
return lambda x: f(g(x)) == g(f(x))
如果非要使用上compose1的话，相当于我们不能自己调用f(g(x))和g(f(x))了，而需要使用compose1，也不复杂，稍微改下lambda函数实现即可。
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.
"""
"*** YOUR CODE HERE ***"
return lambda x: compose1(f, g)(x) == compose1(g, f)(x)
Q7: Count van Count
查看下面count_factors和count_primes两个函数代码：
def count_factors(n):
"""Return the number of positive factors that n has."""
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."""
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返回一个单参数函数用来计算1到n中所有满足condition的数量。
代码框架：
代码语言：javascript复制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.
>>> 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 ***"
测试命令：python3 ok -q count_cond
答案
count_cond接收的参数condition是用来判断i, n是否满足条件的。i是从1遍历到n的迭代变量，而n是不知道的，从测试数据中我们可以看出，n应该是从外界传入的，即我们返回的这个函数的参数。
即，我们的代码应该是这样的：
代码语言：javascript复制def count_cond(condition):
def func(n):
pass
return func
这个嵌套的函数func的逻辑只需要follow一下上面例子中的做法即可。
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.
"""
"*** YOUR CODE HERE ***"
def func(n):
i, count = 1, 0
while i <= n:
if condition(n, i):
count = 1
i = 1
return count
return func
Q8: I Heard You Liked Functions...
创建一个函数cycle，它接收三个函数f1, f2, f3。cycle将会返回另外一个函数，它接收一个整数n作为入参，并且再返回一个函数。这个返回的函数将会接收一个参数x，并且根据n的值循环调用f1,f2,f3应用在x上。
这是n在不同取值下，x应该执行的操作：
n=0，返回xn=1，返回f1(x)n=2，返回f2(f1(x))n=3，返回f3(f2(f1(x)))n=4，返回f1(f3(f2(f1(x))))- 以此类推
代码框架：
代码语言：javascript复制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 ***"
测试命令：python3 ok -q cycle
答案
这题有一些难度，都这么多题做下来了，很快就能写出代码框架：
代码语言：javascript复制def cycle(f1, f2, f3):
def inner1(n):
def inner2(x):
pass
return inner2
return inner1
但问题是动态套用函数循环的这个效果如何实现，这是比较麻烦的。通过观察，我们假设cycle函数返回的这个函数叫做g，根据n=0时，返回x，可以得知：g(0)(x) = x。依次，我们可以写出g(1)(x), g(2)(x)等等。
但怎么体现循环应用呢？我们观察一下可以发现，g函数之间其实存在递归关系。比如g(1)(x) = f1(g(0)(x)，g(2)(x) = f2(g(1)(x))……
所以我们要做的就是使用递归来表达这个逻辑，由于根据n的不同，选择函数也不同。为了解决这个问题，我们可以把函数f1, f2, f3放入数组当中，根据n对3的余数进行选择。
大家可以结合代码细节理解一下其中的逻辑。
代码语言：javascript复制def cycle(f1, f2, f3):
"""Returns a function that is itself a higher-order function.
"""
"*** YOUR CODE HERE ***"
funcs = [f1, f2 ,f3]
def inner1(n):
def inner2(x):
if n == 0:
return x
else:
# funcs[(n-1) % 3] 是一个f1,f2,f3中的一个函数
return funcs[(n-1) % 3](inner1(n-1)(x))
return inner2
return inner1
到这里，这个lab就算是做完了。
里面的题目看起来多，其实做起来还好，顺利的话一个小时左右就可以做完。题目的质量很高，尤其是对于初学者来说，可以说是干货满满，相信只要认真去做，一定可以学到很多。
最后，感谢大家的阅读，祝大家日拱一卒，每天都有进步。
喜欢本文的话不要忘记三连~
