Homework 2: Higher Order Functions and Recursion
Due by 11:59pm on Tuesday, 7/3
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
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
"""
"*** YOUR CODE HERE ***"
return 'REPLACE ME'
Use Ok to test your code:
python3 ok -q make_adder
Q2: Double Eights
Write a recursive function that takes in a number n
and determines if the
digits contain two adjacent 8
s. You can assume that n
is at least a
two-digit number.
Hint: See the recursion lecture for a simplified version of this problem where we use recursion to check if a number has a single
8
.
def double_eights(n):
""" Returns whether or not n has two digits in row that
are the number 8. Assume n has at least two digits in it.
>>> double_eights(1288)
True
>>> double_eights(880)
True
>>> double_eights(538835)
True
>>> double_eights(284682)
False
>>> double_eights(588138)
True
>>> double_eights(78)
False
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'double_eights', ['While', 'For'])
True
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q double_eights
Q3: 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 ***"
After defining product
, show how to define the
factorial function in terms of
product
.
We've provided an
identity
function, defined with a lambda expression. You might need this to writefactorial
.
# The identity function, defined using a lambda expression!
identity = lambda k: k
def factorial(n):
"""Return n factorial for n >= 0 by calling product.
>>> factorial(4)
24
>>> factorial(6)
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
Q4: Summation
Now, write a recursive implementation of summation
, which takes a positive
integer n
and a function term
. It applies term
to every number from 1
to n
including n
and returns the sum of the results.
def summation(n, term):
"""Return the sum of the first n terms in the sequence defined by term.
Implement using recursion!
>>> summation(5, lambda x: x * x * x) # 1^3 + 2^3 + 3^3 + 4^3 + 5^3
225
>>> summation(9, lambda x: x + 1) # 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
54
>>> summation(5, lambda x: 2**x) # 2^1 + 2^2 + 2^3 + 2^4 + 2^5
62
>>> # Do not use while/for loops!
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'summation',
... ['While', 'For'])
True
"""
assert n >= 1
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q summation
Q5: 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 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. You may assume thatcombiner
is commutative, i.e.,combiner(a, b) = combiner(b, a)
.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 use either iteration or recursion to solve this. 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
Q6: Filtered Accumulate
Now, extend the accumulate
function to allow for filtering the results
produced by its term
argument by filling in the implementation for the
filtered_accumulate
function:
def filtered_accumulate(combiner, base, pred, n, term):
"""Return the result of combining the terms in a sequence of N terms
that satisfy the predicate pred. combiner is a two-argument function.
If v1, v2, ..., vk are the values in term(1), term(2), ..., term(N)
that satisfy pred, then the result is
base combiner v1 combiner v2 ... combiner vk
(treating combiner 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
>>> check(HW_SOURCE_FILE, 'filtered_accumulate',
... ['While', 'For', 'Recursion'])
True
"""
def combine_if(x, y):
"*** YOUR CODE HERE ***"
return accumulate(combine_if, base, n, term)
def odd(x):
return x % 2 == 1
def greater_than_5(x):
return x > 5
filtered_accumulate
has the following parameters:
combiner
,base
,term
andn
: the same arguments asaccumulate
.pred
: a one-argument predicate function applied to the values ofterm(k)
for eachk
from 1 ton
. Only values for whichpred
returns a true value are included in the accumulated total. If no values satisfypred
, thenbase
is returned.
For example, the result of filtered_accumulate(add, 0, is_prime, 11,
identity)
is
0 + 2 + 3 + 5 + 7 + 11
for a valid definition of is_prime
.
Implement filtered_accumulate
by defining the combine_if
function. Exactly
what this function does is something for you to discover. Do not use any loops
or make any recursive calls to filtered_accumulate
.
Hint: The order in which you pass the arguments to
combiner
in your solution toaccumulate
matters here.
Use Ok to test your code:
python3 ok -q filtered_accumulate
Q7: 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
Extra questions
Extra questions are not worth extra credit and are entirely optional. They are designed to challenge you to think creatively!
Q8: Anonymous factorial
The recursive factorial function can be written as a single expression by using a conditional expression.
>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))
>>> fact(5)
120
However, this implementation relies on the fact (no pun intended) that
fact
has a name, to which we refer in the body of fact
. To write a
recursive function, we have always given it a name using a def
or
assignment statement so that we can refer to the function within its
own body. In this question, your job is to define fact recursively
without giving it a name!
Write an expression that computes n
factorial using only call
expressions, conditional expressions, and lambda expressions (no
assignment or def statements). Note in particular that you are not
allowed to use make_anonymous_factorial
in your return expression.
The sub
and mul
functions from the operator
module are the only
built-in functions required to solve this problem:
from operator import sub, mul
def make_anonymous_factorial():
"""Return the value of an expression that computes factorial.
>>> make_anonymous_factorial()(5)
120
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'make_anonymous_factorial', ['Assign', 'AugAssign', 'FunctionDef', 'Recursion'])
True
"""
return 'YOUR_EXPRESSION_HERE'
Use Ok to test your code:
python3 ok -q make_anonymous_factorial