Discussion 3: Environment Diagrams, Higher-Order Functions🖨️
Getting Started
Say your name and share a food that you really liked as a child. (It's ok if you still like that food now.)
Environment Diagrams
Q1: Bottles
An environment diagram keeps track of names and their values in frames, which are drawn as boxes.
Answer the following questions about the code below and afterwards, step through the diagram to check your answers.
bottles = 99
take = 1
def pass_it(around):
bottles = 98
return take
remaining = bottles - pass_it(bottles)
bottles = remaining
1) What determines how many different frames appear in an environment diagram?
a) The number of functions defined in the code
b) The number of call expressions in the code
c) The number of return statements in the code
d) The number of times user-defined functions are called when running the code
2) What happens to the return value of pass_it(bottles)?
a) It is used for the new value of remaining in the global frame
b) It is used for the new value of bottles in the global frame
c) It is used for the new value of pass_it in the global frame
d) None of the above
3) What effect does the line bottles = 98 have on the global frame?
a) It temporarily changes the value bound to bottles in the global frame.
b) It permanently changes the value bound to bottles in the global frame.
c) It has no effect on the global frame.
To check your answers, step through the environment diagram in Python Tutor (opens a new tab).
Q2: Teamwork
Draw an environment diagram for the code below. You can use paper or a tablet or the whiteboard. Talk to your group about how you are going to draw it, then go through each step together.
def team(work):
return t(work) - 1
def dream(work, s):
if work(s-2):
t = not s
return not t
work, t = 3, abs
team = dream(team, work + 1) and t
Then step through the environment diagram in Python Tutor (opens a new tab) to check your work.
Here's a blank diagram in case you're using a tablet.
Higher-Order Functions
Remember the problem-solving approach from last discussion; it works just as well for implementing higher-order functions.
- Pick an example input and corresponding output. (This time it might be a function.)
- Describe a process (in English) that computes the output from the input using simple steps.
- Figure out what additional names you'll need to carry out this process.
- Implement the process in code using those additional names.
- Determine whether the implementation really works on your original example.
- Determine whether the implementation really works on other examples. (If not, you might need to revise step 2.)
Q3: Multi-Apply
Implement multi_apply, a higher-order function that takes a one-argument
function f. It returns a function g(x, y) that takes two arguments and
applies f to x repeatedly, a total of y times; for example, when y is 3,
it evaluates f(f(f(x))).
def multi_apply(f):
"""Return a function g(x, y) that applies f to x a total of y times.
>>> def add_one(x):
... return x + 1
>>> multi_add = multi_apply(add_one)
>>> multi_add(3, 1)
4
>>> multi_add(4, 5)
9
>>> multi_add(5, 0)
5
"""
"*** YOUR CODE HERE ***"
Before you press Verify, check your work just by thinking!
Q4: Make Keeper
Implement make_keeper, which takes a positive integer n and returns a
function f that takes as its argument another one-argument function cond.
When f is called on cond, it prints out the integers from 1 to n
(including n) for which cond returns a true value when called on each of
those integers. Each integer is printed on a separate line.
def make_keeper(n):
"""Returns a function that takes one parameter cond and prints
out all integers 1..i..n where calling cond(i) returns True.
>>> def is_even(x): # Even numbers have remainder 0 when divided by 2.
... return x % 2 == 0
>>> make_keeper(5)(is_even)
2
4
>>> make_keeper(5)(lambda x: True)
1
2
3
4
5
>>> make_keeper(5)(lambda x: False) # Nothing is printed
"""
"*** YOUR CODE HERE ***"
No peeking! First try to implement it without the hint.
Hint
To return a function f, include def f(cond): as the first line of the
implementation and return f as the last. The f function should introduce i = 1 in order to loop through all integers, calling cond(i) to determine
whether cond returns true for each integer.
Optional Challenge Problems (if there's extra time)
Higher-order functions take practice to master. These are more challenging, and some of them come from past exams.
Q5: Digit Finder
Implement find_digit, which takes in a positive integer k and returns a
function that takes in a positive integer x and returns the kth digit from
the right of x. If x has fewer than k digits, it returns 0.
For example, in the number 4567, 7 is the 1st digit from the right, 6 is the 2nd digit from the right, and the 5th digit from the right is 0 (since there are only 4 digits).
Important: You may not use strings or indexing for this problem. Try to solve
this problem using only one line as a single lambda expression, since lambdas can only
contain one expression (no loops/assignments).
Tip: Use floor dividing by a power of 10 to get rid of the rightmost digits.
def find_digit(k):
"""Returns a function that returns the kth digit of x.
>>> find_digit(2)(3456)
5
>>> find_digit(2)(5678)
7
>>> find_digit(1)(10)
0
>>> find_digit(4)(789)
0
"""
assert k > 0
"*** YOUR CODE HERE ***"
Hint
First remove all of the digits after digit k, at which point digit k will
be the last digit.
Q6: Match Maker
Implement match_k, which takes in an integer k and returns a function
that takes in a variable x and returns True if all the digits in x that
are k apart are the same.
For example, match_k(2) returns a one argument function that takes in x
and checks if digits that are 2 away in x are the same.
match_k(2)(1010) has the value of x = 1010 and digits 1, 0, 1, 0 going
from left to right. 1 == 1 and 0 == 0, so the match_k(2)(1010) results
in True.
match_k(2)(2010) has the value of x = 2010 and digits 2, 0, 1, 0 going
from left to right. 2 != 1 and 0 == 0, so the match_k(2)(2010) results
in False.
Important: You may not use strings or indexing for this problem.
You may call find_digit.
Tip: Floor dividing by powers of 10 gets rid of the rightmost digits.
def match_k(k):
"""Returns a function that checks if digits k apart match.
>>> match_k(2)(1010)
True
>>> match_k(2)(2010)
False
>>> match_k(1)(1010)
False
>>> match_k(1)(1)
True
>>> match_k(1)(2111111111111111)
False
>>> match_k(3)(123123)
True
>>> match_k(2)(123123)
False
"""
def check(x):
while x // (10 ** k) > 0:
if ____________________________:
return ____________________________
x //= 10
____________________________
____________________________
Hint
In each iteration, compare the last digit with the one that is k positions
before it.
Q7: Which One
This question was Spring 2024 61A Midterm 1 Question 1(b).
What is displayed by the interactive Python interpreter after evaluating
which()(), given that the following code has been executed?
one = 1
def which():
one = 3
def this():
return one
return one + 1
return this
one = 4
Once your whole group agrees on an answer, step through it in Python Tutor (opens a new tab) to see the answer.
Q8: Choose Wisely
This question was Fall 2023 61A Midterm 1 Question 4(b). On the exam, the last two blanks were multiple choice. It is a typical problem that combines iteration and a higher-order function.
Definition: A digit test is a function that takes a non-negative integer
less than 10 and returns True or False.
Implement every, which takes a digit test t and returns a function digit
that takes a positive integer n. The digit function returns whether t
returns True for every digit of n.
def every(t):
"""Return a function of n that returns whether t returns True for every digit of n.
>>> f = every(lambda d: d % 2 == 1)
>>> f(37511) # every digit is odd
True
>>> f(2023) # Not every digit is odd
False
"""
def digit(n):
assert n > 0
while n:
if ____________________________:
____________________________
n = n // 10
return ____________________________
return ____________________________