Homework 2: Higher Order Functions and Recursion
Due by 11:59pm on Wednesday, July 7
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 correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 3 points.
The construct_check
module is used in this assignment, which defines the
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.) This restriction does not apply to all problems in this assignment. If this restriction applies, you will see a call to check
somewhere in the problem's doctests.
Required questions
Important Functions
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
Higher Order Functions
Q1: Make Repeater
Implement the function make_repeater
so that make_repeater(func, n)(x)
returns
func(func(...func(x)...))
, where func
is applied n
times. That is,
make_repeater(func, 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)))
.
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 ***"
For an extra challenge, try defining
make_repeater
usingcompose1
and youraccumulate
function in a single one-line return statement.
def compose1(func1, func2):
"""Return a function f, such that f(x) = func1(func2(x))."""
def f(x):
return func1(func2(x))
return f
Watch the hints video below for somewhere to start:
Use Ok to test your code:
python3 ok -q make_repeater
Recursion
Q2: Num eights
Write a recursive function num_eights
that takes a positive integer pos
and
returns the number of times the digit 8 appears in pos
.
Use recursion - the tests will fail if you use any assignment statements.
def num_eights(pos):
"""Returns the number of times 8 appears as a digit of pos.
>>> num_eights(3)
0
>>> num_eights(8)
1
>>> num_eights(88888888)
8
>>> num_eights(2638)
1
>>> num_eights(86380)
2
>>> num_eights(12345)
0
>>> from construct_check import check
>>> # ban all assignment statements
>>> check(HW_SOURCE_FILE, 'num_eights',
... ['Assign', 'AugAssign'])
True
"""
"*** YOUR CODE HERE ***"
Watch the hints video below for somewhere to start:
Use Ok to test your code:
python3 ok -q num_eights
Q3: Ping-pong
The ping-pong sequence counts up starting from 1 and is always either counting
up or counting down. At element k
, the direction switches if k
is a
multiple of 8 or contains the digit 8. The first 30 elements of the ping-pong
sequence are listed below, with direction swaps marked using brackets at the
8th, 16th, 18th, 24th, and 28th elements:
Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | [8] | 9 | 10 | 11 | 12 | 13 | 14 | 15 | [16] | 17 | [18] | 19 | 20 | 21 | 22 | 23 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
PingPong Value | 1 | 2 | 3 | 4 | 5 | 6 | 7 | [8] | 7 | 6 | 5 | 4 | 3 | 2 | 1 | [0] | 1 | [2] | 1 | 0 | -1 | -2 | -3 |
Index (cont.) | [24] | 25 | 26 | 27 | [28] | 29 | 30 |
---|---|---|---|---|---|---|---|
PingPong Value | [-4] | -3 | -2 | -1 | [0] | -1 | -2 |
Implement a function pingpong
that returns the nth element of the ping-pong
sequence without using any assignment statements.
You may use the function num_eights
, which you defined in the previous question.
Use recursion - the tests will fail if you use any assignment statements.
Hint: If you're stuck, first try implementing
pingpong
using assignment statements and awhile
statement. Then, to convert this into a recursive solution, write a helper function that has a parameter for each variable that changes values in the body of the while loop.
def pingpong(n):
"""Return the nth element of the ping-pong sequence.
>>> pingpong(8)
8
>>> pingpong(10)
6
>>> pingpong(15)
1
>>> pingpong(21)
-1
>>> pingpong(22)
-2
>>> pingpong(30)
-2
>>> pingpong(68)
0
>>> pingpong(69)
-1
>>> pingpong(80)
0
>>> pingpong(81)
1
>>> pingpong(82)
0
>>> pingpong(100)
-6
>>> from construct_check import check
>>> # ban assignment statements
>>> check(HW_SOURCE_FILE, 'pingpong', ['Assign', 'AugAssign'])
True
"""
"*** YOUR CODE HERE ***"
Watch the hints video below for somewhere to start:
Use Ok to test your code:
python3 ok -q pingpong
Q4: Missing Digits
Write the recursive function missing_digits
that takes a number n
that is sorted in increasing order (for example, 12289
is valid but 15362
and 98764
are not). It returns the number of missing digits in n
. A missing digit is a number between the first and last digit of n
of a that is not in n
.
Use recursion - the tests will fail if you use while or for loops.
def missing_digits(n):
"""Given a number a that is in sorted, increasing order,
return the number of missing digits in n. A missing digit is
a number between the first and last digit of a that is not in n.
>>> missing_digits(1248) # 3, 5, 6, 7
4
>>> missing_digits(19) # 2, 3, 4, 5, 6, 7, 8
7
>>> missing_digits(1122) # No missing numbers
0
>>> missing_digits(123456) # No missing numbers
0
>>> missing_digits(3558) # 4, 6, 7
3
>>> missing_digits(35578) # 4, 6
2
>>> missing_digits(12456) # 3
1
>>> missing_digits(16789) # 2, 3, 4, 5
4
>>> missing_digits(4) # No missing numbers between 4 and 4
0
>>> from construct_check import check
>>> # ban while or for loops
>>> check(HW_SOURCE_FILE, 'missing_digits', ['While', 'For'])
True
"""
"*** YOUR CODE HERE ***"
Watch the hints video below for somewhere to start:
Use Ok to test your code:
python3 ok -q missing_digits
Q5: Count coins
Given a positive integer change
, a set of coins makes change for change
if
the sum of the values of the coins is change
. Here we will use standard US Coin values: 1, 5, 10, 25 For example, the following
sets make change for 15
:
- 15 1-cent coins
- 10 1-cent, 1 5-cent coins
- 5 1-cent, 2 5-cent coins
- 5 1-cent, 1 10-cent coins
- 3 5-cent coins
- 1 5-cent, 1 10-cent coin
Thus, there are 6 ways to make change for 15
. Write a recursive function
count_coins
that takes a positive integer change
and returns the number of
ways to make change for change
using coins. Use the get_next_coin
function given to you to calculate the next largest coin denomination given your current coin. I.e. get_next_coin(5)
= 10
.
Hint: Refer the implementation of
count_partitions
for an example of how to count the ways to sum up to a final value with smaller parts. If you need to keep track of more than one value across recursive calls, consider writing a helper function.
def get_next_coin(coin):
"""Return the next coin.
>>> get_next_coin(1)
5
>>> get_next_coin(5)
10
>>> get_next_coin(10)
25
>>> get_next_coin(2) # Other values return None
"""
if coin == 1:
return 5
elif coin == 5:
return 10
elif coin == 10:
return 25
def count_coins(change):
"""Return the number of ways to make change using coins of value of 1, 5, 10, 25.
>>> count_coins(15)
6
>>> count_coins(10)
4
>>> count_coins(20)
9
>>> count_coins(100) # How many ways to make change for a dollar?
242
>>> from construct_check import check
>>> # ban iteration
>>> check(HW_SOURCE_FILE, 'count_coins', ['While', 'For'])
True
"""
"*** YOUR CODE HERE ***"
Watch the hints video below for somewhere to start:
Use Ok to test your code:
python3 ok -q count_coins
Submit
Make sure to submit this assignment by running:
python3 ok --submit
Just for fun Question
This question is out of scope for 61a. Do it if you want an extra challenge or some practice with HOF and abstraction!
Q6: 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