Homework 2: Higher-Order Functions
Q1: Product
from operator import add, mul, sub
square = lambda x: x * x
identity = lambda x: x
triple = lambda x: 3 * x
increment = lambda x: x + 1
HW_SOURCE_FILE=__file__
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
"""
"*** YOUR CODE HERE ***"
total, k = 1, 1
while k <= n:
total, k = total * term(k), k + 1
return totalQ2: Accumulate
def accumulate(combiner, base, n, term):
"""Return the result of combining the first n terms in a sequence and base.
The terms to be combined are term(1), term(2), ..., term(n). combiner 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
>>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
19
>>> accumulate(lambda x, y: 2 * (x + y), 2, 3, square)
58
>>> accumulate(lambda x, y: (x + y) % 17, 19, 20, square)
16
"""
"*** YOUR CODE HERE ***"
total, k = base, 1
while k <= n:
total, k = combiner(total, term(k)), k + 1
return total
def summation_using_accumulate(n, term):
"""Returns the sum of term(1) + ... + term(n). The implementation
uses accumulate.
>>> summation_using_accumulate(5, square)
55
>>> summation_using_accumulate(5, triple)
45
>>> from construct_check import check
>>> # ban iteration and recursion
>>> check(HW_SOURCE_FILE, 'summation_using_accumulate',
... ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
return accumulate(add, 0, n, term)
def product_using_accumulate(n, term):
"""An implementation of product using accumulate.
>>> product_using_accumulate(4, square)
576
>>> product_using_accumulate(6, triple)
524880
>>> from construct_check import check
>>> # ban iteration and recursion
>>> check(HW_SOURCE_FILE, 'product_using_accumulate',
... ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
return accumulate(mul, 1, n, term)Q3: Make Repeater
def compose1(func1, func2):
"""Return a function f, such that f(x) = func1(func2(x))."""
def f(x):
return func1(func2(x))
return f
def make_repeater(func, n):
"""Return the function that computes the nth application of func.
>>> add_three = make_repeater(increment, 3)
>>> add_three(5)
8
>>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 4)(5) # square(square(square(square(5))))
152587890625
>>> make_repeater(square, 0)(5) # Yes, it makes sense to apply the function zero times!
5
"""
"*** YOUR CODE HERE ***"
return accumulate(compose1, identity, n, lambda x: func)Q4: Church numerals
def zero(f):
return lambda x: x
def successor(n):
return lambda f: lambda x: f(n(f)(x))
def one(f):
"""Church numeral 1: same as successor(zero)"""
"*** YOUR CODE HERE ***"
def a(x):
return f(x)
return a
# Solution 2
# return lambda x: x
def two(f):
"""Church numeral 2: same as successor(successor(zero))"""
"*** YOUR CODE HERE ***"
def b(x):
return f(f(x))
return b
# Solution 2
# return lambda x: f(x)
three = successor(two)The original code：
def successor(n):
return lambda f: lambda x: f(n(f)(x))The function successor is returning an anonymous function using lambda. That is hard to read, so lets replace it with a named function.
def successor(n):
def inner_function_one(f):
def inner_function_two(x):
return f(n(f)(x))
return inner_function_two
return inner_function_oneSo now we've broken apart the function, and we can see that successor returns a function that in turn returns another function, which returns... that. The line f(n(f)(x)) is pretty hard to read. It is saying that a function f is being called with the argument n(f)(x), which is a way of saying that n(f) returns a function that is then being passed the argument x. Lets use some more descriptive variable names to see what is happening here.
def successor(first_function):
def inner_function_one(second_function):
def inner_function_two(arg):
return second_function(first_function(second_function)(arg))
# Equivalent to something like
# return second_function(returned_function(arg))
# where returned_function is the result of
# first_function(second_function)
return inner_function_two
return inner_function_onedef church_to_int(n):
"""Convert the Church numeral n to a Python integer.
>>> church_to_int(zero)
0
>>> church_to_int(one)
1
>>> church_to_int(two)
2
>>> church_to_int(three)
3
"""
"*** YOUR CODE HERE ***"
def add1(x):
return x+1
return n(add1)(0)
# Solution 2
# return n(lambda x: x + 1)(0)def add_church(m, n):
"""Return the Church numeral for m + n, for Church numerals m and n.
>>> church_to_int(add_church(two, three))
5
"""
"*** YOUR CODE HERE ***"
int_n = church_to_int(n)
for i in range(int_n):
m = successor(m)
return m
# Solution 2
# return lambda f: lambda x: m(f)(n(f)(x))Recall that Church encoding can be understood as repeated application of a function to an argument. So to add m + n, we need to apply a function f to an argument x m + n times, or equivalently apply it n times and then apply it m times:
def add_church(m, n):
def m_plus_n(f):
def f_repeated_m_plus_n_times(x) # f ** (m + n)
intermediate_result = (n(f))(x) # (f ** n) (x)
final_result = (m(f))(intermediate_result) # (f ** m) ((f ** n) (x))
return final_result
return f_repeated_m_plus_n_times
return m_plus_nIn lambda form, removing redundant parentheses:
def add_church(m, n):
"""Return the Church numeral for m + n, for Church numerals m and n.
>>> three = successor(two)
>>> church_to_int(add_church(two, three))
5
"""
lambda f: lambda x: m(f)(n(f)(x))def mul_church(m, n):
"""Return the Church numeral for m * n, for Church numerals m and n.
>>> four = successor(three)
>>> church_to_int(mul_church(two, three))
6
>>> church_to_int(mul_church(three, four))
12
"""
"*** YOUR CODE HERE ***"
# ans = zero
# int_n = church_to_int(n)
# for i in range(int_n):
# ans = add_church(ans, m)
# return ans
return lambda x: m(n(x))def pow_church(m, n):
"""Return the Church numeral m ** n, for Church numerals m and n.
>>> church_to_int(pow_church(two, three))
8
>>> church_to_int(pow_church(three, two))
9
"""
"*** YOUR CODE HERE ***"
ans = one
int_n = church_to_int(n)
for i in range(int_n):
ans = mul_church(ans, m)
return ans