Homework 2: Higher Order Functions
Due by 11:59pm on Thursday, 9/6
Instructions
Download hw02.zip. Inside the archive, you will find a file called
hw02.py, along with a copy of the ok
autograder.
Submission: When you are done, submit with python3 ok
--submit
. You may submit more than once before the deadline; only the
final submission will be scored. Check that you have successfully submitted
your code on okpy.org. See Lab 0 for more instructions on
submitting assignments.
Using Ok: If you have any questions about using Ok, please refer to this guide.
Readings: You might find the following references useful:
Grading: Homework is graded based on effort, not correctness. However, there is no partial credit; you must show substantial effort on every problem to receive any points.
The construct_check
module is used in this assignment, which defines a
function check
. For example, a call such as
check("foo.py", "func1", ["While", "For", "Recursion"])
checks that the function func1
in file foo.py
does not contain
any while
or for
constructs, and is not an overtly recursive function (i.e.,
one in which a function contains a call to itself by name.)
Required questions
Several doctests refer to these functions:
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
Q1: Make Adder with a Lambda
Implement the make_adder
function, which takes in a number n
and returns a
function that takes in an another number k
and returns n + k
. Your
solution must consist of a single return
statement.
def make_adder(n):
"""Return a function that takes an argument K and returns N + K.
>>> add_three = make_adder(3)
>>> add_three(1) + add_three(2)
9
>>> make_adder(1)(2)
3
"""
return 'YOUR EXPRESSION HERE'
Use Ok to test your code:
python3 ok -q make_adder
Q2: Product
The summation(n, term)
function from the higher-order functions lecture adds
up term(1) + ... + term(n)
. Write a similar function called product
that
returns term(1) * ... * term(n)
. Do not use recursion.
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
>>> 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
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'product', ['Recursion'])
True
"""
"*** YOUR CODE HERE ***"
Now, define the factorial function in
terms of product
in one line.
def factorial(n):
"""Return n factorial for n >= 0 by calling product.
>>> factorial(4) # 4 * 3 * 2 * 1
24
>>> factorial(6) # 6 * 5 * 4 * 3 * 2 * 1
720
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'factorial', ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q product
python3 ok -q factorial
Q3: Accumulate
Let's take a look at how summation
and product
are instances of a more
general function called 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, associative 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
"""
"*** YOUR CODE HERE ***"
accumulate
has the following parameters:
term
andn
: the same parameters as insummation
andproduct
combiner
: a two-argument function that specifies how the current term is combined with the previously accumulated terms.base
: value at which to start the accumulation.
For example, the result of accumulate(add, 11, 3, square)
is
11 + square(1) + square(2) + square(3) = 25
You may assume that combiner
is associative and commutative.
After implementing accumulate
, show how summation
and product
can both be
defined as simple calls to accumulate
:
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
>>> check(HW_SOURCE_FILE, 'summation_using_accumulate',
... ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
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
>>> check(HW_SOURCE_FILE, 'product_using_accumulate',
... ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q accumulate
python3 ok -q summation_using_accumulate
python3 ok -q product_using_accumulate
Extra questions
Extra questions are not worth extra credit and are entirely optional. They are designed to challenge you to think creatively! Feel free to skip them.
Q4: Make Repeater
Implement a function make_repeater
so that make_repeater(f, n)(x)
returns
f(f(...f(x)...))
, where f
is applied n
times. That is,
make_repeater(f, n)
returns another function that can then be applied to
another argument. For example, make_repeater(square, 3)(42)
evaluates to
square(square(square(42)))
. Yes, it makes sense to apply the function zero
times! See if you can figure out a reasonable function to return for that
case. You may use either loops or recursion in your implementation.
def make_repeater(f, n):
"""Return the function that computes the nth application of f.
>>> 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)
5
"""
"*** YOUR CODE HERE ***"
For an extra challenge, try defining
make_repeater
usingcompose1
and youraccumulate
function in a single one-line return statement.
def compose1(f, g):
"""Return a function h, such that h(x) = f(g(x))."""
def h(x):
return f(g(x))
return h
Use Ok to test your code:
python3 ok -q make_repeater
Q5: Church numerals
The logician Alonzo Church invented a system of representing non-negative integers entirely using functions. The purpose was to show that functions are sufficient to describe all of number theory: if we have functions, we do not need to assume that numbers exist, but instead we can invent them.
Your goal in this problem is to rediscover this representation known as Church
numerals. Here are the definitions of zero
, as well as a function that
returns one more than its argument:
def zero(f):
return lambda x: x
def successor(n):
return lambda f: lambda x: f(n(f)(x))
First, define functions one
and two
such that they have the same behavior
as successor(zero)
and successsor(successor(zero))
respectively, but do
not call successor
in your implementation.
Next, implement a function church_to_int
that converts a church numeral
argument to a regular Python integer.
Finally, implement functions add_church
, mul_church
, and pow_church
that
perform addition, multiplication, and exponentiation on church numerals.
def one(f):
"""Church numeral 1: same as successor(zero)"""
"*** YOUR CODE HERE ***"
def two(f):
"""Church numeral 2: same as successor(successor(zero))"""
"*** YOUR CODE HERE ***"
three = successor(two)
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
"""
"*** YOUR CODE HERE ***"
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 ***"
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 ***"
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 ***"
Use Ok to test your code:
python3 ok -q church_to_int
python3 ok -q add_church
python3 ok -q mul_church
python3 ok -q pow_church