# Discussion 2: Higher-Order Functions, Self Reference, Lambda Expressions

# Higher Order Functions

A **higher order function** (HOF) is a function that manipulates other functions by taking in functions as arguments, returning a function, or both. For example, the function `compose1`

below takes in two functions as arguments and returns a function that is the composition of the two arguments.

```
def compose1(f, g):
def h(x):
return f(g(x))
return h
```

HOFs are powerful abstraction tools that allow us to express certain general patterns as named concepts in our programs.

## A Note on Lambda Expressions

A lambda expression evaluates to a function, called a lambda function. For example, `lambda y: x + y`

is a lambda expression, and can be read as “a function that takes in one parameter `y`

and returns `x + y`

.”

A lambda expression by itself evaluates to a function but does not bind it to a name. Also note that the return expression of this function is not evaluated until the lambda is called. This is similar to how defining a new function using a def statement does not execute the function’s body until it is later called.

```
>>> what = lambda x : x + 5
>>> what
<function <lambda> at 0xf3f490>
```

Unlike `def`

statements, lambda expressions can be used as an operator or an operand to a call expression. This is because they are simply one-line expressions that evaluate to functions. In the example below, `(lambda y: y + 5)`

is the operator and `4`

is the operand.

```
>>> (lambda y: y + 5)(4)
9
>>> (lambda f, x: f(x))(lambda y: y + 1, 10)
11
```

### Q1: Keep Ints

Write a function that takes in a function `cond`

and a number `n`

and prints numbers from 1 to `n`

where calling `cond`

on that number returns `True`

.

**Your Answer**Run in 61A Code

**Solution**

```
def keep_ints(cond, n):
"""Print out all integers 1..i..n where cond(i) is true
>>> def is_even(x):
... # Even numbers have remainder 0 when divided by 2.
... return x % 2 == 0
>>> keep_ints(is_even, 5)
2
4
"""
i = 1
while i <= n:
if cond(i):
print(i)
i += 1
```

### Q2: Make Keeper

Write a function similar to `keep_ints`

like in Question 1, but now it takes in a number `n`

and returns a function that has one parameter `cond`

. The returned function prints out numbers from 1 to `n`

where calling `cond`

on that number returns `True`

.

**Your Answer**Run in 61A Code

**Solution**

```
def make_keeper(n):
"""Returns a function which 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
"""
def do_keep(cond):
i = 1
while i <= n:
if cond(i):
print(i)
i += 1
return do_keep
```

## HOFs in Environment Diagrams

Recall that an **environment diagram** keeps track of all the variables that have been defined and the values they are bound to. However, values are not necessarily only integers and strings. Environment diagrams can model more complex programs that utilize higher order functions.

Lambdas are represented similarly to functions in environment diagrams, but since they lack instrinsic names, the lambda symbol (λ) is used instead. If there are multiple lambda statements in the code, we may index them λ1, λ2, etc.

The parent of any function (including lambdas) is always the frame in which the function is defined. It is useful to include the parent in environment diagrams in order to find variables that are not defined in the current frame. In the previous example, when we call `add_two`

(which is really the lambda function), we need to know what `x`

is in order to compute `x + y`

. Since `x`

is not in the frame `f2`

, we look at the frame’s parent, which is `f1`

. There, we find `x`

is bound to 2.

As illustrated above, higher order functions that return a function have their return value represented with a pointer to the function object.

## Currying

One important application of HOFs is converting a function that takes multiple arguments into a chain of functions that each take a single argument. This is known as **currying**. For example, the function below converts the `pow`

function into its curried form:

```
>>> def curried_pow(x):
def h(y):
return pow(x, y)
return h
>>> curried_pow(2)(3)
8
```

### Q3: Curry2 Diagram

Draw the environment diagram that results from executing the code below.

```
def curry2(h):
def f(x):
def g(y):
return h(x, y)
return g
return f
make_adder = curry2(lambda x, y: x + y)
add_three = make_adder(3)
add_four = make_adder(4)
five = add_three(2)
```

**Your Answer**

Return value |

Return value |

Return value |

Return value |

Return value |

**Solution**

### Q4: Curry2 Lambda

Write `curry2`

as a lambda function.

**Your Answer**Run in 61A Code

**Solution**

`curry2 = lambda h: lambda x: lambda y: h(x, y)`

### Q5: HOF Diagram Practice

Draw the environment diagram that results from executing the code below.

```
n = 7
def f(x):
n = 8
return x + 1
def g(x):
n = 9
def h():
return x + 1
return h
def f(f, x):
return f(x + n)
f = f(g, n)
g = (lambda y: y())(f)
```

**Your Answer**

Return value |

Return value |

Return value |

Return value |

**Solution**

# Self Reference

Self-reference refers to a particular design of HOF, where a function eventually returns itself. In particular, a self-referencing function will not return a function **call**, but rather the function object itself. As an example, take a look at the `print_all`

function:

```
def print_all(x):
print(x)
return print_all
```

Self-referencing functions will oftentimes employ helper functions that reference the outer function, such as the example below, `print_sums`

.

```
def print_sums(n):
print(n)
def next_sum(k):
return print_sums(n + k)
return next_sum
```

A call to `print_sums`

returns `next_sum`

. A call to `next_sum`

will return the result of calling `print_sums`

which will, in turn, return another function `next_sum`

. This type of pattern is common in self-referencing functions.

A Note on Recursion: This differs from recursion because typically each new call returns a new function rather than a function call. We have not yet covered recursion so don’t worry too much about what this means!

### Q6: Make Keeper Redux

In this question, we will explore the execution of a self-reference function, `make_keeper_redux`

, based off Question 2, `make_keeper`

. The function `make_keeper_redux`

is similar to `make_keeper`

, but now the function returned by `make_keeper_redux`

should be self-referential—i.e., the returned function should return a function with the same behavior as `make_keeper_redux`

. Feel free to paste and modify your code for `make_keeper`

below.

(Hint: you only need to add one line to your `make_keeper`

solution. What is currently missing from `make_keeper_redux`

?)

**Your Answer**Run in 61A Code

**Solution**

```
def make_keeper_redux(n):
"""Returns a function. This function takes one parameter <cond> and prints out
all integers 1..i..n where calling cond(i) returns True. The returned
function returns another function with the exact same behavior.
>>> def multiple_of_4(x):
... return x % 4 == 0
>>> def ends_with_1(x):
... return x % 10 == 1
>>> k = make_keeper_redux(11)(multiple_of_4)
4
8
>>> k = k(ends_with_1)
1
11
>>> k
<function do_keep>
"""
# Paste your code for make_keeper here!
def do_keep(cond):
i = 1
while i <= n:
if cond(i):
print(i)
i += 1
return make_keeper_redux(n)
return do_keep
```

### Q7: Print Delayed

Write a function `print_delayed`

that delays printing its argument until the next function call. `print_delayed`

takes in an argument `x`

and returns a new function `delay_print`

. When `delay_print`

is called, it prints out `x`

and returns another `delay_print`

.

**Your Answer**Run in 61A Code

**Solution**

```
def print_delayed(x):
"""Return a new function. This new function, when called, will print out x and return another function with the same behavior.
>>> f = print_delayed(1)
>>> f = f(2)
1
>>> f = f(3)
2
>>> f = f(4)(5)
3
4
>>> f("hi") # a function is returned
5
<function delay_print>
"""
def delay_print(y):
print(x) return print_delayed(y) return delay_print
```

### Q8: Print N

Write a function `print_n`

that can take in an integer `n`

and returns a repeatable print function that can print the next `n`

parameters. After the nth parameter, it just prints "done".

**Your Answer**Run in 61A Code

**Solution**

```
def print_n(n):
"""
>>> f = print_n(2)
>>> f = f("hi")
hi
>>> f = f("hello")
hello
>>> f = f("bye")
done
>>> g = print_n(1)
>>> g("first")("second")("third")
first
done
done
<function inner_print>
"""
def inner_print(x):
if n <= 0: print("done")
else:
print(x)
return print_n(n - 1) return inner_print
```

# Exam prep

We recommending reading sections 1.1-1.6 from the textbook for these problems.

Test your work! For example, for `match_k`

, you can type `test(match_k)`

in the python interpreter you get once you click Run in 61A Code to verify if you pass the doctests or not.

### Q9: YY Diagram

Draw the environment diagram that results from executing the code below.

Tip: Using the

`+`

operator with two strings results in the second string being appended to the first. For example`"C"`

+`"S"`

concatenates the two strings into one string`"CS"`

.

```
y = "y"
h = y
def y(y):
h = "h"
if y == h:
return y + "i"
y = lambda y: y(h)
return lambda h: y(h)
y = y(y)(y)
```

**Your Answer**

Return value |

Return value |

Return value |

Return value |

**Solution**

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

.

**RESTRICTION:** You may not use strings or indexing for this problem.

**IMPORTANT:** You do not have to use all the lines, one staff solution does not use the line directly above the while loop.

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

**Your Answer**Run in 61A Code

**Solution**

```
def match_k(k):
""" Return 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): i = 0 while 10 ** (i + k) < x: if (x // 10**i) % 10 != (x // 10 ** (i + k)) % 10: return False i = i + 1 return True return check
# Alternate solution
def match_k_alt(k):
""" Return a function that checks if digits k apart match
>>> match_k_alt(2)(1010)
True
>>> match_k_alt(2)(2010)
False
>>> match_k_alt(1)(1010)
False
>>> match_k_alt(1)(1)
True
>>> match_k_alt(1)(2111111111111111)
False
>>> match_k_alt(3)(123123)
True
>>> match_k_alt(2)(123123)
False
"""
def check(x):
while x // (10 ** k):
if (x % 10) != (x // (10 ** k)) % 10:
return False
x //= 10
return True
return check
```

### Q11: My Last Three Brain Cells

A `k`

-*memory function* takes in a single input, prints whether that input was seen exactly `k`

function calls
ago, and returns a new `k`

-memory function. For example, a 2-memory function will display “Found" if its
input was seen exactly two function calls ago, and otherwise will display “Not found".

Implement `three_memory`

, which is a three-memory function. You may assume that the value None is
never given as an input to your function, and that in the first two function calls the function will display
“Not found" for any valid inputs given.

**Your Answer**Run in 61A Code

**Solution**

```
def three_memory(n):
"""
>>> f = three_memory('first')
>>> f = f('first')
Not found
>>> f = f('second')
Not found
>>> f = f('third')
Not found
>>> f = f('second') # 'second' was not input three calls ago
Not found
>>> f = f('second') # 'second' was input three calls ago
Found
>>> f = f('third') # 'third' was input three calls ago
Found
>>> f = f('third') # 'third' was not input three calls ago
Not found
"""
def f(x, y, z):
def g(i):
if i == x: print('Found') else:
print('Not found') return f(y, z, i) return g return f(None, None, n)
```

### Q12: Natural Chainz

For this problem, a `chain_function`

is a higher order function that repeatedly accepts natural numbers (positive integers).
The first number that is passed into the function that `chain_function`

returns initializes a natural chain,
which we define as a consecutive sequence of increasing natural numbers (i.e., 1, 2, 3). A natural chain
breaks when the next input differs from the expected value of the sequence. For example, the sequence
(1, 2, 3, 5) is broken because it is missing a 4.

Implement the `chain_function`

so that it prints out the
value of the expected number at each chain break as well as the number of chain breaks seen so far,
including the current chain break. Each time the chain breaks, the chain restarts at the most recently input number.

For example, the sequence (1, 2, 3, 5, 6) would only print 4 and 1. We print 4 because there is a missing 4, and we print 1 because the 4 is the first number to break the chain. The 5 broke the chain and restarted the chain, so from here on out we expect to see numbers increasingly linearly from 5. See the doctests for more examples. You may assume that the higher-order function is never given numbers ≤ 0.

**IMPORTANT:** For this problem, the starter code template is just a suggestion. You are welcome to add/delete/modify the starter code template, or even write your own solution that doesn’t use the starter code at all.

**Your Answer**Run in 61A Code

**Solution**

```
def chain_function():
"""
>>> tester = chain_function()
>>> x = tester(1)(2)(4)(5) # Expected 3 but got 4, so print 3. 1st chain break, so print 1 too.
3 1
>>> x = x(2) # 6 should've followed 5 from above, so print 6. 2nd chain break, so print 2
6 2
>>> x = x(8) # The chain restarted at 2 from the previous line, but we got 8. 3rd chain break.
3 3
>>> x = x(3)(4)(5) # Chain restarted at 8 in the previous line, but we got 3 instead. 4th break
9 4
>>> x = x(9) # Similar logic to the above line
6 5
>>> x = x(10) # Nothing is printed because 10 follows 9.
>>> y = tester(4)(5)(8) # New chain, starting at 4, break at 6, first chain break
6 1
>>> y = y(2)(3)(10) # Chain expected 9 next, and 4 after 10. Break 2 and 3.
9 2
4 3
"""
def g(x, y):
def h(n):
if x == 0 or n == x: return g(n + 1, y) else:
# BEGIN SOLUTION ALT="return ____________________________" NO PROMPT
return print(x, y + 1) or g(n + 1, y + 1) return h return g(0, 0)
```

To better understand this solution, let’s rename `y`

to be `count`

and `x`

to be `expected_num`

. Let `n`

be
`observed_num`

. Then on each call to h, we first check whether `observed_num`

== `expected_num`

, which in
our problem is a check for `n`

== `x`

. If this condition is satisfied, then we increment our `expected_num`

by
one and do not change our `count`

. Hence, we have a call to g with an incremented `x`

and an unchanged `y`

,
and we do not print anything. The only other case in which we enter this suite is when `(x, y) == (0, 0)`

,
which is when we pass in the very first number of the chain. We are told in the problem statement that
we can assume there will never be a non-positive input to the chain. Hence, passing in (0, 0) as arguments
to g is a sure indicator to h that we are currently on the first number of a chain, and we should not print
anything (otherwise, when else would you see a 0 passed in as `x`

?).

The second case is trickier. First, we need to print a number if our expected number differs from the
observed number, but we also need to update `expected_num`

and `count`

since the chain is going to restart
when the chain breaks. To do this in one line, we appeal to lab01, in which we learned that the return
value of print is None, which is false-y, and that or operators short-circuit only if a truth-y value is encountered before the last operand. We can print `x`

which is our expected number along with the number
of chain breaks `y + 1`

. This whole procedure returns None, so if we stick it as the first operand of the or
operator, we know that the or operator will not short-circuit. The program will then proceed to evaluate
`g(n + 1, y + 1)`

, which returns `h`

. Although not necessary for this problem, it may be helpful to know
that a function is truth-y. In this case, it doesn’t matter because an or will return the last operand it is
given if it doesn’t short-circuit, regardless of the truth-y-ness of the last operand. Hence, the last line of
`h`

prints the appropriate numbers, updates the `expected_num`

(restarting the chain), updates the count,
and returns `h`

, which will accept the next natural number into the chain.Why does `g`

return `h`

? Watch the
indentations of each line very closely. The only thing the `g`

function does is define a function h and then
return `h`

. All that other stuff where we check for equality and return print etc is all inside the `h`

function.
Hence, that code is not executed until we call `h`

.

As a side note, if you are stuck on a problem like this one on an exam, it may be helpful to ignore
the skeleton and first implement the code assuming you have unlimited lines and freedom to name your
variables whatever you want. When I was writing this question, I named all my functions something
meaningful, and you bet that my variables were not `x`

and `y`

but `expected_num`

and `count`

. I also had a
separate line for the print. However, once I got into making a template skeleton for an exam level problem, I thought
"how do I obfuscate the code to force people to think harder?" The variable name changes were easy, and
condensing the print into the same line as the return was just a trick I’ve seen from previous exams in
this course. I think that coming up with the whole solution from scratch by following the template is
immensely harder than first coming up with your own working solution and then massaging your solution
into the constraints of our blank lines.

- Derek Wan, Fall 2020