Homework 2 Solutions
Solution Files
You can find solutions for all questions in hw02.py.
Required questions
Getting Started Videos
These videos may provide some helpful direction for tackling the coding problems on this assignment.
To see these videos, you should be logged into your berkeley.edu email.
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
Lambda expressions are expressions that evaluate to functions by specifying two things: the parameters and a return expression.
lambda <parameters>: <return expression>
While both lambda
expressions and def
statements create function objects,
there are some notable differences. lambda
expressions work like other
expressions; much like a mathematical expression just evaluates to a number and
does not alter the current environment, a lambda
expression
evaluates to a function without changing the current environment. Let's take a
closer look.
lambda | def | |
---|---|---|
Type | Expression that evaluates to a value | Statement that alters the environment |
Result of execution | Creates an anonymous lambda function with no intrinsic name. | Creates a function with an intrinsic name and binds it to that name in the current environment. |
Effect on the environment | Evaluating a lambda expression does not create or
modify any variables. |
Executing a def statement both creates a new function
object and binds it to a name in the current environment. |
Usage | A lambda expression can be used anywhere that
expects an expression, such as in an assignment statement or as the
operator or operand to a call expression. |
After executing a def statement, the created
function is bound to a name. You should use this name to refer to the
function anywhere that expects an expression. |
Example |
|
|
Higher Order Functions
Q1: Product
Write a function called product
that returns term(1) * ... * term(n)
.
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 = term(k) * total, k + 1
return total
Use Ok to test your code:
python3 ok -q product
The total
variable is used to keep track of the total product so far. We
start with total = 1
since we will be multiplying and anything multiplied
by 1 is itself. We then initialize the counter variable k to use in the while
loop to ensures that we get through all values 1 through k.
Q2: Accumulate
Let's take a look at how product
is an instance of a more
general function called accumulate
, which we would like to implement:
def accumulate(merger, start, n, term):
"""Return the result of merging the first n terms in a sequence and start.
The terms to be merged are term(1), term(2), ..., term(n). merger 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
>>> # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1)
>>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
19
>>> # ((2 * 1^2 * 2) * 2^2 * 2) * 3^2 * 2
>>> accumulate(lambda x, y: 2 * x * y, 2, 3, square)
576
>>> accumulate(lambda x, y: (x + y) % 17, 19, 20, square)
16
"""
total, k = start, 1
while k <= n:
total, k = merger(total, term(k)), k + 1
return total
# Alternative solution
def accumulate_reverse(merger, start, n, term):
total, k = start, n
while k >= 1:
total, k = merger(total, term(k)), k - 1
return total
accumulate
has the following parameters:
term
andn
: the same parameters as inproduct
merger
: a two-argument function that specifies how the current term is merged with the previously accumulated terms.start
: 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
Note: You may assume that
merger
is commutative. That is,merger(a, b) == merger(b, a)
for alla
andb
. However, you may not assumemerger
is chosen from a fixed function set and hard-code the solution.
After implementing accumulate
, show how summation
and product
can both be
defined as function calls to accumulate
.
Important:
You should have a single line of code (which should be a return
statement)
in each of your implementations for summation_using_accumulate
and
product_using_accumulate
, which the syntax check will check for.
def summation_using_accumulate(n, term):
"""Returns the sum: term(1) + ... + term(n), using accumulate.
>>> summation_using_accumulate(5, square)
55
>>> summation_using_accumulate(5, triple)
45
>>> # You aren't expected to understand the code of this test.
>>> # Check that the bodies of the functions are just return statements.
>>> # If this errors, make sure you have removed the "***YOUR CODE HERE***".
>>> import inspect, ast
>>> [type(x).__name__ for x in ast.parse(inspect.getsource(summation_using_accumulate)).body[0].body]
['Expr', 'Return']
"""
return accumulate(add, 0, n, term)
def product_using_accumulate(n, term):
"""Returns the product: term(1) * ... * term(n), using accumulate.
>>> product_using_accumulate(4, square)
576
>>> product_using_accumulate(6, triple)
524880
>>> # You aren't expected to understand the code of this test.
>>> # Check that the bodies of the functions are just return statements.
>>> # If this errors, make sure you have removed the "***YOUR CODE HERE***".
>>> import inspect, ast
>>> [type(x).__name__ for x in ast.parse(inspect.getsource(product_using_accumulate)).body[0].body]
['Expr', 'Return']
"""
return accumulate(mul, 1, n, term)
Use Ok to test your code:
python3 ok -q accumulate
python3 ok -q summation_using_accumulate
python3 ok -q product_using_accumulate
We want to abstract the logic of product
and summation
into accumulate
.
The differences between product
and summation
are:
- How to merge terms. For
product
, we merge via*
(mul
). Forsummation
, we merge via+
(add
). - The starting value. For
product
, we want to start off with 1 since starting with 0 means that our result (via multiplying with the start) will always be 0. Forsummation
, we want to start off with 0 so we're not adding any extra value what we are trying to sum.
We can then define the merge method as merger
and the starting value
as start
inside our accumulate
, with the remaining logic of going
through the loop being similar to product
and summation
.
Once we've defined accumulate
, we can now implement
product_using_accumulate
and summation_using_accumulate
by passing in the
appropriate parameters to accumulate
.
Takeaway: Notice how quick it is now to create accumulator functions with different merger
functions!
This is because we abstracted away the logic of product
and summation
into the accumulate
function. Without this abstraction, our code for a summation
function would be just as long as our code for the product
function from Question 1, and the logic would be highly redundant!
Q3: Funception
Write a function (funception) that takes in another function func1
and a number start
and returns a function (func2
) that will have
one parameter to take in the stop value. func2
should take the
following into consideration in order:
- Takes in the stop value.
- If the value of
start
is less than 0, exit the function by returningNone
. - If the value of
start
is greater than or equal to stop, applyfunc1
onstart
and return the result. - If not, apply
func1
on all the numbers from start (inclusive) up to stop (exclusive) and return the product.
def funception(func1, start):
""" Takes in a function (function 1) and a start value.
Returns a function (function 2) that will find the product of
function 1 applied to the range of numbers from
start (inclusive) to stop (exclusive)
>>> def func1(num):
... return num + 1
>>> func2_1 = funception(func1, 0)
>>> func2_1(3) # func1(0) * func1(1) * func1(2) = 1 * 2 * 3 = 6
6
>>> func2_2 = funception(func1, 1)
>>> func2_2(4) # func1(1) * func1(2) * func1(3) = 2 * 3 * 4 = 24
24
>>> func2_3 = funception(func1, 3)
>>> func2_3(2) # Returns func1(3) since start >= stop
4
>>> func2_4 = funception(func1, 3)
>>> func2_4(3) # Returns func1(3) since start >= stop
4
>>> func2_5 = funception(func1, -2)
>>> func2_5(-3) # Returns None since start < 0
>>> func2_6 = funception(func1, -1)
>>> func2_6(4) # Returns None since start < 0
"""
def func2(stop):
i = start
product = 1
if start < 0:
return None
if start >= stop:
return func1(start)
while i < stop:
product *= func1(i)
i += 1
return product
return func2
Use Ok to test your code:
python3 ok -q funception
Lambda Expressions
Q4: Lambda Math
To get familiar with writing lambda
expressions, let's see how we can use them to help us do some math.
Important:
For each of the following problems, your solution should have only a single line of code (which should be a return
statement).
The syntax check will check for this.
We can start by using a lambda
to complete the mul_by_num
function.
def mul_by_num(num):
"""Returns a function that takes one argument and returns num
times that argument.
>>> x = mul_by_num(5)
>>> y = mul_by_num(2)
>>> x(3)
15
>>> y(-4)
-8
"""
return lambda num2: num * num2
mul_by_num
takes in a single number as an argument, and returns a one argument function that multiplies any value passed to it by the original number.
Use Ok to test your code:
python3 ok -q mul_by_num
The next thing we want to do is to use a lambda
expression to create a function that takes in two integers, x
and y
, and returns whether or not x
is evenly divisible by y
. Complete the function mod_maker
, which has no input but will return a function that, when called on two integers, will return True if x
is divisible by y
. Otherwise, it should return the remainder of x % y
.
def mod_maker():
"""Return a two-argument function that performs the modulo operation and returns True if the numbers are divisble, and the remainder otherwise.
>>> mod = mod_maker()
>>> mod(7, 2) # 7 % 2
1
>>> mod(4, 8) # 4 % 8
4
>>> mod(8,4) # 8 % 4
True
"""
return lambda x, y: x % y or True
Note: You are allowed (and expected) to use the modulo operator itself in your solution. The goal of this function is not to recreate the operator from scratch, but to create an alternate way of calling it.
Use Ok to test your code:
python3 ok -q mod_maker
For our third bit of lambda practice, write a function that takes in two functions, f1
and f2
, and returns another function that takes in a single argument x
. The returned function should compute f1(x) + f2(x)
. You can assume both f1
and f2
take in one argument, and their result can be added
together.
def add_results(f1, f2):
"""
Return a function that takes in a single variable x, and returns
f1(x) + f2(x). You can assume the result of f1(x) and f2(x) can be
added together, and they both take in one argument.
>>> identity = lambda x: x # returns input
>>> square = lambda x: x**2
>>> a1 = add_results(identity, square) # x + x^2
>>> a1(4)
20
>>> a2 = add_results(a1, identity) # (x + x^2) + x
>>> a2(4)
24
>>> a2(5)
35
>>> a3 = add_results(a1, a2) # (x + x^2) + (x + x^2 + x)
>>> a3(4)
44
"""
return lambda x: f1(x) + f2(x)
Use Ok to test your code:
python3 ok -q add_results
Use Ok to run the local syntax checker (which checks that each of your solutions only contains one line):
python3 ok -q lambda_math_syntax_check
Takeaway: Although lambda functions have more restrictions about what they can contain in their bodies than regular functions, they are still useful, especially for making minor tweaks and additions to pre-existing code that doesn't have quite the right structure for what we are trying to do.
Check Your Score Locally
You can locally check your score on each question of this assignment by running
python3 ok --score
This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.
Submit
Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.
Exam Practice
Homework assignments will also contain prior exam questions for you to try. These questions have no submission component; feel free to attempt them if you'd like some practice!
Note that exams from Spring 2020, Fall 2020, and Spring 2021 gave students access to an interpreter, so the question format may be different than other years. Regardless, the questions below are good problems to try without access to an interpreter.
- Fall 2019 MT1 Q3: You Again [Higher Order Functions]
- Spring 2021 MT1 Q4: Domain on the Range [Higher Order Functions]
- Fall 2021 MT1 Q1b: tik [Functions and Expressions]