1.6.高阶函数

发表于 2024-05-31 更新于 2024-06-02 分类于 SICP in python ， Chapter 1.Building Abstractions with Functions 阅读次数：本文字数： 3.4k 阅读时长 ≈ 12 分钟

\(1.6\)高阶函数

1.引入

由前面的讲解我们知道，函数是一种抽象方法，它描述独立于其参数的特定值的复合操作。 例如对函数\(square\)：

1 2	def square(x): return x*x

我们讨论的并不是某个特定的数的平方，而是对任何数的平方的普遍规律。同时，函数中的*也是一种抽象映射，代表乘法。当抽象映射较简单时，我们可以直接用符号来表示；但当抽象映射非常复杂时，我们就会用一个特定函数来实现这个抽象映射。

然而，在将相应的抽象映射转化为特定函数后，我们要将这个特定函数放入原有函数中，构造出能够接受该特定函数作为参数或返回函数作为值的函数。这样的函数即被称为高阶函数。

2.作为参数的函数

我们考虑对下面三种求和的代码实现：

\(1+2+\cdots +n\)

def sum1(n):
    tot,k=0,1
    while k<=n:
        tot,k=tot+k,k+1
    return tot

\(1^3+2^3+\cdots +n^3\)

def sum2(n):
    tot,k=0,1
    while k<=n:
        tot,k=tot+k,k+1
    return tot

\({4\over{1·3}}+{4\over{3·5}}+\cdots+{4\over{(2n-1)·(2n+1)}}\)

def sum2(n):
    tot,k=0,1
    while k<=n:
        tot,k=tot+4/((2*k-1)*(2*k+1)),k+1
    return tot

可以看出，上述求和都可以归纳为以下模式：

def sum(n):
    tot,k=0,1
    while k<=n:
        tot,k=f(k),k+1
    return tot

这种公共模式的存在强有力地证明了有一个有用的抽象正等待着被提出来。通过更进一步的抽象，我们的函数将不止能求解这些特定类型的求和，而是可以求出所有普遍意义上的求和。于是我们使用函数作为参数，将原来程序改写如下：

def sum_abstraction(n,f):
    tot,k=0,1
    while k<=n:
        tot,k=tot+f(k),k+1
    return tot

#以第2个求和为例
def f2(n):
    return n*n*n
#则sum2可以写成
def sum2:
    return sum_abstraction(n,f2)

3.作为一般方法的函数

上一节“作为参数的函数”中，我们用函数表示某种抽象数值运算模式，将某个具体的运算抽象化。在这一节中，我们将设计一些函数来表示一般的计算方法，它们独立于调用它们的函数。

我们考虑下面这个求解黄金分割比\(\varphi\)的程序。我们采用迭代的求法来求。函数的主体为迭代函数\(update\)与检查函数\(close\)，这里的每个函数都对应着一个一般方法。

对于迭代函数，由黄金分割比的性质：\(\varphi=1+{1\over{1+{1\over{1+{1\over{\cdots}}}}}}\)可以得到如下程序：

def update(guess):
    if not check(guess):
        guess=1/guess+1
    return guess

对于\(check\)函数，也即\(update\)的边界函数，由黄金分割比满足的方程：\(x^2=x+1\)可得如下程序：

def check(guess):
    return close(guess*guess,guess+1)

def close(a,b,tolerance=1e-15):
    return(abs(a-b)<tolerance)

从而得到最终的程序如下：

def solve(update,check,guess=1):
    while not check(guess):
        guess=update(guess)
    return guess

通过本题可以看出模块化编程思想的重要性：我们将整个程序拆成几个小的组件，在编写完每个组件后再进行合并，实现复杂的功能。同时我们在编写组件时，对每个抽象过程都可以先命名一个函数，把这个过程抽象化，然后再实现这一过程，这样可以有效降低函数的复杂性。

4.函数的嵌套定义

上面的示例演示了将函数作为参数传递的做法如何将每个一般概念或方程都映射到它自己的短函数上。但在这种方法中，由于每个短函数是在全局独立定义的，全局框架会因为众多函数的加入变得杂乱无章。同时，在某些场合中，我们需要让函数只保持一个参数，这时我们可以考虑建立嵌套函数。

以平方根的计算为例。我们一般通过以下程序迭代实现平方根的计算：

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

def sqrt_update(x,a):
    return average(x,a/x)

这两个函数都是双参的函数，而待实现的\(sqrt\)是单参函数；并且这两个函数单独调用只能实现一次更新。解决这个问题的方法是将函数定义放在其他定义的主体中。

def sqrt(a):
    def update(x):
        return average(x,a/x)
    def check(x):
        return close(x*x,a)
    return solve(update,close)

与局部赋值一样，局部\(def\)语句只影响当前的局部内容。当\(sqrt\)被计算时，这些函数只在作用域中。与我们的计算过程一致，在调用\(sqrt\)之前，这些本地\(def\)语句甚至不会被计算。由此可引出新概念：

词法范围：在函数内部被定义的函数可以共享定义它们的函数的参数。例如本例的\(update\)，其引用参数\(a\)就是封闭函数\(sqrt\)的参数。对于在封闭函数内定义的函数，\(a\)就相当于一个可以任意调用的常数。

由此，我们的变量环境就分成了两个环境：

每个用户自定义函数都有一个父环境：定义它的环境
当调用用户定义函数时，调用函数的内部扩展出的新环境

仍然以\(sqrt\)为例讲解嵌套函数。利用嵌套函数实现的\(sqrt\)计算如下：

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

def solve(update,check,guess=1):
    while not check(guess):
        guess=update(guess)
    return guess

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

def sqrt(a):
    def update(x,a/x):
        return average(x,a/x)

    def check:
        return eq(x*x,a)

    return solve(update,check)

result=sqrt(256)

该函数的执行流程及对应范围如下： 1. 定义函数，此时所有函数均为全局范围 2. 调用\(sqrt\)，此时\(def\)内部的\(update\)、\(check\)函数为词法范围，同时\(update\)、\(check\)继承词法范围内的变量\(a\) 3. 执行\(solve\)，通过迭代计算出\(sqrt\)的值。

通过本例我们也可以了解拓展环境的概念：

拓展环境：一个环境可以由任意长的框架链组成，框架链总是以全局框架结束。在\(sqrt\)之前，环境最多只有两个帧: 局部帧和全局帧。通过调用在其他函数中定义的函数，通过嵌套的\(def\)语句，我们可以创建更长的链。调用 \(update\)的环境由三个框架组成: 局部\(update\)框架、定义 \(update\)的\(sqrt\)框架和全局框架。

由上述框架的概念，我们可以得出框架的优先级：\(update\)先在本地框架中找\(a\)的值，没找到；于是\(update\)去定义\(update\)的\(sqrt\)框架找，找到\(256\)，于是\(a=256\)。

由此，我们得出了词法范围的优点：

局部函数的名称不会干扰定义它的函数的外部名称，因为局部函数名称将绑定在定义它的当前局部环境中，而不是全局环境中。
局部函数可以访问封闭函数的环境，因为局部函数体是在扩展其定义的封闭函数环境中进行定义的。

这种在本地框架中定义的函数被称为闭包，例如本题中的\(sqrt\)函数。在闭包中定义的函数可以获取闭包内的数据信息，而且闭包内的信息是封闭的、不会泄露到外部环境中。

5.作为返回值的函数

词法范围的一个重要特性是：本地定义的函数在返回时维护其父环境。下面举一个应用该特性的例子。

def combine(f,g):
    def h(x):
        return f(g(x))
    return h

这是复合函数的程序。正是通过本地定义函数继承父环境的性质，该函数实现了多个函数间的复合。

一般地，返回函数的函数具有以下优点：

灵活性和可复用性：函数作为返回值可以增加代码的灵活性。通过返回函数，你可以根据需要在运行时动态选择返回不同的实现，使得代码更加灵活和可复用。
封装和抽象：函数作为返回值有助于封装和抽象代码。你可以将一些复杂的逻辑封装在函数内部，然后返回这个函数，从而隐藏内部实现细节，使得接口更加简洁，提高代码的可维护性。
延迟执行：返回函数可以支持延迟执行的模式。例如，你可以返回一个函数对象，该对象在调用时才会执行具体的逻辑。这种延迟执行的方式有助于提高性能，特别是在涉及昂贵计算或者需要从外部获取资源的情况下。
函数封装：返回函数的能力使得函数成为一种函数工厂。你可以根据一些参数或者条件返回不同的函数，从而实现更加通用和可配置的代码结构。

6.高阶函数的经典应用

\(a.\)牛顿迭代法

\(i.\)牛顿迭代的原理

\(ii.\)牛顿迭代法的实现

我们考虑实现\(\sqrt[n]{a}\)的计算。首先令\(\sqrt[n]{a}=x\)，则问题转化为求\(x^n=a\)的实根。我们根据牛顿迭代法将程序拆分为以下模块： * 牛顿迭代函数的实现：由于我们要实现一个函数的封装，采用返回函数的高阶函数：

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

我们将抽象过程\(f\)与\(df\)命名为了两个函数，下面考虑如何实现两者。

\(f\)：\(f\)即为\(x^n\)

def f(x):
    return power(x,n)
```   
&emsp;&emsp;同理：
```python
def df(x):
    return n*power(x,n-1)

接下来是实现\(power\)：

\(power\):简单的连乘即可：

def power(x,n):
    mul,cnt=1,0
    while cnt<n:
        mul,cnt=mul*x,cnt+1
    return mul

寻找零点函数的实现：寻找零点分为两步：检验是否为零点与牛顿迭代。我们分别实现这两个功能，然后将它们封装为寻找零点函数：
- 检验是否为零点：判断\(f(x)-a\)是否在误差范围即可：
  1
  2
  def iszero(x):
  return eq(f(x),0)

函数封装：

def solve(update, is_zero):
    def iteratively_solve(x):
        while not is_approx_zero(x):
            x = update(x)
        return x
    return iteratively_solve

def find_zero(f,df):
    def is_zero(x):
        return eq(f(x),0)
    return solve(newton_update(f,df),is_zero)

最终函数封装：

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)

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

def improve(update, is_approx_zero, max_iter=1000):
    def iteratively_improve(x):
        iteration = 0
        while not is_approx_zero(x) and iteration < max_iter:
            x = update(x)
            iteration += 1
        return x
    return iteratively_improve

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

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 approx_eq(a, b, epsilon=1e-6):
    return abs(a - b) < epsilon

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)

\(b.\)\(Curry\)化

\(i.\)一般的\(Curry\)化

我们可以通过高阶函数的方法，可以将一个有很多参数的函数拆分成一个函数链，每个函数链节都是单参函数。

以双参函数\(pow(a,n)\)为例。我们可以用以下程序将\(pow(a,n)\)转化为\(h(a)(n)\)：

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

>>> curried_pow(2)(3)
8

除了满足单参的需求，由于将原函数拆成了多个函数，\(Curry\)化的函数还可以通过改动某个函数，使\(Curry\)化后的函数能实现不同的功能。例如下面计算\(2^1\sim 2^{10}\)的程序：

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

map_to_range(1,10,pow(2))

这里，\(Curry\)函数\(pow(2)\)只执行“以\(2\)为底”这一模块。而另一个参数“\(n\)次幂”则由\(map\_to\_range\)传递。

\(ii.\)自动化

以下程序可以实现对输入函数的\(Curry\)化与\(Uncurry\)化：

def curry(f):
    def g(x):
        def h(y):
            return f(x,y)
        return h
    return g

def uncurry(g):
    def f(x,y):
        return g(x)(y)
    return f
#调用
pow_curried=curry(pow)
pow=uncurry(pow_curried)

\(c.\)\(lambda\)表达式

\(lambda\)表达式可以在不声明函数的情况下，将变量转换为一个函数。下面这个程序就是\(lambda\)表达式：

1 2	def composel(f,g): return lambda x:f(g(x))

我们可以用如下表格理解\(lambda\)表达式的概念：

\(lambda\)表达式的返回值称作 \(lambda\)函数 。\(lambda\)函数没有内置名称，但可以和普通的函数一样调用：

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

对于较简单的函数，利用\(lambda\)表达式可以简化代码；但如果函数较为复杂，\(lambda\)就很可能给人带来理解上的困难。因此在代码较复杂、层层嵌套时，还是用传统的def为佳。