Discussion 2: Higher-Order Functions, Environment Diagrams

• disc02.pdf

Attendance

Your TA will come around during discussion to check you in.

If you miss discussion for a good reason (such as sickness or a scheduling conflict), email cs61a@berkeley.edu within one week to receive attendance credit.

Getting Started

Q1: Warm Up

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

Environment Diagrams

Q2: Double Trouble

Draw the environment diagram on paper or a whiteboard (without having the computer draw it for you)! Then, check your work by stepping through the diagram.

Q3: Dream Work

Draw an environment diagram for the code below. Then, step through the diagram with PythonTutor to check your work.

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.

Call Expressions

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

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.

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

Hint

Q7: 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).

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

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

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