Higher-Order Functions

函数特征

一个函数的定义域(domain)即为所有可能的输入
一个函数的值域(range)即为所有可能的输出
一个纯函数表现即为建立输入与输出之间的映射

assert语句

格式：assert <bool expression> <output information>

用处：当布尔表达式成立时，语句继续执行；当布尔表达式不成立时，程序跳出并提示指定的报错信息。

函数作为形参

设计一个计算求和、立方项求和的函数，我们可以通过在对求和函数中传入对每一位数的操作对应的函数来简化代码，而非为不同种类求和分别设计函数，如下：

from math import pow
def identity(k):
    return k

def cube(k):
    return int(pow(k,3))

def summation(n,term):
    """sum the first N terms of a sequence.
    >>> summation(5,cube)
    225
    """
    total,k=0,1
    while k<=n:
        total,k = total + term(k), k+1
    return total

def sum_naturals(n):
    """sum the first N natural numbers
    >>> sum_naturals(5)
    15
    """
    return summation(n,identity) # 传入返回原值函数进行计算
def sum_cubes(n):
    """sum the first N cubes of natural numbers
    >>> sum_cubes(5)
    225
    """
    return summation(n,cube) # 传入返回每个值的立方函数进行计算

其中，summation函数中的term参数与传入的函数有关

identity与cube函数作为单个参数传入summation函数，以处理不同情况下的求和

形参term函数在计算total时被回调，回调的是传入的对应函数

函数作为返回值

当一个函数在另一个函数体内定义，该函数的名称绑定在本地作用域中

如下：

def make_adder(n):
    """return a function that takes one argument called k and return k+N
    >>> add_three = make_adder(3)
    >>> add_three(4)
    7
    """
    def adder(k):
        return k+n # adder函数返回数值k+n
    return adder # make_adder函数返回adder函数

make_adder函数返回一个函数adder，而函数adder是局部定义的函数，它可以使用make_adder内部的变量（k与n）

对于语句make_adder(1)(2)，实现的效果即为1+2

作用

函数是第一类值(first-class)：函数可以作为参数传递，作为返回值返回
higher-order函数指代以函数作为参数或返回值的函数
1. 它可以表示计算的一般情况
2. 它可以防止程序代码过于重复冗杂
3. 它可以将不同功能分离成多个函数

匿名函数(Lambda Expressions )

格式：lambda <formal parameter>: <return value>

lambda指定义一个匿名函数

lambda后紧跟一个形式参数，冒号后为返回值（无return关键字）

返回值只能是一句表达式

使用时将其赋值给一个变量并按照def函数方式调用或直接按照def函数方式调用

与def不同的一点是：def定义的函数拥有一个内部名称(intrinsic name)，而lambda定义的函数即使赋值给了另一个名字的变量，它的名称仍为lambda

返回语句(Return Statements)

函数中的return语句让程序返回到先前的environment，并给函数一个值

在执行函数体时，遇到return语句函数即结束

看如下例子：

def search(f):
    """find a number that one more than the square root of
    the number put in the positive function
    >>> search(positive)
    11
    """
    x=0
    while not f(x): # 当positive函数返回为0时进入循环
        x+=1
    return x

def square(x):
    return x**2
def positive(x):
    return max(0,square(x)-100)
def inverse(f):
    """return g(y) such that g(f(x)) ->x
    >>> inverse(square)(16)
    4
    """
    return lambda y: search(lambda x:f(x)==y) # 返回某个完全平方数的平方根

positive函数：

传入search后，寻找的是第一个比positive函数中减数的平方根大的数

因为若数x的平方比减数小，return值肯定是0，while条件成立，x++继续寻找

inverse函数：

inverse用于寻找完全平方数y的平方根

传入square函数用于计算search函数中x的平方，与inverse函数返回的lambda函数中传入的y比较是否相等，若不相等，满足while循环条件，x++继续比较，若相等则找到，跳出循环返回此时x值。

控制语句(Control Statements)

条件语句

执行条件：每一句clause按序执行

判断条件判断语句是否成立（若存在）
若值为true或遇到else的clause，执行语句块并跳过其余clauses

但为何没有一个函数能实现条件判断呢？

对于调用表达式(call expression)的执行如下：

而在if语句中，只有其中一句会被执行，因此使用函数替代并不合适，如下代码：

def if_(c,t,f):
    if c:
        return t
    else:
        return f

from math import sqrt

def real_sqrt(x):
    return if_(x>0,sqrt(x),0.0)

if __name__ == '__main__':
    print(real_sqrt(-4))

我们需要实现返回一个实数平方根结果的实部，众所周知，负数开平方后实部为0，因此负数应输出0

但执行后发现却出现了sqrt的 ValueError: math domain error

因为在函数调用时，sqrt(x)同时也会执行，此时x小于0故触发了sqrt的assert

因此没有了控制语句，我们只能在值之间选择而不能在条件之间选择

条件语句的简单形式

<consequent> if <predicate> else <alternative>

执行predicate语句
若为真，则整个表达式的值为consequent的值
若为假，则整个表达式的值为alternative的值

逻辑运算符的短路效应

执行一个语句<left> and <right>

计算left语句
若结果是false，则整个表达式的结果是false
若结果是true，则整个表达式的结果是right语句的结果

执行一个语句<left> or <right>

计算left语句
若结果为true，则整个表达式的结果是true
若结果为false，则整个表达式的结果是right语句的结果

HW

Lecture4的作业部分

柯里化(Currying)

定义：柯里化（Currying）是一种处理多元函数的方法。它产生一系列连锁函数，其中每个函数固定部分参数，并返回一个新函数，用于传回其它剩余参数的功能。

即它可以把一个多元函数转换为一系列函数，每个函数传入一个参数，即将f(a,b,c)转换为f(a)(b)(c)

如上文中的makeadder函数，返回的是在内部定义的adder函数，每个函数接受一个参数，等同于makeadder(k,n)

柯里化是函数式编程的一个体现，使得函数代码更简洁

1-Product

My solution:

x = 1
re = 1
while x<=n:
    re*=term(x)
    x+=1
return re

product函数有一个term参数用于接收函数，根据不同计算需要可以传入不同计算相关函数(square，identity等)

2- Accumulate

My solution:

a=1
   re=start
   while a<=n:
       re = fuse(re,term(a))
       a+=1
   return re

return accumulate(add, 0, n, term)

return accumulate(mul, 1, n, term)

在上一题的基础上添加了选择每个数之间使用加法还是乘法的参数fuse，fuse同时也是接收函数来指定每个term运算之间的运算方式(add,mul 等)

3-Make repeater

My solution:

if n == 0: return lambda x: x
return lambda x: f(make_repeater(f,n-1)(x))

这里需要将传入的数值执行n次指定运算f，即f(f(...f(x)...))

本人使用了递归实现，即make_repeater(f,n)(x)=f(make_repeater(f,n-1)(x))=f(f(make_repeater(f,n-2)))=...=f(f(...f(x)...))

每次加一层f()，直到\(n=0\)时替换为x

红魔咖啡馆

【CS61A】CS61A——Higher-Order Functions

Higher-Order Functions

函数特征

assert语句

函数作为形参

函数作为返回值

作用

匿名函数(Lambda Expressions )

返回语句(Return Statements)

控制语句(Control Statements)

条件语句

条件语句的简单形式

逻辑运算符的短路效应

HW

柯里化(Currying)

1-Product

2- Accumulate

3-Make repeater