[CS61A] Lecture 5&6&7. Environments & Design & Functions Examples & Homework 2: Higher Order Functions
Lecture
Lecture 5. Environments
环境是编程语言中的一大命题，每个变量、函数都拥有它们所属的环境，也被称为作用域。
作用域在高阶函数中起到重要的作用，高阶函数中的变量因为作用域起到了状态的表示作用，使得多次调用特定的函数能够返回不同的结果。
Lecture 6. Design
函数抽象是编程语言很重要的一部分；
函数应该拥有一个有意义的名称，虽然对功能没有任何影响，但当程序复杂度上升时，好的函数名是函数功能最好的注释；
一个用函数组成的音乐制作器，比较神奇。
Lecture 7. Functions Examples
介绍了几个函数的例子，用来温习之前的知识点，最后介绍了装饰器的概念与用法。
Homework
Homework 2: Higher Order Functions
Q1: Product
要求实现product函数，返回term(1) * ... * term(n)。
product函数：
def product(n, term):
"""Return the product of the first n terms in a sequence.
n: a positive integer
term: a function that takes one argument to produce the term
>>> product(3, identity) # 1 * 2 * 3
6
>>> product(5, identity) # 1 * 2 * 3 * 4 * 5
120
>>> product(3, square) # 1^2 * 2^2 * 3^2
36
>>> product(5, square) # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
14400
>>> product(3, increment) # (1+1) * (2+1) * (3+1)
24
>>> product(3, triple) # 1*3 * 2*3 * 3*3
162
"""
return reduce(mul, [term(i) for i in range(1, n+1)])
Q2: Accumulate
要求实现accumulate函数。
accumulate函数：
def accumulate(merger, start, n, term):
"""Return the result of merging the first n terms in a sequence and start.
The terms to be merged are term(1), term(2), ..., term(n). merger is a
two-argument commutative function.
>>> accumulate(add, 0, 5, identity) # 0 + 1 + 2 + 3 + 4 + 5
15
>>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
26
>>> accumulate(add, 11, 0, identity) # 11
11
>>> accumulate(add, 11, 3, square) # 11 + 1^2 + 2^2 + 3^2
25
>>> accumulate(mul, 2, 3, square) # 2 * 1^2 * 2^2 * 3^2
72
>>> # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1)
>>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
19
>>> # ((2 * 1^2 * 2) * 2^2 * 2) * 3^2 * 2
>>> accumulate(lambda x, y: 2 * x * y, 2, 3, square)
576
>>> accumulate(lambda x, y: (x + y) % 17, 19, 20, square)
16
"""
return reduce(merger, list(map(term, list(range(1, n+1))))+[start])
summation_using_accumulate函数：
def summation_using_accumulate(n, term):
"""Returns the sum: term(0) + ... + term(n), using accumulate.
>>> summation_using_accumulate(5, square)
55
>>> summation_using_accumulate(5, triple)
45
>>> # You aren't expected to understand the code of this test.
>>> # Check that the bodies of the functions are just return statements.
>>> # If this errors, make sure you have removed the "***YOUR CODE HERE***".
>>> import inspect, ast
>>> [type(x).__name__ for x in ast.parse(inspect.getsource(summation_using_accumulate)).body[0].body]
['Expr', 'Return']
"""
return accumulate(add, 0, n, term)+term(0)
product_using_accumulate函数：
def product_using_accumulate(n, term):
"""Returns the product: term(1) * ... * term(n), using accumulate.
>>> product_using_accumulate(4, square)
576
>>> product_using_accumulate(6, triple)
524880
>>> # You aren't expected to understand the code of this test.
>>> # Check that the bodies of the functions are just return statements.
>>> # If this errors, make sure you have removed the "***YOUR CODE HERE***".
>>> import inspect, ast
>>> [type(x).__name__ for x in ast.parse(inspect.getsource(product_using_accumulate)).body[0].body]
['Expr', 'Return']
"""
return accumulate(mul, 1, n, term)
Q3: Filtered Accumulate
要求实现filtered_accumulate函数，添加过滤的功能：
def filtered_accumulate(merger, start, cond, n, term):
"""Return the result of merging the terms in a sequence of N terms
that satisfy the condition cond. merger is a two-argument function.
If v1, v2, ..., vk are the values in term(1), term(2), ..., term(N)
that satisfy cond, then the result is
start merger v1 merger v2 ... merger vk
(treating merger as if it were a binary operator, like +). The
implementation uses accumulate.
>>> filtered_accumulate(add, 0, lambda x: True, 5, identity) # 0 + 1 + 2 + 3 + 4 + 5
15
>>> filtered_accumulate(add, 11, lambda x: False, 5, identity) # 11
11
>>> filtered_accumulate(add, 0, odd, 5, identity) # 0 + 1 + 3 + 5
9
>>> filtered_accumulate(mul, 1, greater_than_5, 5, square) # 1 * 9 * 16 * 25
3600
>>> # Do not use while/for loops or recursion
>>> from construct_check import check
>>> # ban iteration and recursion
>>> check(HW_SOURCE_FILE, 'filtered_accumulate', ['While', 'For', 'Recursion'])
True
"""
def merge_if(x, y):
return merger(x, y) if cond(y) else x
return accumulate(merge_if, start, n, term)
Q4: Funception
要求实现funception函数：
def funception(func_a, start):
""" Takes in a function (function A) and a start value.
Returns a function (function B) that will find the product of
function A applied to the range of numbers from
start (inclusive) to stop (exclusive)
>>> def func_a(num):
... return num + 1
>>> func_b1 = funception(func_a, 0)
>>> func_b1(3) # func_a(0) * func_a(1) * func_a(2) = 1 * 2 * 3 = 6
6
>>> func_b2 = funception(func_a, 1)
>>> func_b2(4) # func_a(1) * func_a(2) * func_a(3) = 2 * 3 * 4 = 24
24
>>> func_b3 = funception(func_a, 3)
>>> func_b3(2) # Returns func_a(3) since start > stop
4
>>> func_b4 = funception(func_a, -2)
>>> func_b4(-3) # Returns None since start < 0
>>> func_b5 = funception(func_a, -1)
>>> func_b5(4) # Returns None since start < 0
"""
def func_b(end):
return reduce(mul, map(func_a, range(start+1, end)), func_a(start)) if start >=0 else None
return func_b
参考资料
Homework 2: Higher Order Functions：https://cs61a.org/hw/hw02/
