# 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:

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.

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

### 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.

No peeking! First try to implement it without the hint.

`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.

Run in 61A Code

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

`k`

positions before it.
# Document the occasion

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