当前仅显示指定条件回帖 [ 展开查看全部 ]
02-15 11:05
文件名称:
2.2.3.1.5 High Order Functions.md
所在目录:
2.编程模块 / 2.2 Python 模块 / 2.2.3 CS Intro / 2.2.3.1 Building Abstraction with Functions
文件大小:
23.16 KB
下载地址:
文本预览:
# High Order Functions and Lambda Expressions （高阶函数和 Lambda 表达式）
从之前的章节里可以看到，函数作为一种抽象方法，描述的是与其参数的特定值无关的复合运算。
例如，在`square`函数中
```python
def square(x):
return x * x
```
我们讨论的不是获取某个特定数字平方的方法，而是在讨论获取任意数字的平方的一种方法。
对于简单诸如求平方这类的简单过程，我们可以不显式的使用square函数，而是直接编写下面的表达式。
```python
>>> 3 * 3
9
>>> 4 * 4
16
```
但是对于更复杂的过程，这种做法就变得不够优雅且较为困难了（如求fibonacci数列或开平方）。
一般来说，缺乏函数定义(function definition)会让我们编写程序变得相当困难，因为这将迫使我们始终在特定运算的层次上工作，而这些运算恰好是语言中的基元运算（本例中为乘法），而不是更高层次的运算。因此，虽然我们的程序可以计算平方，但我们的语言却缺乏表达平方概念的能力，这就把事情变得更加繁琐了。
因此，我们对功能强大的编程语言的要求之一，就是能够通过为常见模式命名的方式来建立抽象，然后直接根据这些名称进行工作。而函数提供了这种能力。正如我们将在下面的示例中看到的，有一些常见的编程模式(programming patterns)会在代码中重复出现，给这种相同的模式编写相似的函数，增加了不必要的重复。而通过给这些模式命名，我们可以把它们抽象化（再次增加一层**抽象壁垒**），从而写出清晰的代码。
而为了以命名概念的形式表达某些一般模式，我们需要构造一些函数，这些函数可以接受其他函数作为参数，也可以返回函数作为值。操纵函数的函数称为**高阶函数**。本节将展示高阶函数如何作为强大的抽象机制，极大地增强我们语言的表达能力。
## Functions as Argument 函数作为参数
考虑下面三个函数
第一个函数计算了不大于n的自然数之和：
```python
def sum_naturals(n):
total, k = 0, 1
while k <= n:
total, k = total + k, k + 1
return total
```
第一个函数计算了不大于n的自然数之立方和：
```python
def sum_naturals(n):
total, k = 0, 1
while k <= n:
total, k = total + k*k*k, k + 1
return total
```
第三个函数计算下面这个数列到n的和(收敛至$\pi$)：
$$\frac{8}{1\times 3}+\frac{8}{5\times 7}+...+ \frac{8}{4n-1\times 4n-3}$$
```python
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
```
这三个程序显然共享了一个共同的基本模式。它们在很大程度上是相同的，只有步骤的名称、用于计算要添加的项的 a 函数，以及提供 a 下一个值的函数有所不同。我们可以通过在相同的模板中填充``来生成每个程序：
```python
def(n):
total, k = 0, 1
while k <= n:
total, k = total +(k), k + 1
return total
```
这种常见模式的出现，有力地证明了有一个有用的抽象概念正等待着我们去挖掘。事实上，数学家很久以前就确定了级数求和的抽象，并发明了“σ符号”来表示这个概念，例如
$$\sum_{n=a}^b f(n) = f(a) + f(a+1) + ... + f(b-1) + f(b)$$
σ符号的威力在于它允许数学家处理求和概念本身，而不仅限于特定的求和问题。例如，可以对无论特定的求和序列如何进行求和，得出一般性的求和结果。
同样，作为程序设计者，我们希望我们的语言足够强大，这样我们就能编写出表达求和概念本身的程序，而不仅仅是计算特定和的程序。在我们的程序语言中，我们可以很容易地做到这一点，方法是采用上图所示的通用模板，并将上面的``转化为形式参数：
在下面的示例中，求和的两个参数是上界 n 和计算第 k 项的函数项。我们可以像使用任何函数一样使用求和，它能简洁地表达求和。请花点时间看一下这个例子，注意将 cube 与本地名称项绑定后，$1*1*1 + 2*2*2 + 3*3*3 = 36$ 的结果是如何正确计算的。
```python
def summation(n, term): def summation(n, term):
total, k = 0, 1
while k <= n:
total, k = total + term(k), k + 1
return total return
def cube(x):
return x*x*x
def sum_cubes(n):
return summation(n, cube)
result = sum_cubes(3)
```
使用返回其输入的参数的 identity 函数，我们还可以使用完全相同的 summation 函数求和自然数。
```python
>>> 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 函数也可以直接调用，无需为特定序列定义另一个函数。
```python
>>> summation(10, square)
385
```
可以通过使用我们的抽象 summation 来定义 pi_sum ，通过定义一个函数 pi_term 来计算每个项。我们将参数 1e6 （ 1 * 10^6 = 1000000 的简写）传递进去，以生成一个接近 π 的近似值。
```python
>>> 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
```
有了summation 函数，我们可以将其作为构建进一步概念的基石。例如求函数$f(x)$在a到b上的定积分。有兴趣的同学可以在MIT开源的教材SICP[^1]找到一些习题。不过需要注意的是，MIT使用Scheme(一种函数式编程语言Lisp的方言)作为其教学语言，但是影响不大，能稍微领会其，知道写的函数在干什么就足够了。
## Functions as General Methods 函数作为一般性的方法
我们介绍过用户自定义函数，它是一种对数字运算模式进行抽象的机制，从而使运算与所涉及的特定数字无关。有了高阶函数，我们开始看到一种更强大的抽象：一些函数表达了通用的计算方法，与它们调用的特定函数无关。
尽管我们对函数的含义进行了概念上的扩展，但我们关于如何评估调用表达式的环境模型仍可优雅地扩展到高阶函数的情况，而不会发生任何变化。当用户定义的函数被应用到某些参数时，形式参数会被绑定到新的局部框架中的参数值（可能是函数）。
请看下面的示例，它实现了迭代改进的一般方法，并用于计算黄金分割率。黄金分割率通常被称为 "phi"，是一个接近 1.6 的数字，经常出现在自然、艺术和建筑中。
迭代改进算法从方程解的猜测开始。它反复应用一个更新函数来改进这个猜测，并应用近似比较来检查当前的猜测是否 "足够接近 "被认为是正确的。
```python
>>> def improve(update, close, guess=1):
while not close(guess):
guess = update(guess)
return guess
```
这个`improve`函数是重复的细节的一般表达式。它没有说明要解决的问题是什么：这些细节都留给了作为参数传递进来的`update`和` close `函数。
我们在小学二年级学过,黄金分割率有两个的特性，一是可以通过重复求任何正数的倒数与 1 的和来计算，二是黄金分割率比它的平方小 1。我们可以将这些性质表示为可以被`improve`使用的函数。
```python
>>> 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` ，我们可以将两个数字之间的差的绝对值与一个小的容差值进行比较。
```python
>>> def approx_eq(x, y, tolerance=1e-15):
return abs(x - y) < tolerance
```
调用 `improve` ，使用参数 `golden_update` 和 `square_close_to_successor` 将计算黄金比例的有限近似值。
```python
>>> improve(golden_update, square_close_to_successor)
1.6180339887498951
```
这个例子说明了计算机科学中的两个相关的重要思想。首先，命名和函数可以使我们把大量的复杂性抽象化。虽然每个函数定义都很简单，但我们的评估过程引发的计算过程非常复杂。其次，正是由于我们对 Python 语言有一个非常普遍的评估过程，所以可以将小组件组合成复杂的过程。理解程序的解释过程使我们能够验证和检查我们创建的过程。
像往常一样，我们新的通用方法 `improve` 需要一个测试来检查其正确性。黄金比率可以提供这样一个测试，因为它也有一个精确的闭式解，我们可以将其与这个迭代结果进行比较。
```python
>>> 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()
```
对于这个测试，没有消息就是好消息： `improve_test` 在其 `assert` 语句执行成功后返回 None 。
## Functions as Return Value 函数作为返回值
上面的示例说明了，将函数作为参数能极大地增强了编程语言的表达能力。通过创建返回值本身就是函数的一类函数，我们甚至可以获得更强的表达能力。
一旦定义了许多简单的函数，函数组合就自然而然地成为我们编程语言中的一种组合方法。也就是说，给定两个函数 `f(x)` 和 `g(x)`，我们可能想定义 `h(x)` = `f(g(x))`。我们可以使用现有工具定义函数组合：
```python
def compose1(f, g):
def h(x):
return f(g(x))
return h
```
接下来我们来看一个拓展示例，它是我们前文提到的牛顿迭代法更为一般化的版本。
牛顿法是一种经典的迭代方法，用于找到数学函数的参数，使其返回值为 0。这些值被称为函数的零点。找到函数的零点通常等价于解决其他感兴趣的问题，比如计算平方根。
牛顿法是一种迭代改进算法：它改进了对任何可微分函数零点的猜测，这意味着它可以在任意点用直线逼近。牛顿法根据这些直线近似值来寻找函数的零点。
试想一条通过点$(𝑥,𝑓(𝑥))$的直线，其斜率与函数$𝑓(𝑥)$在该点的曲线相同。这样的直线称为切线，其斜率称为$𝑓$在$𝑥$处的导数。对于函数$f$及其导数$df$，`newton_update` 表示沿着这条切线到 0 的计算过程。
```python
def newton_update(f, df):
def update(x):
return x - f(x) / df(x)
return update
```
接着，我们可以通过定义一个使用`newton_update`和`improve`的`find_root`函数来查看$f(x)$是否接近0.
```python
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$次方和求函数$x^n -a =0 $是等价的。
考虑最简单的求平方根，我们首先定义函数$f$和它的导数$df$。利用一些初等的微积分知识，我们知道$f(x)=x^2-a$，$df(x)=2x$。因此，下面我们用定义一个求平方根的函数。
```python
def square_root_newton(a):
def f(x):
return x * x - a
def df(x):
return 2 * x
return find_zero(f, df)
```
```python
>>>square_root_newton(64)
8.0
```
我们把求根的方法一般化到求任意次方根$n$，我们计算
$$f(x)=x^n−a$$
及其导数
$$df(x)=n⋅ x^{n−1}$$
```python
>>> 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
```
不过需要注意的是使用牛顿法时，它并不总是收敛的。初始猜测值 `improve`必须足够接近零，并且必须满足关于函数的各种条件。尽管存在这些缺陷，牛顿法是一种强大的通用计算方法，用于解决可微方程。现代计算机中用于对数和大整数除法的快速算法采用了这种技术的变体。
## Curry 柯里化
~~柯里化是一种把接受多个参数的函数转换成咖喱的技术~~
柯里化的主要思想是将一个$n$元函数转换为$n$个一元函数的嵌套调用。例如，原始函数$f(a, b, c)$ 可以被转换为$f(a)(b)(c)$。这种技术在函数式编程中非常常见，有助于函数的部分应用（Partial Application），即固定函数的一些参数，从而生成一个新的函数。换句话说，柯里化函数每次只接受一个参数，并返回一个新的函数，直到所有参数都被接受为止。
下面是一个柯里化pow函数的例子：
```python
>>>def curried_pow(x):
def inner(y):
return pow(x, y)
return inner
>>>cured_pow(2)(3)
8
```
一些编程语言，如 Haskell，只允许接受单个参数的函数，因此程序员必须对所有多参数过程进行柯里化。在诸如 Python 之类的更一般的语言中，当我们需要一个只接受一个参数的函数时，柯里化也是有用的。例如，`map`函数将单参数函数应用于一系列值。在后面的章节中，我们将看到更一般的映射模式的示例，但现在，我们可以在一个函数中实现该模式：
```python
>>> def map_to_range(start, end, f):
while start < end:
print(f(start))
start = start + 1
```
我们可以使用 `map_to_range` 和 `curried_pow` 来计算 2 的前十次幂，而不是专门编写一个函数来实现：
```python
>>> map_to_range(0, 10, curried_pow(2))
1
2
4
8
16
32
64
128
256
512
```
类似地，我们可以使用相同的两个函数来计算其他数字的幂。科里化使我们我们无需为每个要计算幂的数字编写特定函数，就能完成计算。
在上面的例子中，我们手动对 `pow` 函数进行了柯里化变换，得到了 `curried_pow` 。而实际上，我们可以定义一些函数来自动化柯里化，以及逆变换未柯里化：
```python
>>> 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`。
## Lambda Functions lambda函数
在讲python中的$\lambda$函数前，我想先掰扯几句它的历史和一些数学背景。
一切要从上个世纪初，也就是 1900 年左右开始说起了。那时候数学界的气象是这样的：希尔伯特刚刚提出他的23个问题，其中第2个问题问的是公理系统的相容性；1901年提出的，动摇了集合论基础的罗素悖论还是个很流行的话题；至于哥德尔不完备性定理呢，大家都还不知道。所以在这之后的几十年很多数学家和逻辑学家都在致力于给整个数学建立一个一致的公理基础。比如罗素和怀特海德写了 “数学原理（ Principia Mathematica）”；比如约翰·冯·诺伊曼写了关于公理化集合论的博士论文；再比如阿隆佐·邱奇（Alonzo Church）提出了 𝜆 演算 。
邱奇发明λ演算实在二十世纪三十年代左右，其初衷是设计一套形式系统，代替罗素的类型理论和Zermelo的集合理论，来给逻辑学提供一个基础。然鹅这个系统在发表不久之后就被发现有矛盾，当然现在我们早已知道哥德尔不完备性定理威力之大，但是当时的逻辑学家们对这一定理的威力没有清晰而广泛的认知，因此那时邱奇还希望这个定理不会拓展到它的系统上。1935年，邱奇的两个学生Stephen Kleene 和 Barkley Rosser 发现邱奇的逻辑系统是不一致的。
然而他们发现系统中的纯λ演算有一系列良好的性质，后来更是证明用λ演算可以等价定义出可计算函数，这就是著名的“邱奇-图灵论题”的一部分了。更一进步的，邱奇用 𝜆 演算证明了一阶逻辑不存在递归判定过程，这是对希尔伯特提出的判定性问题（Entscheidungs problem）的第一个否定性答案，这比用图灵证明停机问题不可判定还要早几个月。1936年，阿兰·图灵发明了图灵机。图灵把解决判定问题的通用解法是否存在的问题归约到停机问题。而图灵后来证明了λ演算和图灵机是等价的计算模型。
不过二十世纪三十年代在 𝜆 演算方面的成果差不多也就这些了，再接下来的 20 年都没有太多研究和进展。直到六十年代，那时有了计算机，有了程序设计语言，有了计算机科学家。在 1965 年，英国计算机科学家 Peter Landin 发现可以通过把复杂的程序语言转化成简单的 𝜆 演算，来理解程序语言的行为。这个洞见可以让我们把 𝜆 演算本身看成一种程序设计语言。而众所周知的 John McCarthy 的Lisp 语言，更是让 𝜆 演算广为传播。现在不论是各种实际的程序设计语言还是理论上的研究工作，𝜆演算都是一个绕不过去的基本工具了。
我们先从数学开始说起。函数是数学中一个非常基础的概念，当然在python中也是。在数学上，我们可以很轻松的写出一个叫$f$的计算平方和的函数,而有了函数也能方便我们后续的计算
$$
\begin{gather}
f(x, y) = x^2 + y^2 \tag{1}
\end{gather}
$$
$$
\begin{gather}
f(2,3) = 2^2 + 3^2 = 13 \tag*{}
\end{gather}
$$
但是事实上，名字对于一个函数来说也并不是必须的，下面的映射也表示的平方和的函数
$$
\begin{gather}
(x, y) \mapsto x^2 + y^2 \tag{2}
\end{gather}
$$
我们用(2)的整体作为函数的名字也一样能表示计算平方的过程
$$
\begin{gather}
(x, y) \mapsto x^2 + y^2(2,3) = 2^2 + 3^2 = 13 \tag*{}
\end{gather}
$$
我们把 (2) 称为匿名函数，它有两个参数。那么再问，单参数函数和多参数函数的区分有必要吗？
可以换个角度来看，我们把 (2) 改写成下面这个样子：
$$
\begin{gather}
x \mapsto(y \mapsto x^2 + y^2 ) \tag{3}
\end{gather}
$$
这个映射是什么意思呢？我们一步一步来。首先是$x$被映射成了$y \mapsto x^2 + y^2$，后者是一个以y为参数的函数。因此我们可以把(3)理解成：把一个数映射成函数的函数，这就是我们说的高阶函数(HOF).
值得注意的是，现在的(3)是一个单参数函数，我们可以先给它一个参数，比如 $2$，我们便可以得到下面的一个函数：
$$
\begin{gather}
x \mapsto(y \mapsto x^2 + y^2 )(2) = y \mapsto 4 + y^2 \tag*{}
\end{gather}
$$
再给这个函数一个参数，比如$3$，我们便可以得到：
$$
\begin{gather}
y \mapsto 4 + y^2(3) = 4 + 3^2 = 13 \tag*{}
\end{gather}
$$
这样我们就搞清楚了(3)是如何进行平方和运算的。而运用类似的方法，我们可以把任意多个参数的函数转换为单参数的高阶函数，这就是我们上一节讲到的柯里化(Currying)。
匿名函数和柯里化λ运算为简化函数概念采取的方法，上面这段说明可以看作是lambda运算的非正式介绍。事实上，大多数编程语言里的所谓Lambda表达式也就是把这两个概念组合在一起罢了，Python也不例外。而如果你想要更深入的了解λ演算，下面放了一些一些推荐的博客与书。[^2]
咳咳咳，嗯。让我们回归正题，现在来看看python中的Lambda表达式。到目前为止，每当我们想要定义一个新函数时，我们都需要给它一个名字。但对于其他类型的表达式，我们不需要将中间值与名称关联起来。也就是说，我们可以计算 a*b + c*d 而不必给子表达式 a*b 或 c*d 或完整表达式命名。在 Python 中，我们可以使用 lambda 表达式临时创建函数值，它们会评估为匿名函数。λ表达式会评估为只有一个返回表达式作为其函数体的函数。不允许赋值和控制语句。比如下面一个例子
```python
>>> 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))|
λ表达式的结果称为λ函数。它没有固有名称（因此 Python 打印`` 作为名称），但除此之外，它的行为就像任何其他函数。
```python
>>> s = lambda x: x * x
>>> s
at 0xf3f490>
>>> s(12)
144
```
虽然说匿名的lambda表达式更短，更直接。但是就像一把双刃剑一样，如果不当的使用lambda表达式会让你对程序变得难以阅读~~这或许提高了你的不可替代性，但是过了一段时间再去看这段代码可能你也不知道你写了什么xd~~。 以下定义是正确的，但许多程序员很难快速理解。
```python
>>> compose1 = lambda f,g: lambda x: f(g(x))
```
一般来说，Python风格的代码(pythonic code)更喜欢使用显式def语句而不是lambda表达式，但允许在需要简单函数作为参数或返回值的情况下使用它们。
## *Abstraction and First-Class Functions 抽象机制与一等公民*
可以看看这篇文章[^3]。
## *Function Decorators 函数装饰器*
摆了，可以去看看文档、问GPT
[^1]:[SICP](https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-12.html)
[^2]: About Lambda Calculus 1. [让我们谈谈Lambda演算](https://github.com/txyyss/Lambda-Calculus/tree/master)
[不知道什么时候的博客了](https://cgnail.github.io/tags/#lambda%E6%BC%94%E7%AE%97)
[同样也是不知道什么时候的博客](https://liujiacai.net/blog/2014/10/12/lambda-calculus-introduction/#%CE%BB%E6%BC%94%E7%AE%97%E7%9A%84%E8%AF%AD%E6%B3%95%E4%B8%8E%E6%B1%82%E5%80%BC)
[A Tutorial Introduction to the Lambda Calculus](https://arxiv.org/pdf/1503.09060)
[The Lambda Calculus for Absolute Dummies](https://palmstroem.blogspot.com/2012/05/lambda-calculus-for-absolute-dummies.html)
如果你对计算理论感兴趣，可以去看看CS154的课程[Introduction to the Theory of Computing](https://www.youtube.com/channel/UCrz06enpAptXhu4pYJfR-EQ/videos)
[^3]:[一等公民的函数](https://llh911001.gitbooks.io/mostly-adequate-guide-chinese/content/ch2.html)
从之前的章节里可以看到，函数作为一种抽象方法，描述的是与其参数的特定值无关的复合运算。
例如，在`square`函数中
```python
def square(x):
return x * x
```
我们讨论的不是获取某个特定数字平方的方法，而是在讨论获取任意数字的平方的一种方法。
对于简单诸如求平方这类的简单过程，我们可以不显式的使用square函数，而是直接编写下面的表达式。
```python
>>> 3 * 3
9
>>> 4 * 4
16
```
但是对于更复杂的过程，这种做法就变得不够优雅且较为困难了（如求fibonacci数列或开平方）。
一般来说，缺乏函数定义(function definition)会让我们编写程序变得相当困难，因为这将迫使我们始终在特定运算的层次上工作，而这些运算恰好是语言中的基元运算（本例中为乘法），而不是更高层次的运算。因此，虽然我们的程序可以计算平方，但我们的语言却缺乏表达平方概念的能力，这就把事情变得更加繁琐了。
因此，我们对功能强大的编程语言的要求之一，就是能够通过为常见模式命名的方式来建立抽象，然后直接根据这些名称进行工作。而函数提供了这种能力。正如我们将在下面的示例中看到的，有一些常见的编程模式(programming patterns)会在代码中重复出现，给这种相同的模式编写相似的函数，增加了不必要的重复。而通过给这些模式命名，我们可以把它们抽象化（再次增加一层**抽象壁垒**），从而写出清晰的代码。
而为了以命名概念的形式表达某些一般模式，我们需要构造一些函数，这些函数可以接受其他函数作为参数，也可以返回函数作为值。操纵函数的函数称为**高阶函数**。本节将展示高阶函数如何作为强大的抽象机制，极大地增强我们语言的表达能力。
## Functions as Argument 函数作为参数
考虑下面三个函数
第一个函数计算了不大于n的自然数之和：
```python
def sum_naturals(n):
total, k = 0, 1
while k <= n:
total, k = total + k, k + 1
return total
```
第一个函数计算了不大于n的自然数之立方和：
```python
def sum_naturals(n):
total, k = 0, 1
while k <= n:
total, k = total + k*k*k, k + 1
return total
```
第三个函数计算下面这个数列到n的和(收敛至$\pi$)：
$$\frac{8}{1\times 3}+\frac{8}{5\times 7}+...+ \frac{8}{4n-1\times 4n-3}$$
```python
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
```
这三个程序显然共享了一个共同的基本模式。它们在很大程度上是相同的，只有步骤的名称、用于计算要添加的项的 a 函数，以及提供 a 下一个值的函数有所不同。我们可以通过在相同的模板中填充`
```python
def
total, k = 0, 1
while k <= n:
total, k = total +
return total
```
这种常见模式的出现，有力地证明了有一个有用的抽象概念正等待着我们去挖掘。事实上，数学家很久以前就确定了级数求和的抽象，并发明了“σ符号”来表示这个概念，例如
$$\sum_{n=a}^b f(n) = f(a) + f(a+1) + ... + f(b-1) + f(b)$$
σ符号的威力在于它允许数学家处理求和概念本身，而不仅限于特定的求和问题。例如，可以对无论特定的求和序列如何进行求和，得出一般性的求和结果。
同样，作为程序设计者，我们希望我们的语言足够强大，这样我们就能编写出表达求和概念本身的程序，而不仅仅是计算特定和的程序。在我们的程序语言中，我们可以很容易地做到这一点，方法是采用上图所示的通用模板，并将上面的`
在下面的示例中，求和的两个参数是上界 n 和计算第 k 项的函数项。我们可以像使用任何函数一样使用求和，它能简洁地表达求和。请花点时间看一下这个例子，注意将 cube 与本地名称项绑定后，$1*1*1 + 2*2*2 + 3*3*3 = 36$ 的结果是如何正确计算的。
```python
def summation(n, term): def summation(n, term):
total, k = 0, 1
while k <= n:
total, k = total + term(k), k + 1
return total return
def cube(x):
return x*x*x
def sum_cubes(n):
return summation(n, cube)
result = sum_cubes(3)
```
使用返回其输入的参数的 identity 函数，我们还可以使用完全相同的 summation 函数求和自然数。
```python
>>> 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 函数也可以直接调用，无需为特定序列定义另一个函数。
```python
>>> summation(10, square)
385
```
可以通过使用我们的抽象 summation 来定义 pi_sum ，通过定义一个函数 pi_term 来计算每个项。我们将参数 1e6 （ 1 * 10^6 = 1000000 的简写）传递进去，以生成一个接近 π 的近似值。
```python
>>> 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
```
有了summation 函数，我们可以将其作为构建进一步概念的基石。例如求函数$f(x)$在a到b上的定积分。有兴趣的同学可以在MIT开源的教材SICP[^1]找到一些习题。不过需要注意的是，MIT使用Scheme(一种函数式编程语言Lisp的方言)作为其教学语言，但是影响不大，能稍微领会其，知道写的函数在干什么就足够了。
## Functions as General Methods 函数作为一般性的方法
我们介绍过用户自定义函数，它是一种对数字运算模式进行抽象的机制，从而使运算与所涉及的特定数字无关。有了高阶函数，我们开始看到一种更强大的抽象：一些函数表达了通用的计算方法，与它们调用的特定函数无关。
尽管我们对函数的含义进行了概念上的扩展，但我们关于如何评估调用表达式的环境模型仍可优雅地扩展到高阶函数的情况，而不会发生任何变化。当用户定义的函数被应用到某些参数时，形式参数会被绑定到新的局部框架中的参数值（可能是函数）。
请看下面的示例，它实现了迭代改进的一般方法，并用于计算黄金分割率。黄金分割率通常被称为 "phi"，是一个接近 1.6 的数字，经常出现在自然、艺术和建筑中。
迭代改进算法从方程解的猜测开始。它反复应用一个更新函数来改进这个猜测，并应用近似比较来检查当前的猜测是否 "足够接近 "被认为是正确的。
```python
>>> def improve(update, close, guess=1):
while not close(guess):
guess = update(guess)
return guess
```
这个`improve`函数是重复的细节的一般表达式。它没有说明要解决的问题是什么：这些细节都留给了作为参数传递进来的`update`和` close `函数。
我们在小学二年级学过,黄金分割率有两个的特性，一是可以通过重复求任何正数的倒数与 1 的和来计算，二是黄金分割率比它的平方小 1。我们可以将这些性质表示为可以被`improve`使用的函数。
```python
>>> 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` ，我们可以将两个数字之间的差的绝对值与一个小的容差值进行比较。
```python
>>> def approx_eq(x, y, tolerance=1e-15):
return abs(x - y) < tolerance
```
调用 `improve` ，使用参数 `golden_update` 和 `square_close_to_successor` 将计算黄金比例的有限近似值。
```python
>>> improve(golden_update, square_close_to_successor)
1.6180339887498951
```
这个例子说明了计算机科学中的两个相关的重要思想。首先，命名和函数可以使我们把大量的复杂性抽象化。虽然每个函数定义都很简单，但我们的评估过程引发的计算过程非常复杂。其次，正是由于我们对 Python 语言有一个非常普遍的评估过程，所以可以将小组件组合成复杂的过程。理解程序的解释过程使我们能够验证和检查我们创建的过程。
像往常一样，我们新的通用方法 `improve` 需要一个测试来检查其正确性。黄金比率可以提供这样一个测试，因为它也有一个精确的闭式解，我们可以将其与这个迭代结果进行比较。
```python
>>> 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()
```
对于这个测试，没有消息就是好消息： `improve_test` 在其 `assert` 语句执行成功后返回 None 。
## Functions as Return Value 函数作为返回值
上面的示例说明了，将函数作为参数能极大地增强了编程语言的表达能力。通过创建返回值本身就是函数的一类函数，我们甚至可以获得更强的表达能力。
一旦定义了许多简单的函数，函数组合就自然而然地成为我们编程语言中的一种组合方法。也就是说，给定两个函数 `f(x)` 和 `g(x)`，我们可能想定义 `h(x)` = `f(g(x))`。我们可以使用现有工具定义函数组合：
```python
def compose1(f, g):
def h(x):
return f(g(x))
return h
```
接下来我们来看一个拓展示例，它是我们前文提到的牛顿迭代法更为一般化的版本。
牛顿法是一种经典的迭代方法，用于找到数学函数的参数，使其返回值为 0。这些值被称为函数的零点。找到函数的零点通常等价于解决其他感兴趣的问题，比如计算平方根。
牛顿法是一种迭代改进算法：它改进了对任何可微分函数零点的猜测，这意味着它可以在任意点用直线逼近。牛顿法根据这些直线近似值来寻找函数的零点。
试想一条通过点$(𝑥,𝑓(𝑥))$的直线，其斜率与函数$𝑓(𝑥)$在该点的曲线相同。这样的直线称为切线，其斜率称为$𝑓$在$𝑥$处的导数。对于函数$f$及其导数$df$，`newton_update` 表示沿着这条切线到 0 的计算过程。
```python
def newton_update(f, df):
def update(x):
return x - f(x) / df(x)
return update
```
接着，我们可以通过定义一个使用`newton_update`和`improve`的`find_root`函数来查看$f(x)$是否接近0.
```python
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$次方和求函数$x^n -a =0 $是等价的。
考虑最简单的求平方根，我们首先定义函数$f$和它的导数$df$。利用一些初等的微积分知识，我们知道$f(x)=x^2-a$，$df(x)=2x$。因此，下面我们用定义一个求平方根的函数。
```python
def square_root_newton(a):
def f(x):
return x * x - a
def df(x):
return 2 * x
return find_zero(f, df)
```
```python
>>>square_root_newton(64)
8.0
```
我们把求根的方法一般化到求任意次方根$n$，我们计算
$$f(x)=x^n−a$$
及其导数
$$df(x)=n⋅ x^{n−1}$$
```python
>>> 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
```
不过需要注意的是使用牛顿法时，它并不总是收敛的。初始猜测值 `improve`必须足够接近零，并且必须满足关于函数的各种条件。尽管存在这些缺陷，牛顿法是一种强大的通用计算方法，用于解决可微方程。现代计算机中用于对数和大整数除法的快速算法采用了这种技术的变体。
## Curry 柯里化
~~柯里化是一种把接受多个参数的函数转换成咖喱的技术~~
柯里化的主要思想是将一个$n$元函数转换为$n$个一元函数的嵌套调用。例如，原始函数$f(a, b, c)$ 可以被转换为$f(a)(b)(c)$。这种技术在函数式编程中非常常见，有助于函数的部分应用（Partial Application），即固定函数的一些参数，从而生成一个新的函数。换句话说，柯里化函数每次只接受一个参数，并返回一个新的函数，直到所有参数都被接受为止。
下面是一个柯里化pow函数的例子：
```python
>>>def curried_pow(x):
def inner(y):
return pow(x, y)
return inner
>>>cured_pow(2)(3)
8
```
一些编程语言，如 Haskell，只允许接受单个参数的函数，因此程序员必须对所有多参数过程进行柯里化。在诸如 Python 之类的更一般的语言中，当我们需要一个只接受一个参数的函数时，柯里化也是有用的。例如，`map`函数将单参数函数应用于一系列值。在后面的章节中，我们将看到更一般的映射模式的示例，但现在，我们可以在一个函数中实现该模式：
```python
>>> def map_to_range(start, end, f):
while start < end:
print(f(start))
start = start + 1
```
我们可以使用 `map_to_range` 和 `curried_pow` 来计算 2 的前十次幂，而不是专门编写一个函数来实现：
```python
>>> map_to_range(0, 10, curried_pow(2))
1
2
4
8
16
32
64
128
256
512
```
类似地，我们可以使用相同的两个函数来计算其他数字的幂。科里化使我们我们无需为每个要计算幂的数字编写特定函数，就能完成计算。
在上面的例子中，我们手动对 `pow` 函数进行了柯里化变换，得到了 `curried_pow` 。而实际上，我们可以定义一些函数来自动化柯里化，以及逆变换未柯里化：
```python
>>> 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`。
## Lambda Functions lambda函数
在讲python中的$\lambda$函数前，我想先掰扯几句它的历史和一些数学背景。
一切要从上个世纪初，也就是 1900 年左右开始说起了。那时候数学界的气象是这样的：希尔伯特刚刚提出他的23个问题，其中第2个问题问的是公理系统的相容性；1901年提出的，动摇了集合论基础的罗素悖论还是个很流行的话题；至于哥德尔不完备性定理呢，大家都还不知道。所以在这之后的几十年很多数学家和逻辑学家都在致力于给整个数学建立一个一致的公理基础。比如罗素和怀特海德写了 “数学原理（ Principia Mathematica）”；比如约翰·冯·诺伊曼写了关于公理化集合论的博士论文；再比如阿隆佐·邱奇（Alonzo Church）提出了 𝜆 演算 。
邱奇发明λ演算实在二十世纪三十年代左右，其初衷是设计一套形式系统，代替罗素的类型理论和Zermelo的集合理论，来给逻辑学提供一个基础。然鹅这个系统在发表不久之后就被发现有矛盾，当然现在我们早已知道哥德尔不完备性定理威力之大，但是当时的逻辑学家们对这一定理的威力没有清晰而广泛的认知，因此那时邱奇还希望这个定理不会拓展到它的系统上。1935年，邱奇的两个学生Stephen Kleene 和 Barkley Rosser 发现邱奇的逻辑系统是不一致的。
然而他们发现系统中的纯λ演算有一系列良好的性质，后来更是证明用λ演算可以等价定义出可计算函数，这就是著名的“邱奇-图灵论题”的一部分了。更一进步的，邱奇用 𝜆 演算证明了一阶逻辑不存在递归判定过程，这是对希尔伯特提出的判定性问题（Entscheidungs problem）的第一个否定性答案，这比用图灵证明停机问题不可判定还要早几个月。1936年，阿兰·图灵发明了图灵机。图灵把解决判定问题的通用解法是否存在的问题归约到停机问题。而图灵后来证明了λ演算和图灵机是等价的计算模型。
不过二十世纪三十年代在 𝜆 演算方面的成果差不多也就这些了，再接下来的 20 年都没有太多研究和进展。直到六十年代，那时有了计算机，有了程序设计语言，有了计算机科学家。在 1965 年，英国计算机科学家 Peter Landin 发现可以通过把复杂的程序语言转化成简单的 𝜆 演算，来理解程序语言的行为。这个洞见可以让我们把 𝜆 演算本身看成一种程序设计语言。而众所周知的 John McCarthy 的Lisp 语言，更是让 𝜆 演算广为传播。现在不论是各种实际的程序设计语言还是理论上的研究工作，𝜆演算都是一个绕不过去的基本工具了。
我们先从数学开始说起。函数是数学中一个非常基础的概念，当然在python中也是。在数学上，我们可以很轻松的写出一个叫$f$的计算平方和的函数,而有了函数也能方便我们后续的计算
$$
\begin{gather}
f(x, y) = x^2 + y^2 \tag{1}
\end{gather}
$$
$$
\begin{gather}
f(2,3) = 2^2 + 3^2 = 13 \tag*{}
\end{gather}
$$
但是事实上，名字对于一个函数来说也并不是必须的，下面的映射也表示的平方和的函数
$$
\begin{gather}
(x, y) \mapsto x^2 + y^2 \tag{2}
\end{gather}
$$
我们用(2)的整体作为函数的名字也一样能表示计算平方的过程
$$
\begin{gather}
(x, y) \mapsto x^2 + y^2(2,3) = 2^2 + 3^2 = 13 \tag*{}
\end{gather}
$$
我们把 (2) 称为匿名函数，它有两个参数。那么再问，单参数函数和多参数函数的区分有必要吗？
可以换个角度来看，我们把 (2) 改写成下面这个样子：
$$
\begin{gather}
x \mapsto(y \mapsto x^2 + y^2 ) \tag{3}
\end{gather}
$$
这个映射是什么意思呢？我们一步一步来。首先是$x$被映射成了$y \mapsto x^2 + y^2$，后者是一个以y为参数的函数。因此我们可以把(3)理解成：把一个数映射成函数的函数，这就是我们说的高阶函数(HOF).
值得注意的是，现在的(3)是一个单参数函数，我们可以先给它一个参数，比如 $2$，我们便可以得到下面的一个函数：
$$
\begin{gather}
x \mapsto(y \mapsto x^2 + y^2 )(2) = y \mapsto 4 + y^2 \tag*{}
\end{gather}
$$
再给这个函数一个参数，比如$3$，我们便可以得到：
$$
\begin{gather}
y \mapsto 4 + y^2(3) = 4 + 3^2 = 13 \tag*{}
\end{gather}
$$
这样我们就搞清楚了(3)是如何进行平方和运算的。而运用类似的方法，我们可以把任意多个参数的函数转换为单参数的高阶函数，这就是我们上一节讲到的柯里化(Currying)。
匿名函数和柯里化λ运算为简化函数概念采取的方法，上面这段说明可以看作是lambda运算的非正式介绍。事实上，大多数编程语言里的所谓Lambda表达式也就是把这两个概念组合在一起罢了，Python也不例外。而如果你想要更深入的了解λ演算，下面放了一些一些推荐的博客与书。[^2]
咳咳咳，嗯。让我们回归正题，现在来看看python中的Lambda表达式。到目前为止，每当我们想要定义一个新函数时，我们都需要给它一个名字。但对于其他类型的表达式，我们不需要将中间值与名称关联起来。也就是说，我们可以计算 a*b + c*d 而不必给子表达式 a*b 或 c*d 或完整表达式命名。在 Python 中，我们可以使用 lambda 表达式临时创建函数值，它们会评估为匿名函数。λ表达式会评估为只有一个返回表达式作为其函数体的函数。不允许赋值和控制语句。比如下面一个例子
```python
>>> 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))|
λ表达式的结果称为λ函数。它没有固有名称（因此 Python 打印`
```python
>>> s = lambda x: x * x
>>> s
>>> s(12)
144
```
虽然说匿名的lambda表达式更短，更直接。但是就像一把双刃剑一样，如果不当的使用lambda表达式会让你对程序变得难以阅读~~这或许提高了你的不可替代性，但是过了一段时间再去看这段代码可能你也不知道你写了什么xd~~。 以下定义是正确的，但许多程序员很难快速理解。
```python
>>> compose1 = lambda f,g: lambda x: f(g(x))
```
一般来说，Python风格的代码(pythonic code)更喜欢使用显式def语句而不是lambda表达式，但允许在需要简单函数作为参数或返回值的情况下使用它们。
## *Abstraction and First-Class Functions 抽象机制与一等公民*
可以看看这篇文章[^3]。
## *Function Decorators 函数装饰器*
摆了，可以去看看文档、问GPT
[^1]:[SICP](https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-12.html)
[^2]: About Lambda Calculus 1. [让我们谈谈Lambda演算](https://github.com/txyyss/Lambda-Calculus/tree/master)
[不知道什么时候的博客了](https://cgnail.github.io/tags/#lambda%E6%BC%94%E7%AE%97)
[同样也是不知道什么时候的博客](https://liujiacai.net/blog/2014/10/12/lambda-calculus-introduction/#%CE%BB%E6%BC%94%E7%AE%97%E7%9A%84%E8%AF%AD%E6%B3%95%E4%B8%8E%E6%B1%82%E5%80%BC)
[A Tutorial Introduction to the Lambda Calculus](https://arxiv.org/pdf/1503.09060)
[The Lambda Calculus for Absolute Dummies](https://palmstroem.blogspot.com/2012/05/lambda-calculus-for-absolute-dummies.html)
如果你对计算理论感兴趣，可以去看看CS154的课程[Introduction to the Theory of Computing](https://www.youtube.com/channel/UCrz06enpAptXhu4pYJfR-EQ/videos)
[^3]:[一等公民的函数](https://llh911001.gitbooks.io/mostly-adequate-guide-chinese/content/ch2.html)
点赞
回复
X