1.6 高阶函数

我们已经看到函数是一种抽象方法，它描述了独立于参数的特定值的复合操作。比如，在square中，

>>> def square(x):
        return x * x

我们讨论的不是某一特定数的平方，而是一种求任意数平方的方法。当然，我们可以不用定义这个函数，只要总是写这样的表达式

>>> 3 * 3
9
>>> 5 * 5
25

也没有明确提到square。 这种做法对于像平方这样的简单计算已经足够了，但是对于像abs或fib这样的更复杂的例子就变得困难了。 一般来说，缺少函数定义将使我们处于不利地位，因为它迫使我们总是在语言中碰巧是原语的特定操作(在本例中是乘法)的级别上工作，而不是在更高级别的操作中工作。 我们的程序可以计算平方，但是我们的语言缺乏表达平方概念的能力。

我们应该从强大的编程语言中要求的一件事是，能够通过为公共模式指定名称来构建抽象，然后直接根据名称工作。 函数提供了这种能力。 正如我们将在下面的示例中看到的，有一些常见的编程模式在代码中重复出现，但是与许多不同的函数一起使用。 这些模式也可以通过命名进行抽象。

要将特定的通用模式表示为命名的概念，我们需要构造可以接受其他函数作为参数或返回函数作为值的函数。 操纵函数的函数称为高阶函数。 本节将展示高阶函数如何作为强大的抽象机制，极大地增强语言的表达能力。

1.6.1 函数作为参数

考虑以下三个函数，它们都计算求和。

第一个是sum_naturals，计算到n的自然数之和：

>>> def sum_naturals(n):
        total, k = 0, 1
        while k <= n:
            total, k = total + k, k + 1
        return total
        
>>> sum_naturals(100)
5050

第二个是sum_cubes，它计算一直到n的自然数的立方体的和。

>>> def sum_cubes(n):
        total, k = 0, 1
        while k <= n:
            total, k = total + k*k*k, k + 1
        return total
        
>>> sum_cubes(100)
25502500

第三个是pi_sum，计算级数中各项的和

它收敛得很慢。

>>> def pi_sum(n):
        total, k = 0, 1
        while k <= n:
            total, k = total + 8 / ((4*k-3) * (4*k-1)), k + 1
        return total
        
>>> pi_sum(100)
3.1365926848388144

这三个函数显然共享一个共同的底层模式。它们在大多数情况下是相同的，只是名称和用于计算要添加的项的k函数不同。我们可以通过在同一个模板中填充槽来生成每个函数：

def <name>(n):
    total, k = 0, 1
    while k <= n:
        total, k = total + <term>(k), k + 1
    return total

这种常见模式的存在有力地证明，有一个有用的抽象正等着浮出水面。 每一个函数都是项的和。 作为程序设计者，我们希望我们的语言足够强大，这样我们就可以编写一个表达求和概念本身的函数，而不仅仅是计算特定求和的函数。 在Python中，我们可以很容易地使用上面所示的通用模板，并将“slot”转换为形式参数：

在下面的示例中，summation将上界n和计算第k项的函数term作为它的两个参数。 我们可以像使用任何函数一样使用summation，它简洁地表示求和。 花点时间逐步浏览一下这个示例，并注意如何将cube绑定到本地名term，以确保正确计算结果1*1*1 + 2*2*2 + 3*3*3 = 36。 在这个例子中，不再需要的框架被移除以节省空间。

使用返回参数的identity函数，我们也可以使用完全相同的summation函数对自然数求和。

>>> def summation(n, term):
        total, k = 0, 1
        while k <= n:
            total, k = total + term(k), k + 1
        return total
>>> def identity(x):
        return x
>>> def sum_naturals(n):
        return summation(n, identity)
>>> sum_naturals(10)
55

也可以直接调用summation函数，而不需要为特定序列定义另一个函数。

>>> summation(10, square)
385

通过定义一个函数pi_term来计算每一项，我们可以使用summation抽象来定义pi_sum。我们传递参数1e6(1 * 10^6 = 1000000的简写)来生成接近pi的值。

>>> def pi_term(x):
        return 8 / ((4*x-3) * (4*x-1))
>>> def pi_sum(n):
        return summation(n, pi_term)
>>> pi_sum(1e6)
3.141592153589902

1.6.2 函数作为通用方法

我们引入了用户定义函数作为一种机制来抽象数字运算的模式，从而使它们独立于所涉及的特定数字。 对于高阶函数，我们开始看到一种更强大的抽象：一些函数表达了通用的计算方法，与它们调用的特定函数无关。

尽管对函数的含义进行了这种概念上的扩展，但我们关于如何计算调用表达式的环境模型优雅地扩展到高阶函数的情况，没有改变。 当用户定义的函数被应用到一些参数时，形式形参被绑定到一个新的局部框架中这些参数的值(可能是函数)。

考虑下面的示例，它实现了迭代改进的通用方法，并使用它来计算黄金比例。 黄金分割率，通常被称为“phi”，是一个接近1.6的数字，经常出现在自然、艺术和建筑中。

迭代改进算法从对方程解的guess开始。 它反复应用update函数来改进猜测，并应用close比较来检查当前guess是否“足够接近”，可以认为是正确的。

>>> def improve(update, close, guess=1):
        while not close(guess):
            guess = update(guess)
        return guess

这个improve函数是重复细化的一般表达式。它没有指定要解决什么问题:这些细节留给作为参数传入的update和close函数。

黄金比例的一个众所周知的性质是，它可以通过重复地将任何正数的倒数与1相加来计算，而且它比它的平方数小1。我们可以将这些性质表示为函数，以便与improve一起使用。

>>> def golden_update(guess):
        return 1/guess + 1
>>> def square_close_to_successor(guess):
        return approx_eq(guess * guess, guess + 1)

上面，我们引入了一个对approx_eq的调用，如果它的参数大致相等，则该调用将返回True。为了实现approx_eq，我们可以比较两个数字之间的差的绝对值到一个小的tolerance值。

>>> def approx_eq(x, y, tolerance=1e-15):
        return abs(x - y) < tolerance

使用golden_update和square_close_to后继参数调用improve将计算黄金比例的有限近似值。

>>> improve(golden_update, square_close_to_successor)
1.6180339887498951

通过跟踪计算的步骤，我们可以看到这个结果是如何计算的。首先，使用update、close和guess的绑定构造一个用于improve的局部框架。在improve主体中，名称close被绑定到square_close_to后继函数，该函数在guess的初始值上被调用。跟踪其余步骤，以查看演变为计算黄金比例的计算过程。

这个例子说明了计算机科学中两个相关的大概念。 首先，命名和函数允许我们抽象出大量的复杂性。 虽然每个函数的定义都很简单，但是计算过程是非常复杂的。 其次，正是由于我们有一个非常通用的Python语言评估过程，小的组件可以被组合成复杂的过程。 理解解释程序的过程使我们能够验证和检查我们创建的过程。

和往常一样，我们新的改进的improve方法需要一个测试来检查它的正确性。 黄金比例可以提供这样一个测试，因为它也有一个精确的封闭形式的解，我们可以比较这个迭代结果。

>>> from math import sqrt
>>> phi = 1/2 + sqrt(5)/2
>>> def improve_test():
        approx_phi = improve(golden_update, square_close_to_successor)
        assert approx_eq(phi, approx_phi), 'phi differs from its approximation'
>>> improve_test()

对于这个测试，没有消息就是好消息:在它的assert语句成功执行之后，improve_test返回None。

1.6.3 定义函数III:嵌套定义

上面的示例演示了将函数作为参数传递的能力如何显著增强了编程语言的表达能力。 每个一般概念或方程都映射到它自己的短函数上。 这种方法的一个负面后果是，全局框架中充斥着小函数的名称，这些小函数的名称必须是唯一的。 另一个问题是，我们受到特定函数签名的限制:要改进的update参数必须只有一个参数。 嵌套函数定义解决了这两个问题，但是需要我们丰富我们的环境模型。

让我们考虑一个新问题：计算一个数的平方根。 在编程语言中，“平方根”通常缩写为sqrt。 重复应用下面的更新会收敛到a的平方根：

>>> def average(x, y):
        return (x + y)/2
>>> def sqrt_update(x, a):
        return average(x, a/x)

这个有两个参数的更新函数与improve不兼容(它有两个参数，而不是一个)，而且它只提供一个更新，而我们真正关心的是通过重复更新来求平方根。解决这两个问题的方法是将函数定义放在其他定义的主体中。

>>> def sqrt(a):
        def sqrt_update(x):
            return average(x, a/x)
        def sqrt_close(x):
            return approx_eq(x * x, a)
        return improve(sqrt_update, sqrt_close)

与局部赋值一样，局部def语句只影响当前的局部框架。这些函数仅在sqrt求值时才在作用域中。与我们的求值过程一致，这些局部def语句直到调用sqrt才会被求值。

词法作用域。局部定义的函数还可以访问定义它们的作用域中的名称绑定。在本例中，sqrt_update引用的是名称a，它是其外围函数sqrt的一个形式形参。这种在嵌套定义之间共享名称的原则称为词法作用域。关键的是，内部函数可以访问定义它们的环境中的名称(而不是调用它们的环境)。

为了启用词法作用域，我们需要对环境模型进行两个扩展。

1. 每个用户定义函数都有一个父环境：定义函数的环境。

2. 当用户定义的函数被调用时，它的本地框架继承它的父环境。

在sqrt之前，所有的函数都是在全局环境中定义的，所以它们都有相同的父类:全局环境。相比之下，当Python计算sqrt的前两个子句时，它会创建与本地环境相关联的函数。在调用

>>> sqrt(256)
16.0

该环境首先为sqrt添加一个本地框架，并计算sqrt_update和sqrt_close的def语句。

每个函数值都有一个新的注释，我们将从现在开始在环境图中包括它，一个父值。函数值的父值是定义该函数的环境的第一个框架。没有父注解的函数在全局环境中定义。当用户定义的函数被调用时，创建的框架与该函数具有相同的父值。

随后，名称sqrt_update将解析为这个新定义的函数，该函数将作为参数传递以进行改进。在improve函数体中，必须将update函数(绑定到sqrt_update)应用于初始猜测x(1)。这个最终的应用程序为sqrt_update创建了一个环境，该环境以仅包含x的本地帧开始，但父帧sqrt仍然包含a的绑定。

这个计算过程中最关键的部分是将sqrt_update的父进程传输到调用sqrt_update创建的框架。 这个框架也被注释为[parent=f1]。

扩展的环境。 一个环境可以由任意长的框架链组成，这些框架总是以全局框架结束。 在这个sqrt示例之前，环境最多有两个框架:一个局部框架和一个全局框架。 通过嵌套def语句调用在其他函数中定义的函数，可以创建更长的链。 调用sqrt_update的环境由三个框架组成:本地sqrt_update框架、定义了sqrt_update的sqrt框架(标记为f1)和全局框架。

sqrt_update函数体中的返回表达式可以通过遵循这一框架链来解析a的值。 在当前环境中查找绑定到该名称的第一个值。 Python首先检查sqrt_update帧——没有a存在。 Python在父帧f1中检查next，并找到a到256的绑定。

因此，我们认识到Python中词法作用域的两个关键优势。

1. 局部函数的名称不会与定义它的函数的外部名称相冲突，因为局部函数的名称将绑定在定义它的当前局部环境中，而不是全局环境中。

2. 局部函数可以访问外围函数的环境，因为局部函数的函数体是在扩展定义它的求值环境的环境中求值的。

sqrt_update函数携带一些数据：在定义它的环境中引用的值。 因为它们以这种方式“封装”信息，局部定义的函数通常被称为闭包。

1.6.4 函数作为返回值

通过创建返回值本身就是函数的函数，我们可以在程序中实现更强的表达能力。 词法作用域编程语言的一个重要特性是，本地定义的函数在返回时维护它们的父环境。 下面的示例演示了该特性的实用程序。

一旦定义了许多简单函数，函数组合就是编程语言中包含的一种自然的组合方法。 也就是说，给定两个函数f(x)和g(x)我们可以定义h(x) = f(g(x)) 我们可以使用现有的工具来定义函数组合：

>>> def compose1(f, g):
        def h(x):
            return f(g(x))
        return h

此示例的环境图显示了如何正确解析名称f和g，即使存在名称冲突。

compose1中的1表示组合函数都有一个参数。解释器不强制执行这种命名约定；1只是函数名的一部分。

在这一点上，我们开始观察我们努力精确定义计算的环境模型的好处。无需对环境模型进行任何修改，就可以解释以这种方式返回函数的能力。

1.6.5 例:牛顿法

这个扩展的示例展示了函数返回值和局部定义如何协作，以简明地表达一般概念。 我们将实现一种广泛应用于机器学习、科学计算、硬件设计和优化的算法。

牛顿法是一种经典的迭代方法，用于寻找数学函数的参数，该函数的返回值为0。 这些值称为函数的零点。 找到一个函数的零点通常等同于解决其他一些感兴趣的问题，例如计算平方根。

在我们继续之前，有一个激励人心的评论：我们很容易想当然地认为我们知道如何计算平方根。 不只是Python，但您的电话，web浏览器，或袖珍计算器可以为您这样做。 然而，学习计算机科学的一部分是了解如何计算这样的数量，这里提出的一般方法适用于求解Python内置的大量方程。

牛顿法是一种迭代改进算法：它对任何可微函数的零点猜测进行改进，这意味着它可以在任意点用一条直线来近似。牛顿法遵循这些线性近似来寻找函数零点。

假设一条经过点(x,f(x))的直线与函数f(x)在该点处的斜率相同。 这样一条直线叫做正切，它的斜率叫做f (x)的导数。

这条直线的斜率是函数值变化量与函数参数变化量的比值。 因此，将x平移f(x)除以斜率，就会得到切线与0交点处的参数值。

newton_update表示函数f及其导数df从这条切线到0的计算过程。

>>> def newton_update(f, df):
        def update(x):
            return x - f(x) / df(x)
        return update

最后，我们可以根据改进算法newton_update定义find_root函数，并比较f(x)是否接近于0。

>>> def find_zero(f, df):
        def near_zero(x):
            return approx_eq(f(x), 0)
        return improve(newton_update(f, df), near_zero)

计算根。使用牛顿法，我们可以计算任意次n的根。a的n次根为x，使x*x*x...x = a 用x重复n次。例如：

• 64的平方根是8，因为8任然8=64。

• 64的立方根(三)为4，因为4*4*4=64。

• 64 的6次根为2，这是因为任意2*2*2*2*2*2=64。

我们可以用牛顿法计算根，观察如下：

• 64的平方根(写成根号64)等于x，使x平方−64=0

• 更一般地说，设a的n次方为x，有x的n次方-a=0

如果我们能找到最后一个方程的0，那么我们就能计算n次方根。通过画出n = 2 3 6和a = 64的曲线，我们可以把这个关系形象化。

我们首先通过定义f及其导数df来实现square_root。我们从微积分中得到f(x)=x平方−a的导数是线性函数df(x)=2x。

>>> def square_root_newton(a):
        def f(x):
            return x * x - a
        def df(x):
            return 2 * x
        return find_zero(f, df)
>>> square_root_newton(64)
8.0

将其推广到任意次n的根，计算f(x)=x的n次方−a，其导数df(x)=n*x的(n-1)次方。

>>> def power(x, n):
        """Return x * x * x * ... * x for x repeated n times."""
        product, k = 1, 0
        while k < n:
            product, k = product * x, k + 1
        return product
>>> def nth_root_of_a(n, a):
        def f(x):
            return power(x, n) - a
        def df(x):
            return n * power(x, n-1)
        return find_zero(f, df)
>>> nth_root_of_a(2, 64)
8.0
>>> nth_root_of_a(3, 64)
4.0
>>> nth_root_of_a(6, 64)
2.0

所有这些计算中的近似误差可以通过改变approx_eq中的容差到一个更小的数字来减少。

当你用牛顿法实验时，要知道它并不总是收敛的。 改进函数的初始猜想必须足够接近于零，并且满足函数的各种条件。 尽管有这个缺点，牛顿法仍然是求解可微分方程的一种强大的通用计算方法。 对数和大整数除法的快速算法采用了现代计算机技术的变体。

1.6.6 柯里化

我们可以使用高阶函数将带多个实参的函数转换为每个函数带单个实参的函数链。更具体地说,函数f (x, y)，我们可以定义一个函数g，g (x) (y)相当于f (x, y)。在这里，g是一个高阶函数，它接受一个参数x和返回另一个函数，它接受一个参数y。这种转变称为柯里化。

例如，我们可以定义pow函数的curry版本：

>>> def curried_pow(x):
        def h(y):
            return pow(x, y)
        return h

>>> curried_pow(2)(3)
8

有些编程语言，如Haskell，只允许函数带一个参数，因此程序员必须curry所有的多参数过程。在Python等更通用的语言中，当需要一个只接受单个参数的函数时，套用是很有用的。例如，map模式对一个值序列应用一个单参数函数。在后面的章节中，我们会看到更多的map模式的例子，但现在，我们可以在函数中实现这个模式：

>>> def map_to_range(start, end, f):
        while start < end:
            print(f(start))
            start = start + 1

我们可以使用map_to_range和curried_pow来计算2的前10次幂，而不是专门编写一个函数来实现：

>>> map_to_range(0, 10, curried_pow(2))
1
2
4
8
16
32
64
128
256
512

我们也可以用同样的两个函数来计算其他数的幂。curry(柯里化)允许我们在不为每一个我们希望计算其幂的数字编写特定的函数的情况下这样做。

在上面的示例中，我们对pow函数手动执行了套用转换，以获得curried_pow。相反，我们可以定义自动柯里化的函数，以及逆柯里化的转换：

>>> def curry2(f):
        """Return a curried version of the given two-argument function."""
        def g(x):
            def h(y):
                return f(x, y)
            return h
        return g

>>> def uncurry2(g):
        """Return a two-argument version of the given curried function."""
        def f(x, y):
            return g(x)(y)
        return f

>>> pow_curried = curry2(pow)
>>> pow_curried(2)(5)
32
>>> map_to_range(0, 10, pow_curried(2))
1
2
4
8
16
32
64
128
256
512

curry2函数的双参数函数f，并返回一个单参数函数g。当g应用于一个参数x，它返回一个单参数函数h。当h应用于y，它调用f (x, y)。因此，curry2 (f) (x) (y)相当于f (x, y)。uncurry2逆柯里化的转换函数,以便uncurry2 (curry2 (f))相当于f。

1.6.7 Lambda表达式

到目前为止，每次我们想要定义一个新函数时，我们都需要给它一个名称。但是对于其他类型的表达式，我们不需要将中间值与名称相关联。也就是说，我们可以计算a*b + c*d，而不必命名子表达式a*b或c*d，或完整表达式。在Python中，我们可以使用lambda表达式动态创建函数值，该表达式的计算结果为未命名的函数。lambda表达式的计算结果是一个函数，它的函数体只有一个返回表达式。不允许使用赋值和控制语句。

>>> def compose1(f, g):
        return lambda x: f(g(x))

我们可以通过构造一个相应的英语句子来理解lambda表达式的结构：

     lambda            x            :          f(g(x))
"A function that    takes x    and returns     f(g(x))"

lambda表达式的结果称为lambda函数。它没有内在的名称(因此Python打印作为名称)，但在其他方面它的行为与任何其他函数一样。

>>> s = lambda x: x * x
>>> s
<function <lambda> at 0xf3f490>
>>> s(12)
144

在环境图中，lambda表达式的结果也是一个函数，用希腊字母λ (lambda)命名。我们的compose示例可以用lambda表达式非常紧凑地表达。

一些程序员发现使用lambda表达式中的未命名函数更短也更直接。然而，复合lambda表达式是出了名的难以辨认，尽管它们很简洁。下面的定义是正确的，但是许多程序员很难快速理解它。

>>> compose1 = lambda f,g: lambda x: f(g(x))

一般来说，Python风格更喜欢显式def语句而不是lambda表达式，但在需要简单函数作为参数或返回值的情况下也允许使用显式def语句。

这样的文体规则只是指导方针； 你可以用任何你想要的方式编程。 然而，在编写程序时，请考虑一下有一天可能会阅读您的程序的用户。 当您可以使您的程序更容易理解时，您就帮了那些人的忙。

lambda一词是由于书面数学符号的不兼容性和早期类型设置系统的约束而产生的历史意外。

It may seem perverse to use lambda to introduce a procedure/function. The notation goes back to Alonzo Church, who in the 1930's started with a "hat" symbol; he wrote the square function as "ŷ . y × y". But frustrated typographers moved the hat to the left of the parameter and changed it to a capital lambda: "Λy . y × y"; from there the capital lambda was changed to lowercase, and now we see "λy . y × y" in math books and (lambda (y) (* y y)) in Lisp.

—Peter Norvig

1.6.8 抽象和一级函数

在本节开始时，我们注意到用户定义函数是一种至关重要的抽象机制，因为它们允许我们将通用的计算方法表示为编程语言中的显式元素。 现在，我们已经了解了高阶函数如何允许我们操纵这些通用方法来创建进一步的抽象。

作为程序员，我们应该警惕在我们的程序中识别底层抽象的机会，在它们的基础上进行构建，并将它们一般化以创建更强大的抽象。 这并不是说人们应该总是以尽可能抽象的方式编写程序；专业的程序员知道如何选择适合他们任务的抽象级别。 但是，能够从这些抽象的角度来思考是很重要的，这样我们就可以准备好在新的环境中应用它们。 高阶函数的意义在于，它们使我们能够将这些抽象显式地表示为编程语言中的元素，这样它们就可以像处理其他计算元素一样处理。

一般来说，编程语言会对计算元素的操作方式施加限制。 限制最少的元素被称为具有一级状态。 一级元素的一些“权限和特权”是：

1. 它们可能与名字联系在一起。

2. 它们可以作为参数传递给函数。

3. 它们可以作为函数的结果返回。

4. 它们可以包含在数据结构中。

Python授予函数完全一流的地位，由此获得的表达能力是巨大的。

1.6.9 函数修饰符

Python提供了特殊的语法来应用高阶函数作为def语句执行的一部分，称为decorator。最常见的例子可能是trace：

>>> def trace(fn):
        def wrapped(x):
            print('-> ', fn, '(', x, ')')
            return fn(x)
        return wrapped

>>> @trace
    def triple(x):
        return 3 * x

>>> triple(12)
->  <function triple at 0x102a39848> ( 12 )
36

在本例中，定义了一个高阶函数跟踪，它使用print语句返回一个函数，该函数位于对其参数的调用之前，并输出参数。triple的def语句有一个注释@trace，它影响def的执行规则。通常，会创建函数triple。但是，name triple没有绑定到这个函数。相反，名称triple被绑定到在新定义的triple函数上调用trace的返回函数值。在代码中，这个装饰器等价于：

>>> def triple(x):
        return 3 * x

>>> triple = trace(triple)

在与此文本关联的项目中，装饰器用于跟踪，以及在从命令行运行程序时选择调用哪些函数。

额外的专家。 装饰符号@也可以跟在调用表达式后面。 @后面的表达式首先计算(就像上面的名称跟踪计算一样)，然后是def语句，最后是对装饰器表达式计算的结果应用于新定义的函数，结果绑定到def语句中的名称。 Ariel Ortiz的一个关于装饰师的简短教程为感兴趣的学生提供了进一步的例子。