在Python中使用lambda函数添加教会数

Question

我正在自学Python和计算机科学，使用的是一个基于《计算机程序的构造和解释》的在线课程。我对教会数字的基本概念有一些了解，但在用Python的lambda函数来加法教会数字时遇到了困难。

下面是我的代码，供你参考：

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."""
    return lambda x: f(x)


def two(f):
    """Church numeral 2."""
    return lambda x: 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
    """
    return n(lambda x: x + 1)(0)


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

    >>> three = successor(two)
    >>> four = successor(three)
    >>> church_to_int(mul_church(two, three))
    6
    >>> church_to_int(mul_church(three, four))
    12
    """
    return lambda x: m(n(x))

这是我遇到问题的add_church函数：

def add_church(m, n):
    """Return the Church numeral for m + n, for Church numerals m and n.
    >>> three = successor(two)
    >>> church_to_int(add_church(two, three))
    5
    """
    return lambda f: lambda x: m(f(x))(n(x))

我认为加法教会数字的一种方法是让add_church(m, n)中的一个函数作为另一个函数的输入或“x”。但是，我总是收到错误提示，说明我在函数调用时使用了错误的参数。

举个例子，当我调用：

church_to_int(add_church(one, two))

我收到一个“int对象不可调用”的错误，还有其他错误。我也尝试了不同的方法，但都没有成功。

我觉得我对lambda函数的理解有些问题，这让我在实现add_church时遇到了麻烦。我已经花了很长时间在这个问题上，所以任何能帮助我找到答案的建议都将非常感谢。

Answer 1

回想一下，教堂编码可以理解为把一个函数反复应用到一个参数上。所以要计算 m + n，我们需要把一个函数 f 应用到一个参数 x 上，总共 m + n 次，或者说先应用 n 次，然后再应用 m 次：

def add_church(m, n):
    def m_plus_n(f):
        def f_repeated_m_plus_n_times(x)                # f ** (m + n)
            intermediate_result = (n(f))(x)             # (f ** n) (x)
            final_result = (m(f))(intermediate_result)  # (f ** m) ((f ** n) (x))
            return final_result
        return f_repeated_m_plus_n_times
    return m_plus_n

在 lambda 形式中，去掉多余的括号：

def add_church(m, n):
    """Return the Church numeral for m + n, for Church numerals m and n.
    >>> three = successor(two)
    >>> church_to_int(add_church(two, three))
    5
    """
    return lambda f: lambda x: m(f)(n(f)(x))