Discussion 2: Environment Diagrams, Higher-Order Functions

Switch to Pensieve:

  • Everyone: Go to pensieve.co, log in with your @berkeley.edu email, and enter your group number (which was in the email that assigned you to this discussion). As long as you all enter the same number (any number), you'll all be using a shared document.

Once you're on Pensieve, you don't need to return to this page; Pensieve has all the same content (but more features). If for some reason Penseive doesn't work, return to this page and continue with the discussion.

Attendance

Your TA will come around during discussion to check you in. You can start on the worksheet before being checked in; you don't need to wait for your TA to get started.

If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your discussion): attendance form

Getting Started [5 minutes]

Say your name and a city (or place) that you like, which is not Berkeley and is not where you have lived. Feel free to share why you like it.

VERY IMPORTANT: In this discussion, don't press Check Answer or run any Python code until your whole group is sure that the answer is right. Your goal should be to have all checks pass the first time! Figure things out and check your work by thinking about what your code will do and discussing with others. Not sure? Talk to your group or a TA! (You won't get to run Python during the midterm, so get used to solving problems without it now.)

If your group has 6 or more students, you're welcome to split into two sub-groups and then sync up at the end. If you want two separate Pensieve documents for the two sub-groups, just have one sub-group add 1000 to their group number.

Q1: Warm Up

What is the value of result after executing result = (lambda x: 2 * (lambda x: 3)(4) * x)(5)? Talk about it with your whole group and make sure you all agree before anybody checks the answer.

Call Expressions [15 minutes]

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. Then, step through the diagram generated by Python Tutor to check your work.

Here's a blank diagram in case you're using a tablet:

template

If you have questions, ask them instead of just looking up the answer! First ask your group, and then your TA.

Higher-Order Functions [60 minutes]

Remember the problem-solving approach from last discussion; it works just as well for implementing higher-order functions.

  1. Pick an example input and corresponding output. (This time it might be a function.)
  2. Describe a process (in English) that computes the output from the input using simple steps.
  3. Figure out what additional names you'll need to carry out this process.
  4. Implement the process in code using those additional names.
  5. Determine whether the implementation really works on your original example.
  6. Determine whether the implementation really works on other examples. (If not, you might need to revise step 2.)

Q2: 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.

No peeking! First try to implement it without the 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.

Don't run Python to check your work. You can check it just by thinking!.

Once your group has converged on a solution, now it's time to practice your ability to describe your own code. A good description is like a good program: concise and accurate. Nominate someone to describe how your solution works and have them present to the group. If you want feedback, you can also present to your TA.

Q3: 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.

Tip: Use floor dividing by a power of 10 to get rid of the rightmost digits.

First remove all of the digits after digit k, at which point digit k will be the last digit.

Q4: 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.

In each iteration, compare the last digit with the one that is k positions before it.

Optional Exam Review

Here are some recent Midterm 1 problems that are similar to the problems you just solved. If you have extra time, discuss them with your group. If you don't have enough time, you could schedule another meeting with your group before the midterm to go through these together.

Here's a good format for group exam review:

  • First, everyone read the question but don't solve it yet.
  • Second, see if anyone has any questions about what the problem is asking for.
  • Third, let everyone work individually for five minutes or so to try to make progress on their own.
  • Fourth, have the people who got stuck (which is ok!) explain what they tried.
  • Fifth, give suggestions to the people who got stuck about what they might have tried to keep making progress.
  • Finally, talk through potential solutions to the problem.

Avoid the temptation to look up the solution until your whole group is confident that you've reached a correct answer.

  • Spring 2024 Midterm 1 Question 1(b) asked for the value of which()() after executing the following code:
one = 1
def which():
    one = 3
    def this():
        return one
        return one + 1
    return this
    one = 4
  • Fall 2023 Midterm 1 Question 4(b) is a typical problem that combines iteration and higher-order function. It relies on this definition from 4(a), "A digit test is a function that takes a non-negative integer less than 10 and returns True or False."
  • Spring 2024 Midterm 1 Questions 4(b) and 4(c) go together. 4(b) is very similar to the question above (4(b) from Fall 2023), and 4(c) is a typical problem that asks you to use a function that has already been defined.

All past exams are here: cs61a.org/resources/