Skip to content

Problem 7: Church Numerals (4pts)

Problem

The logician Alonzo Church invented a system of representing non-negative integers entirely using functions. The purpose was to show that functions are sufficient to describe all of number theory: if we have functions, we do not need to assume that numbers exist, but instead we can invent them.

Your goal in this problem is to rediscover this representation known as Church numerals. Here are the definitions of zero, as well as a function that returns one more than its argument:

逻辑学家阿隆佐·丘奇（Alonzo Church）发明了一种完全用函数来表示非负整数的系统。其目的是为了表明函数足以描述所有的数论：如果我们有了函数，我们就不需要假设数字的存在，而是可以发明它们。

您在此问题中的目标是重新发现这种被称为“丘奇数”（Church Numerals）的表示法。下面是 zero 的定义，以及一个返回比其参数大一的数字的函数：

def zero(f):
    return lambda x: x

def successor(n):
    return lambda f: lambda x: f(n(f)(x))

First, define functions one and two such that they have the same behavior as successor(zero) and successor(successor(zero)) respectively, but do not call successor in your implementation.

Next, implement a function church_to_int that converts a church numeral argument to a regular Python integer.

Finally, implement functions add_church, mul_church, and pow_church that perform addition, multiplication, and exponentiation on church numerals. For deeper understanding, church2int, iteration or recursion is forbidden from your implementation.

首先，定义函数 one 和 two，使它们的行为分别与 successor(zero) 和 successor(successor(zero)) 相同，但在您的实现中不能调用 successor。

接下来，实现一个函数 church_to_int，将一个丘奇数参数转换为一个普通的 Python 整数。

最后，实现函数 add_church、mul_church 和 pow_church，它们对丘奇数执行加法、乘法和指数运算。为了更深入地理解，您的实现中禁止使用 church_to_int、迭代或递归。

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 ***"


three = successor(two)

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 ***"


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 ***"

Hints

  • 思考丘奇数与函数幂之间的联系，尝试用数学方法进行推导。

Solutions

先理解题意。zero 相当于 f 的零次函数幂，one 是一次幂，以此类推。

那么，前几个函数就很明朗了。

注意 successor 返回的是一个函数，所以要先写 lambda f:。

n 首先将 f 调用了 n 次，因此 \(n(f(x))=f^n(x)\)。

然后我们需要再套一层 f，因此答案是 f(n(f)(x))

def zero(f):
    return lambda x: x


def successor(n):
    return lambda f: lambda x: f(n(f)(x))


def one(f):
    return f


def two(f):
    return lambda x: f(f(x))

接下来，我们可以取特值来实现 church_to_int。

def church_to_int(n):
    return n(lambda x: x + 1)(0)

因为 \(f^{m+n}(x)=f^m(f^n(x))\)，所以有

def add_church(m, n):
    return lambda f: lambda x: m(f)(n(f)(x))

而 \(f^{mn}(x)\) 是将 \(f^n\) 执行 \(m\) 次，所以有

def mul_church(m, n):
    return lambda x: m(n(x))

要让 f 执行 \(m^n\) 次，而 \(m\) 本来就是一个函数，所以我们需要计算 \(m\) 的 \(n\) 次函数幂。

def pow_church(m, n):
    return n(m)

如果你觉得这里的 return n(m) 难以理解，可以多写两个 lambda，尝试推导一下。

def pow_church(m, n):
    return lambda x: (lambda f: n(f))(m)(x)

或者使用标准的丘奇数表示法：

def pow_church(m, n):
    return lambda f: lambda x: n(m)(f)(x)