日拱一卒，不愧是伯克利，做完这几道题我感觉我升华了……

TechFlow-承志

发布于 2022-08-26 14:34:20

5340

发布于 2022-08-26 14:34:20

文章被收录于专栏：TechFlow

作者 | 梁唐

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

今天我们继续来聊聊伯克利的CS61A课程，这次咱们看的是作业3。

这一次的作业除了关注函数式编程之外，也增加了递归的考察。我个人觉得也是学习和理解递归的一个非常不错的案例。

和之前的作业相比，这一次的作业难度提升了很多，尤其是附加题，真的是非常非常的难。难到让我不停地感慨，不愧是伯克利的作业……

它的难并不在于用到了新知识，实际上用到的都是基本的Python函数式编程和递归的思想。难就难在它对于思维的考察非常非常深入……我非常推荐大家都仔细看一看，一定一定可以刷新认知。

完整的代码我上传到了GitHub，点击【阅读原文】即可跳转

好了，废话不多说了，我们一起来看题吧。

Q1: Has Seven

通过递归的方式实现一个函数，判断给定的数字当中是否包含7。

这题很简单，递归的常规用法，每次通过对10取模拿到最后一个数，判断它是否为7，接着递归处理n // 10的结果。

def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.
    """
    "*** YOUR CODE HERE ***"
    if k < 10:
        return k == 7
    else:
        return has_seven(k // 10) or k % 10 == 7

Q2: Summation

实现一个递归函数summation，它有两个参数，一个是整数n，一个是一个函数term。要求返回

\sum_{i=1}^n term(i)

的结果.

def summation(n, term):

    """Return the sum of the first n terms in the sequence defined by term.
    Implement using recursion!

    >>> summation(5, lambda x: x * x * x) # 1^3 + 2^3 + 3^3 + 4^3 + 5^3
    225
    >>> summation(9, lambda x: x + 1) # 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
    54
    >>> summation(5, lambda x: 2**x) # 2^1 + 2^2 + 2^3 + 2^4 + 2^5
    62
    >>> # Do not use while/for loops!
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'summation',
    ...       ['While', 'For'])
    True
    """
    assert n >= 1
    "*** YOUR CODE HERE ***"

这也是递归的常规用法，当n=1时，返回term(1)，否则返回term(n) + summation(n-1, term)。

def summation(n, term):

    """Return the sum of the first n terms in the sequence defined by term.
    Implement using recursion!
    """
    assert n >= 1
    "*** YOUR CODE HERE ***"
    if n == 1:
        return term(n)
    return summation(n-1, term) + term(n)

Q3: Accumulate

def accumulate(combiner, base, n, term):
    """Return the result of combining the first n terms in a sequence and base.
    The terms to be combined are term(1), term(2), ..., term(n).  combiner is a
    two-argument commutative function.

    >>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
    15
    >>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
    26
    >>> accumulate(add, 11, 0, identity) # 11
    11
    >>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
    25
    >>> accumulate(mul, 2, 3, square)   # 2 * 1^2 * 2^2 * 3^2
    72
    """
    "*** YOUR CODE HERE ***"

实现summation函数的一个通用版本accumulate，它接受4个参数：combiner,base,n,term。用来实现：[base, term(1), term(2)...term(n)]这些结果通过combiner函数聚合起来的结果。

combiner函数接收两个整数，返回两个整数结合的结果。比如常规的加法、乘法都是combiner。

有几个样例供我们参考：

>>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
15
>>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
26
>>> accumulate(add, 11, 0, identity) # 11
11
>>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
25
>>> accumulate(mul, 2, 3, square)   # 2 * 1^2 * 2^2 * 3^2
72

可以把base理解成n=0时的结果。

这题的难度相比刚才提升了一些，需要我们充分理解combiner,accumulate函数的用法，以及充分理解递归思想。在刚才的summation函数当中，我们默认用的是加法连接结果，这里换成了combiner。

由于combiner只能接收两个结果，结合递归，可以将这两个结果设置成accmulate(combiner, base, n-1, term)和term(n)，其实就是把递归的结果和当前的结果通过combiner结合起来。

代码如下：

def accumulate(combiner, base, n, term):
    """Return the result of combining the first n terms in a sequence and base.
    The terms to be combined are term(1), term(2), ..., term(n).  combiner is a
    two-argument commutative function.
    """
    "*** YOUR CODE HERE ***"
    if n < 1:
        return base
    return combiner(accumulate(combiner, base, n-1, term), term(n))

通过accmulate函数实现累加(summation)和累乘(product)。套用我们刚才实现的accmulate函数即可。

def summation_using_accumulate(n, term):
    """Returns the sum of term(1) + ... + term(n). The implementation
    uses accumulate.
    """
    "*** YOUR CODE HERE ***"
    return accumulate(add, 0, n, term)

def product_using_accumulate(n, term):
    """An implementation of product using accumulate.
    """
    "*** YOUR CODE HERE ***"
    return accumulate(mul, 1, n, term)

Q4: Filtered Accumulate

def filtered_accumulate(combiner, base, pred, n, term):
    """Return the result of combining the terms in a sequence of N terms
    that satisfy the predicate pred. combiner is a two-argument function.
    If v1, v2, ..., vk are the values in term(1), term(2), ..., term(N)
    that satisfy pred, then the result is
         base combiner v1 combiner v2 ... combiner vk
    (treating combiner as if it were a binary operator, like +). The
    implementation uses accumulate.

    >>> filtered_accumulate(add, 0, lambda x: True, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
    15
    >>> filtered_accumulate(add, 11, lambda x: False, 5, identity) # 11
    11
    >>> filtered_accumulate(add, 0, odd, 5, identity)   # 0 + 1 + 3 + 5
    9
    >>> filtered_accumulate(mul, 1, greater_than_5, 5, square)  # 1 * 9 * 16 * 25
    3600
    >>> # Do not use while/for loops or recursion
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'filtered_accumulate',
    ...       ['While', 'For', 'Recursion'])
    True
    """
    def combine_if(x, y):
        "*** YOUR CODE HERE ***"
    return accumulate(combine_if, base, n, term)

进一步增加难度，需要在accumulate的基础上增加过滤，实现filtered_accumulate函数。filtered_accumulate函数相比accmulate多了一个pred，这是一个函数，用来判断某一个值是否需要过滤。

不能在filtered_accumulate函数中调用自身（递归），也不能通过循环实现。

我们参考一下样例：

def odd(x):
    return x % 2 == 1

def greater_than_5(x):
    return x > 5

>>> filtered_accumulate(add, 0, lambda x: True, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
15 # pred 全部返回True，所以相当于累加
>>> filtered_accumulate(add, 11, lambda x: False, 5, identity) # 11
11 # pred 全部返回False，相当于全部不执行，所以结果就是base
>>> filtered_accumulate(add, 0, odd, 5, identity)   # 0 + 1 + 3 + 5
9
>>> filtered_accumulate(mul, 1, greater_than_5, 5, square)  # 1 * 9 * 16 * 25
3600

显然，源代码中已经给了我们提示，我们要实现combine_if函数，调用accmulate函数完成逻辑。

combine_if函数用来判断combine时的情况。combine_if函数接收两个参数x和y,表示待combine的两个数。如果x和y都能通过pred的检测，那显然返回结果就是combiner(x, y)。

如果y不能通过检测，那么我们就返回x。同样，如果x不能通过，y可以通过，那么返回y。但如果两者都不能通过怎么办？返回0吗？

显然我们不能返回0，因为返回0会导致后面combine的时候出错。这里是一个难点。

冷静分析下来，会发现其实这种情况不可能出现，x一定是合法的。我们回顾一下之前accmulate函数的实现，返回的结果是combiner(accumulate(combiner, base, n-1, term), term(n))。我们combine的两个部分分别是accumulate(xxxx)和term(n)，前者是递归迭代子问题的结果，后者是term(n)。

前者是迭代出的结果，既然是迭代出的结果，那么就一定是合法的。所以我们只需要判断y是否能够通过pred即可。因为即使所有的元素都不合法，也有base作为兜底，所以递归的结果一定不可能为空，都不合法时也能返回base。

这里判断x还是判断y不是绝对的，和我们accmulate函数的实现方式有关。如果我们实现的是combiner(term(n), accumulate(xxx))，那么就是y一定合法，判断x了。

def filtered_accumulate(combiner, base, pred, n, term):
    """Return the result of combining the terms in a sequence of N terms
    """
    def combine_if(x, y):
        "*** YOUR CODE HERE ***"
        if pred(y):
            return combiner(x, y)
        return x
    return accumulate(combine_if, base, n, term)

Q5: Make Repeater

实现make_repearter函数，调用make_repeater(f, n)(x)时返回f(f(...f(x)...))，中间一共嵌套n次。

def make_repeater(f, n):
    """Return the function that computes the nth application of f.

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    8
    >>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
    243
    >>> make_repeater(square, 2)(5) # square(square(5))
    625
    >>> make_repeater(square, 4)(5) # square(square(square(square(5))))
    152587890625
    >>> make_repeater(square, 0)(5)
    5
    """
    "*** YOUR CODE HERE ***"

我们看下注释里的样例：

>>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 4)(5) # square(square(square(square(5))))
152587890625
>>> make_repeater(square, 0)(5)

比如第一个make_repeater(triple, 5)(1)，triple表示将一个数乘3，我们把1乘3五次，得到的就是

3^5=243

。

显然最简单的办法是使用循环：

def make_repeater(f, n):
    """Return the function that computes the nth application of f.
  """
    def process(x):
        for i in range(n):
            x = f(x)
        return x
    return process

如果我们不使用循环，使用递归其实套路和上面的问题一样，我们假设g(1) = f(x), g(2) = f(f(x)), g(n) = f(f(...f(x)...))。那么我们要返回的结果就是f(g(n-1))。

所以代码为：

def make_repeater(f, n):
    """Return the function that computes the nth application of f.
  """
    def process(x):
        if n == 0:
            return x
        else:
            return f(make_repeater(f, n-1)(x))
    return process

简单解释一下，make_repeater(f, n)返回的结果是一个函数，我们假设叫做

g^n

。那么

g^n(x)

就是我们要的答案，make_repeater(f, n-1)返回的就是

g^{n-1}

。

附加

给定一个函数compose1：

def compose1(f, g):
    """Return a function h, such that h(x) = f(g(x))."""
    def h(x):
        return f(g(x))
    return h

要求在make_repeater中调用compose1和accmulate函数，只使用一行代码实现功能。

compose1可以将两个函数嵌套，接着我们可以想到利用accumulate将f函数嵌套n次。那么我们需要先将1-n这n个数都转化成函数f，即实现一个函数，接收一个整数，返回函数f，然后再通过compose1嵌套起来，整理思路后，代码如下：

def make_repeater(f, n):
    """Return the function that computes the nth application of f.
  """
  return accumulate(compose1, identity, n, lambda _: f)

Q6: Quine

本题是附加题，实现一行代码，使得这行代码的运行结果和代码本身一样。这样的代码叫做quine。

提示：

可以使用print函数
可以使用repr函数，它会返回带引号的字符串
可以使用eval函数，它会执行将字符串转化成代码执行

虽然有这些提示，但我还是没有想出来，也确实太难了，大家感兴趣可以自己试一试。下面分享几个从网上的大佬处看到的答案：

print((lambda s:s%s)('print((lambda s:s%%s)(%r))'))
s='s="s="+repr(s)+";"+s;print(s)';s="s="+repr(s)+";"+s;print(s)

Q7: Church numerals

附加题，逻辑学家Alonzo Church发明了一种使用函数来表示非负整数的方法，这样表示出来的整数叫做Church numerals。

本题的目的就是仿照这个思路，实现Church numerals。题目当中提供了zero的定义：

def zero(f):
    return lambda x: x

def successor(n):
    return lambda f: lambda x: f(n(f)(x))
  
def one(f):
    """Church numeral 1: same as successor(zero)"""
    "*** YOUR CODE HERE ***"

def two(f):
    """Church numeral 2: same as successor(successor(zero))"""
    "*** YOUR CODE HERE ***"

首先，我们要做的是根据zero和successor函数实现one和two函数。

其中one拥有和successor(zero)相同的逻辑，而two拥有successor(successor(zero))相同的逻辑。

我看到successor逻辑的时候好悬没崩溃，这实在是太复杂了。两个匿名函数嵌套，返回的结果也很奇怪f(n(f)(x))，根本看不出来是什么东西。

但冷静下来会发现，我们可以代入一下zero函数，因为zero函数的逻辑很简单，不论传入什么参数，返回的都是lambda x: x。所以我们可以把n代入zero，这样n(f)得到的结果就是lambda x: x。(lambda x: x)(x)结果是x，这样表达式就化简成了lambda f: lambda x: f(x)，这就是successor(zero)返回的结果。

我们要让one函数和它逻辑相同，其实很简单，就是把最外面的匿名函数换成实名函数，名称是one。所以one函数的代码为：

def one(f):
    """Church numeral 1: same as successor(zero)"""
    "*** YOUR CODE HERE ***"
    return lambda x: f(x)

看完了one，我们再来看two，这个时候我们要求successor(successor(zero))，本质上就是求successor(one)。我们接着往里面代入即可，把n代入成one，n(f)就是one(f)，返回的结果是什么，是lambda x: f(x)，这是也是一个函数，接收一个参数x，返回f(x)。

巧了one(f)后面跟着的就是传参(x)，所以o(f)(x)代入之后就成了f(x)。整个代码段化简就成了：lambda f: lambda x: f(f(x))。

我们和one同样操作，换一个名字就得到了two的实现：

def two(f):
    """Church numeral 2: same as successor(successor(zero))"""
    "*** YOUR CODE HERE ***"
    return lambda x: f(f(x))

接下来是three，它的代码是题目中带的。

three = successor(two)

我们仿照上面的做法，代入一下successor，可以得到three = lambda f: lambda x: f(f(f(x)))。

到这里，我们就找到了规律，我们用函数的嵌套层数表达数字，嵌套了多少层就表示几。

下一题我们要做的是函数到整数的转换，本质上就是把函数解套的过程。

def church_to_int(n):
    """Convert the Church numeral n to a Python integer.

    >>> church_to_int(zero)
    0
    >>> church_to_int(one)
    1
    >>> church_to_int(two)
    2
    >>> church_to_int(three)
    3
    """
    "*** YOUR CODE HERE ***"

我刚开始想要通过递归来实现，但是发现有一个问题，即使我们解套到了0，得到的也依然是一个函数。后来苦苦思索的时候灵光一闪：既然这是一个层层嵌套的函数，我们能不能利用函数的嵌套性得到层数呢？

实现的方法也很简单，传入函数：f(x) = f(x) + 1即可。

def church_to_int(n):
    """Convert the Church numeral n to a Python integer.
    """
    "*** YOUR CODE HERE ***"
    f = lambda x: x+1
    return n(f)(0)

接下来，我们要实现整数的加法、乘法和乘方。

def add_church(m, n):
    """Return the Church numeral for m + n, for Church numerals m and n.

    >>> church_to_int(add_church(two, three))
    5
    """
    "*** YOUR CODE HERE ***"

def mul_church(m, n):
    """Return the Church numeral for m * n, for Church numerals m and n.

    >>> four = successor(three)
    >>> church_to_int(mul_church(two, three))
    6
    >>> church_to_int(mul_church(three, four))
    12
    """
    "*** YOUR CODE HERE ***"

def pow_church(m, n):
    """Return the Church numeral m ** n, for Church numerals m and n.

    >>> church_to_int(pow_church(two, three))
    8
    >>> church_to_int(pow_church(three, two))
    9
    """
    "*** YOUR CODE HERE ***"

所使用的方法类似，我们把m和n看成一个整体。m是m个f函数嵌套的整体，可以看成是关于函数f的函数，n是n个f函数嵌套的整体，当m和n传入的参数f相同时，我们要求m+n，即想办法获得一个m+n层的高阶函数，用数学表达式为：

f(f(...f[f(f(f(...(x)...)))]...))

，内部的括号为n层f嵌套，外层为m层括号嵌套。

由于m和n都是关于f的高阶函数，代入m和n的定义可以简写成：

m(f)(n(f)(x))

。

所以代码为：

def add_church(m, n):
    """Return the Church numeral for m + n, for Church numerals m and n.
    """
    "*** YOUR CODE HERE ***"
    return lambda f: lambda x: m(f)(n(f)(x))

计算m x n时，我们需要先把函数f嵌套n次，再把嵌套之后得到的n函数嵌套m次。这一次对于m函数而言，它的参数不再是函数f，而是函数n。

代码如下：

def mul_church(m, n):
    """Return the Church numeral for m * n, for Church numerals m and n.
    """
    "*** YOUR CODE HERE ***"
    return lambda f: lambda x: m(n(f))(x)

也可以简写成这样：

def mul_church(m, n):
    """Return the Church numeral for m * n, for Church numerals m and n.
    """
    "*** YOUR CODE HERE ***"
    return lambda f: m(n(f))

最后是乘方，我们要计算

m^n

，即实现m个n函数嵌套。已知

n(f)

的功能是将f函数嵌套n层，那么显然，我们把m函数看成是一个整体，自然是将m函数作为n函数的参数传入。

def pow_church(m, n):
    """Return the Church numeral m ** n, for Church numerals m and n.
    """
    "*** YOUR CODE HERE ***"
    return lambda f: n(m)(f)

也可以简化为：

def pow_church(m, n):
    """Return the Church numeral m ** n, for Church numerals m and n.
    """
    "*** YOUR CODE HERE ***"
    return n(m)

不知道到这里大家有没有发现问题，最大的问题是，m x n写成：lambda f: m(n(f))，

m^n

写成：lambda f: n(m)(f)。这两者看起来非常非常相似，为什么结果相差这么大呢？

最简单的解释就是作用对象不同，我们先来看第一个：lambda f: m(n(f))。我们把m和n分别看成是一个整体，在这行代码当中，n接收了一个参数f。而m接收的参数是n(f)。我们可以做一个换元，我们假设g = n(f)，那么m函数的入参就是g。

我们再来看第二行代码：lambda f: n(m)(f)，这里m函数没有入参，而n函数的入参是m。表面上一个入参是n(f)一个是m，好像差不多。其实相差很大。n(f)是n函数作用于f上的结果，这个结果不再具备将函数嵌套n层的能力。所以外层再套上m函数，得到的也只是这个结果本身嵌套m次。而n(m)不同，传入的参数是m本身，而非m作用之后的结果，m函数的功能就是将输入的函数嵌套m次，所以当它经过n函数作用于自身的时候，总层数会不停地乘上m。

不知道大家看到这里还好么，脑子蒙圈了没有。如果脑子蒙圈了，不要惊慌也不要怀疑智商，是非常非常正常的，高阶函数入参和返回结果都是函数，的确非常容易使人懵逼。我第一次做这些题的时候，足足用了一两个小时，怎么都想不明白。

但其实没啥大不了，一次想不明白，咬牙坚持反复思考了几次之后还是逐渐理解了，每思考一次，都觉得思路清晰了一些。几次下来，就没啥问题了。

所以大家首先不要害怕，多思考，多推敲，想不明白多想几次，也许就在下一刻，你会发现一切豁然开朗。

好了，关于这一次的作业就先聊到这里，感谢大家的阅读。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-04-07，如有侵权请联系 cloudcommunity@tencent.com 删除

serverless

编程算法

本文分享自 Coder梁微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

serverless

编程算法