日拱一卒，伯克利带你Python进阶，函数式编程与lambda表达式
大家好，日拱一卒，我是梁唐。
lambda表达式和高阶函数是Python语法当中最重要的部分几乎没有之一，大部分Python的高阶用法都是围绕这两者展开的。因此想要学好Python这门语言，这两个知识点肯定是绕不过去的。
以后我们在学习这些知识的时候，往往都是基于博客或者是书籍。经典书籍中的内容当然没的说，但仅仅学习理论是不够的，学习技术相关的内容，无论如何不上手亲自练习一下肯定是不行的。我之前自学的时候就经常苦于没有练习的场景，都是自己生拼硬凑出几个例子来实践。
现在有了伯克利的公开课资料之后，我们不仅能够听到伯克利老师的讲课视频，也能亲自做一做它的课后练习和实验，这是一个非常非常好的练习机会。并且最最关键的是，这些都是免费的。
本系列会持续更新，想要一起学习的同学不妨在评论区打个卡。
好了，废话不多说，让我们一起开始本次的实验吧。
和之前一样，我们需要先打开原始文档，找到对应的压缩包进行下载，或者也可以通过我的GitHub获取。压缩包解压之后，会有这么几个文件：
这中间我们要改动的只有lab03.py和lab03_extra.py，其他文件不需要动，都是测试相关的文件。
一切准备就绪，我们可以开始实验了。
Required Questions
必做题
Q1: GCD
古希腊数学家欧几里得在公元前300年就想出了计算a和b的最大公约数的方法，a和b两数的最大公约数为：
- 如果
a和b当中较小的数能整除较大的数，则为较小的数，或者 - 较小数和较大数关于较小数余数的最大公约数
这段话看起来有些拗口，转换以下，也就是说，当a大于b时，如果a不能被b整除，那么结果就是：
gcd(a, b) = gcd(b, a % b)
用递归的方式实现欧几里得算法（辗转相除法）
代码框架如下：
def gcd(a, b):
"""Returns the greatest common divisor of a and b.
Should be implemented using recursion.
>>> gcd(34, 19)
1
>>> gcd(39, 91)
13
>>> gcd(20, 30)
10
>>> gcd(40, 40)
40
"""
"*** YOUR CODE HERE ***"
使用Ok测试程序，命令为：python3 ok -q gcd
答案
辗转相除法的原理题目说明里已经讲得很清楚了，甚至还给出了关键步骤的伪代码，我们只需要将它装进递归里即可。
递归终止的条件是什么？是a % b = 0，此时的最大公约数就是b，否则，继续进行辗转相除法。
def gcd(a, b):
"""Returns the greatest common divisor of a and b.
Should be implemented using recursion.
"""
"*** YOUR CODE HERE ***"
if a % b == 0:
return b
return gcd(b, a % b)
Q2: Hailstone
在作业1当中我们做过一题叫做hailstone，开始的时候你会选择一个正整数n。如果n是偶数，将它除以2，如果它是奇数，则将它乘3再加1。重复以上步骤，直到n等于1。
使用递归的方式实现hailstone，并且打印出中间步骤，返回最终的操作次数。
代码框架为：
def hailstone(n):
"""Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.
>>> a = hailstone(10)
10
5
16
8
4
2
1
>>> a
7
"""
"*** YOUR CODE HERE ***"
完成之后，使用Ok进行测试：python3 ok -q hailstone
答案
这题稍微麻烦一点点，我们直接递归有点小问题，就是没办法保存执行的次数，因此需要我们重新改写一下函数签名。
然而我们不能直接改写hailstone的签名，这会影响外部的调用。所以我们只能在hailstone内部再创建一个新的函数，这也是高阶函数的常规操作。在这个内部的函数当中，它接收两个参数，一个是当前的整数n，还有一个是执行的次数，也是我们hailstone函数需要返回的结果。
打印中间步骤以及递归的过程就交给这个函数执行，hailstone只需要调用即可。
def hailstone(n):
"""Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.
"""
"*** YOUR CODE HERE ***"
def func(n, ans):
print(n)
if n == 1:
return ans
if n % 2 == 0:
n //= 2
else:
n = n * 3 + 1
return func(n, ans+1)
return func(n, 1)
函数
Q3: WWPD: Call Expressions
填空题，读代码给出代码运行或返回的结果。
答题命令：python3 ok -q call_expressions -u，如果代码返回结果为一个函数，输入Function，如果代码运行报错，输入Error，如果什么也不会展示，输入Nothing。
一共有六道题，总的来说不算太难，如果做不出来，可以复制一下代码到Python解释器中实际运行一下。
>>> from operator import add
>>> def double(x):
... return x + x
...
>>> def square(y):
... return y * y
...
>>> def f(z):
... add(square(double(z)), 1)
...
>>> f(4)
______
>>> def foo(x, y):
... print("x or y")
... return x or y
...
>>> a = foo
______
>>> b = foo()
______
>>> c = a(print("x"), print("y"))
______
>>> print(c)
______
>>> def welcome():
... print('welcome to')
... return 'hello'
...
>>> def cs61a():
... print('cs61a')
... return 'world'
...
>>> print(welcome(), cs61a())
______
高阶函数
Q4: 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))))- 以此类推
代码框架：
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
答案
这题上篇文章当中做过了，直接贴答案
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
Lambda 表达式
Q5: Palindrome
如果一个数从前往后和从后往前读起来一样，那么它就被称为回文数。填写下面代码当中的空缺，使得它可以判断一个数是否是回文数。请不要修改其他部分。
代码框架：
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
答案
函数最后返回的结果是y == n，也就是说通过y和n是否相等来判断回文的。那么基于回文数的基本定义，y显然应该是n从右到左看的结果。所以我们需要从x的末尾获取数字，并放到y的头部。
在算法题当中这也是常规操作，不明白的小伙伴可以参考一下以下代码结合起来一起理解。
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: y * 10 + x % 10
while x > 0:
x, y = x // 10, f()
return y == n
Environment diagrams
Q6: Doge
画出下面程序执行之后的函数调用图。
wow = 6
def much(wow):
if much == wow:
such = lambda wow: 5
def wow():
return such
return wow
such = lambda wow: 4
return wow()
wow = much(much(much))(wow)
答案
老师故意把函数的调用返回过程搞得很乱，理解困难的话，老师提供了专门的网站可以一步一步展示绘制的过程：pythontutor.com/composingpr…
More Recursion Practice
Q7: Find the Bug
找到下列递归函数的bug
def skip_mul(n):
"""Return the product of n * (n - 2) * (n - 4) * ...
>>> skip_mul(5) # 5 * 3 * 1
15
>>> skip_mul(8) # 8 * 6 * 4 * 2
384
"""
if n == 2:
return 2
else:
return n * skip_mul(n - 2)
当你找到了，运行以下命令来检查你的答案：python3 ok -q skip_mul_ok -u
当你改好之后，运行一下命令来测试代码：python3 ok -q skip_mul
答案
从注释里可以看出来，这题原本是要实现一个间隔为2的阶乘。
但问题在于，它的递归终结的表达式有点问题，只判断了n == 2的情况。当n == 1时，则没有囊括在内。所以当传入的n是奇数时会无线递归死循环。
所以要修改也很简单，将n == 2改成 n <= 2，返回的结果从固定的2改成n即可。
def skip_mul(n):
"""Return the product of n * (n - 2) * (n - 4) * ...
>>> skip_mul(5) # 5 * 3 * 1
15
>>> skip_mul(8) # 8 * 6 * 4 * 2
384
"""
if n <= 2:
return n
else:
return n * skip_mul(n - 2)
Q8: Is Prime
实现一个函数is_prime它接收一个参数n，如果n是质数返回True否则返回False。
假设n > 1，我们在之前实现过一个迭代的版本，请将它改成递归实现。
提示：你需要一个helper函数，尤其是当你递归时需要的参数比外界传入的更多时，这样你就可以避免修改外界入参了
开发完成之后，使用ok测试代码：python3 ok -q is_prime
答案
我们直接根据质数的定义实现，如果从2到n-1的数都不能整除n，那么n就是质数。我们在递归当中多传入一个参数k用来枚举2到n-1中可能整除n的数，当n = k或者是n能整除k时为递归终止条件。
def is_prime(n):
"""Returns True if n is a prime number and False otherwise.
>>> is_prime(2)
True
>>> is_prime(16)
False
>>> is_prime(521)
True
"""
"*** YOUR CODE HERE ***"
def is_prime_helper(n, k):
if n == k:
return True
if n % k == 0:
return False
return is_prime_helper(n, k+1)
return is_prime_helper(n, 2)
Q9: Interleaved Sum
复习一下summation函数，实现了从1到n，对term(i)进行求和。
def summation(n, term):
"""Return the sum of the first n terms of a sequence.
>>> summation(5, lambda x: pow(x, 3))
225
"""
total, k = 0, 1
while k <= n:
total, k = total + term(k), k + 1
return total
实现一个函数interleaved_sum函数，它功能很相似，也是计算1到n的term和。但对于奇数和偶数采用不同的term函数。你不能使用循环或者任何方式判断一个数是奇数还是偶数，你可以判断数是否等于0，1，或者n。
代码框架：
def interleaved_sum(n, odd_term, even_term):
"""Compute the sum odd_term(1) + even_term(2) + odd_term(3) + ..., up
to n.
>>> # 1 + 2^2 + 3 + 4^2 + 5
... interleaved_sum(5, lambda x: x, lambda x: x*x)
29
"""
"*** YOUR CODE HERE ***"
提示：使用递归和helper函数
完成之后，使用ok进行测试：python3 ok -q interleaved_sum
答案
如果我们可以判断当前的n的奇偶性，其实这题并不难。
但题目中明确说了，我们不能这样干。我们当然可以再写一个递归函数来获取当前的n对应的函数是什么，但其实有一点没必要。因为我们可以把这个逻辑也合并到递归的主体里。因为Python可以返回多个结果，也可以返回函数，那么我们大可以递归的时候返回一下下一次需要调用的函数。
代码如下：
def interleaved_sum(n, odd_term, even_term):
"""Compute the sum odd_term(1) + even_term(2) + odd_term(3) + ..., up
to n.
>>> # 1 + 2^2 + 3 + 4^2 + 5
... interleaved_sum(5, lambda x: x, lambda x: x*x)
29
"""
"*** YOUR CODE HERE ***"
def helper(n, odd_term, even_term):
if n == 0:
return odd_term, even_term(0)
f, tot = helper(n-1, odd_term, even_term)
next_f = odd_term if f == even_term else even_term
return next_f, tot + f(n)
_, ret = helper(n, odd_term, even_term)
return ret
Q10: Ten-pairs
实现一个函数，它接收一个整数n，返回它拥有的ten-pairs的数量。ten-pair是指n中一对加起来等于10的数字。不要使用赋值语句。
比如数字7823952拥有3个ten-pair，分别是7+3=10, 8+2=10, 8+2=10。
提示：使用helper函数来计算n中每一个数字出现的次数
完成之后，使用ok进行测试：python3 ok -q ten_pairs
答案
由于题目限制了不能使用赋值语句，所以难度增加了不小，所以我们只能使用递归去获取我们想要的结果。
我们先不考虑helper怎么设计，先来思考一下主体的递归程序的结构。如果n小于10，显然不可能存在ten-pair，那么直接return 0。
如果n大于10，它的ten-pair可以拆分成两个部分，一个部分是包含当前个位数的ten-pair，我们假设当前个位数是k，另一个部分是不包含k的ten-pair。显然，对于不包含k的ten-pair我们可以直接递归来求。而包含k的怎么求呢？
其实很简单，就是需要统计一下k之前有多少个10-k的值。那么我们实现一个递归函数来完成10-k的次数统计即可。
def ten_pairs(n):
"""Return the number of ten-pairs within positive integer n.
>>> ten_pairs(7823952)
3
>>> ten_pairs(55055)
6
>>> ten_pairs(9641469)
6
"""
"*** YOUR CODE HERE ***"
def helper(n, k):
if n < 10:
return n == k
return helper(n // 10, k) + (n % 10 == k)
if n < 10:
return 0
return ten_pairs(n // 10) + helper(n // 10, 10 - n % 10)
我是先做完了作业再来做的实验，明显感觉到虽然实验中的题目难度不低，但做起来顺手了很多。说明了作业当中的练习对提升理解和熟练度还是很有好处的，希望大家也能亲自尝试一下，体会一下其中的乐趣。
转载自:https://juejin.cn/post/7099471610905640967