Discussion 3: Higher-Order Functions

If there are fewer than 3 people in your group, feel free to merge your group with another group in the room.

Now 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 lab).

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.

Getting Started [2 minutes]

Say your name and share a food that you really liked as a child. (It's ok if you still like that food now.)

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 the course staff.

Higher-Order Functions [40 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.)

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

Your Answer
Run in 61A Code
Solution
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
    """
    def f(cond):
        i = 1
        while i <= n:
            if cond(i):
                print(i)
            i += 1
    return f

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 unless you're confident your answer is correct. You can check it just by thinking!. If you get stuck, ask the staff for help.

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

Hint: Floor dividing by powers of 10 gets rid of the rightmost digits.

Your Answer
Run in 61A Code
Solution
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 (x % 10) != (x // (10 ** k)) % 10:
                return False
            x //= 10
        return True
    return check
In each iteration, compare the last digit with the one that is k positions before it.

Document the occasion

Please all fill out the attendance form (one submission per person per week).