# Homework 2: Higher Order Functions and Lambdas hw02.zip

Due by 11:59pm on Thursday, February 2

## 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 the assignment by uploading all code files you've edited to Gradescope. 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 Gradescope. 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 2 points.

# 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
``````# A lambda expression by itself does not alter
# the environment
lambda x: x * x

# We can assign lambda functions to a name
# with an assignment statement
square = lambda x: x * x
square(3)

# Lambda expressions can be used as an operator
# or operand
negate = lambda f, x: -f(x)
negate(lambda x: x * x, 3)``````
``````def square(x):
return x * x

# A function created by a def statement
# can be referred to by its intrinsic name
square(3)``````

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

Use Ok to test your code:

``python3 ok -q product``

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

`accumulate` has the following parameters:

• `term` and `n`: the same parameters as in `product`
• `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 all `a` and `b`. However, you may not assume `merger` 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']
"""

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']
"""
``````

Use Ok to test your code:

``````python3 ok -q accumulate
python3 ok -q summation_using_accumulate
python3 ok -q product_using_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:

1. Takes in the stop value.
2. If the value of `start` is less than 0, exit the function by returning `None`.
3. If the value of `start` is greater than or equal to stop, apply `func1` on `start` and return the result.
4. 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
"""
``````

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 ______
``````

`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 ______
``````

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 ______
``````

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.

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.

1. Fall 2019 MT1 Q3: You Again [Higher Order Functions]
2. Spring 2021 MT1 Q4: Domain on the Range [Higher Order Functions]
3. Fall 2021 MT1 Q1b: tik [Functions and Expressions]