Discussion 2: Environment Diagrams, Higher-Order Functions

• disc02.pdf

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

If your group has 6 or more students, you're welcome to split into two sub-groups and then sync up at the end.

Q1: Warm Up

What is the value of result after executing result = (lambda x: 2 * (lambda x: 3)(4) * x)(5)?

Higher-Order Functions

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.

Call Expressions

Q3: Silence of the Lambda

Draw the environment diagram on paper or a tablet (without having the computer draw it for you)! Then, check your work by stepping through the diagram with PythonTutor. This problem's video contains the solution.

Q4: Match Maker

Assume that find_digit(k) is correctly implemented. find_digit 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.

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.

Hint

Q5: Ups and Downs A

Definition. Two adjacent digits in a non-negative integer are an increase if the left digit is smaller than the right digit, and a decrease if the left digit is larger than the right digit.

For example, 61127 has 2 increases (1 → 2 and 2 → 7) and 1 decrease (6 → 1).

You may use the sign function defined below in all parts of this question.

def sign(x):
    if x > 0:
        return 1
    elif x < 0:
        return- 1
    else:
        return 0

Implement ramp, which takes a non-negative integer n and returns whether it has more increases than decreases when reading its digits from left to right (see the definition above).

Q6: Ups and Downs C

The process function below uses tally and result functions to analyze all adjacent pairs of digits in a non-negative integer n. A tally function is called on each pair of adjacent digits.

def process(n, tally, result):
    """Process all pairs of adjacent digits in N using functions TALLY and RESULT.
    """ 

    while n >= 10:
        tally, result = tally(n % 100 // 10, n % 10)
        n = n // 10
    return result()

Implement ups, which returns two functions that can be passed as tally and result arguments to process, so that process computes whether a non-negative integer n has exactly k increases.

Hint: You can use sign from the previous page and the built-in max and min functions.

Q7: Choose Wisely A

Definition: A digit test is a function that takes a non-negative integer less than 10 and returns True or False.

Implement only which takes a non-negative integer n and a digit test t. It returns a non-negative integer containing only the digits of n for which t returns True when called on each of those digits. The digits should appear in the same order as they did in n. The number 0 has no digits. You may not use str or repr or [ or ] or for.

Q8: Choose Wisely B

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.