likes
comments
collection
share

日拱一卒，伯克利带你Python进阶，函数式编程与lambda表达式

作者站长头像
站长
· 阅读数 7

大家好，日拱一卒，我是梁唐。

lambda表达式和高阶函数是Python语法当中最重要的部分几乎没有之一，大部分Python的高阶用法都是围绕这两者展开的。因此想要学好Python这门语言，这两个知识点肯定是绕不过去的。

以后我们在学习这些知识的时候，往往都是基于博客或者是书籍。经典书籍中的内容当然没的说，但仅仅学习理论是不够的，学习技术相关的内容，无论如何不上手亲自练习一下肯定是不行的。我之前自学的时候就经常苦于没有练习的场景，都是自己生拼硬凑出几个例子来实践。

现在有了伯克利的公开课资料之后，我们不仅能够听到伯克利老师的讲课视频，也能亲自做一做它的课后练习和实验，这是一个非常非常好的练习机会。并且最最关键的是，这些都是免费的。

本系列会持续更新，想要一起学习的同学不妨在评论区打个卡。

课程链接

实验原始文档

Github

好了，废话不多说，让我们一起开始本次的实验吧。

和之前一样，我们需要先打开原始文档，找到对应的压缩包进行下载，或者也可以通过我的GitHub获取。压缩包解压之后，会有这么几个文件：

日拱一卒，伯克利带你Python进阶，函数式编程与lambda表达式

这中间我们要改动的只有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，返回x
  • n=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…

日拱一卒，伯克利带你Python进阶，函数式编程与lambda表达式

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)

我是先做完了作业再来做的实验，明显感觉到虽然实验中的题目难度不低，但做起来顺手了很多。说明了作业当中的练习对提升理解和熟练度还是很有好处的，希望大家也能亲自尝试一下，体会一下其中的乐趣。