# 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
"""
total, k = 1, 1
while k <= n:
total, k = total * term(k), k + 1
return total

## Q2: 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
"""
total, k = base, 1
while k <= n:
total, k = combiner(total, term(k)), k + 1

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
"""

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
"""
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.

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
"""
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)"""
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))"""
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_one

So 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_one

def 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
"""
return x+1
# 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.

5
"""
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_n

In 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)
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
"""
# ans = zero
# int_n = church_to_int(n)
# for i in range(int_n):
# 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
"""
return ans