过程抽象—控制语句和高级函数(二)
高阶函数
为了将某些通用模式进行命名抽象,我们将需要构造一些函数,这些函数可以接受其他函数作为参数,也可以返回函数作为值。
操作函数的函数成为高阶函数。高阶函数为一种非常强大的抽象机制,极大简化并提高我们编程语言的表达能力。
作为高阶函数输入
# 高阶函数 # 计算过程泛化 # 求解一个数列,前k项的值。 from math import pow from operator import mul def sum_number(n,shape): # shape: a formal parameter that will be bound to a function. total, k = 0,1 while k <=n: total, k = total + shape(k), k+1 return total def identity(k): return k def square(k): return k*k def cube(k): return pow(k,3) def pi_term(k): return 8/mul(4*k-3,4*k-1) def sum_naturals(n): return sum_number(n,identity) def sum_cubes(n): # the cube function is passed as an argument value. return sum_number(n,cube) sum_cubes(5) sum_number(10000,pi_term)
函数作为一般方法
我们引入了用户自定义的函数,作为一种抽象数字运算模式的机制,以使他们独立于所涉及的特定数字。
使用高阶函数,看到一种更加强大的抽象:一些函数表示通过的计算方法,而与他们调用的特定函数无关。
函数调用环境
示例:计算黄金分割点的代码
def improve(update,close,guess=1): while not close(guess): guess = update(guess) return guess def golden_update(guess): return 1/guess +1 def square_close_to_successor(guess): return approx_eq(guess*guess, guess+1) def approx_eq(x,y,tolerance=1e-15): return abs(x-y)<tolerance improve(golden_update,square_close_to_successor)
嵌套函数
上示例说明了将函数作为参数传递的能力如何显着增强了我们编程语言的表达能力。每个一般概念或方程式都映射到其自己的短函数。这种方法的一个负面结果是,全局帧变得杂乱无章,而所有小功能的名称都必须是唯一的。另一个问题是我们受到特定函数签名的约束:
要改进的update参数必须恰好采用一个参数。嵌套函数定义解决了这两个问题,但要求我们丰富环境模型。
以下示例为求根公式,具体代码如下:
def average(x, y): return (x + y)/2 def sqrt_update(x, a): return average(x, a/x) # 嵌套函数 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 approx_eq(x, y, tolerance=1e-5): return abs(x - y) < tolerance def improve(update, close, guess=1): while not close(guess): guess = update(guess) return guess sqrt(8)
组合函数
定义h(x)= f(g(x))
def compose1(f, g): def h(x): return f(g(x)) return h
牛顿切线法,如图所示
牛顿切线法求根公式
def newton_update(f, df): def update(x): return x - f(x) / df(x) return update def find_zero(f, df): def near_zero(x): return approx_eq(f(x), 0) return improve(newton_update(f, df), near_zero) def approx_eq(x, y, tolerance=1e-5): return abs(x - y) < tolerance def improve(update, close, guess=1): while not close(guess): guess = update(guess) return guess 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(8)
函数环境如下:
定义多参数函数
f(x,y) = g(x)(y),输出2的0次幂到10次幂
def curried_pow(x): def h(y): return pow(x, y) return h def map_to_range(start,end,f): while start < end: print(f(start)) start += 1 map_to_range(0,10,curried_pow(2))
函数运行环境如下:
其他多参数函数
def curried_pow(x): def h(y): return pow(x, y) return h def uncurry2(g): """Return a two-argument version of the given curried function.""" def f(x,y): return g(x)(y) return f uncurry2(curried_pow)(2, 5)
lambda表达式
在Python中,我们可以使用lambda表达式动态创建函数值,该表达式的值将为未命名函数。Lambda表达式的计算结果为具有单个return表达式作为其主体的函数。不允许分配和控制语句。
def composel(f,g): return lambda x: f(g(x)) s = lambda x: x*x s
多个lambda函数示例如下所示
抽象与第一类函数
我们从本节开始观察到,用户定义函数是至关重要的抽象机制,因为它们允许我们将通用计算方法表达为编程语言中的显式元素。现在我们已经看到了高阶函数如何允许我们操纵这些通用方法来创建进一步的抽象。
作为程序员,我们应该识别程序中的基础抽象,在其基础上进行构建,并将其泛化以创建更强大的抽象。这并不是说人们应该总是以最抽象的方式编写程序。专业的程序员知道如何选择适合其任务的抽象级别。但是重要的是要能够根据这些抽象思想进行思考,以便我们可以随时将它们应用到新的上下文中。高阶函数的重要性在于它们使我们能够将这些抽象形式明确表示为编程语言中的元素,以便可以像处理其他计算元素一样处理它们。
通常,编程语言对可操纵计算元素的方式施加了限制。限制最少的元素据说具有第一类的地位。
第一类元素的一些“权利和特权”是
它们可能与名称绑定。
它们可以作为参数传递给函数。
它们可能作为函数的结果返回。
它们可能包含在数据结构中
python 赋予函数完全具有第一类的地位,因此,表达能力的提高是巨大的。
函数修饰符
python提供特殊语法来应用高阶函数,这是执行def语句(称为装饰器)的一部分。
也许最常见的例子是记录函数。
递归函数
如果函数的体直接或间接调用函数本身,则该函数称为递归。也就是说,执行递归函数体的过程可能又需要再次应用该函数。递归函数在Python中不使用任何特殊语法,但确实需要一些努力才能理解和创建。以下例子为计算所有数字的和。
# 递归函数实现是否正确? # 1. 基础例是否正确 # 2. 把递归函数当做一个抽象函数 # 3. 假设函数在f(n-1)正确 # 4. 验证f(n)正确 def split(n): return n//10, n%10 def sum_digits(n): if n<10: return n; else: all_but_last, last = split(n) return sum_digits(all_but_last) + last sum_digits(100)
例子:求解整数a,小于数给定数b的和分解
def count_partitions(n,m): """Count the ways to partition n using parts up to a""" if n ==0: return 1 elif n<0: return 0 elif m==0: return 0 else: return count_partitions(n-m,m) + count_partitions(n,m-1) count_partitions(6,4)