# Lab 3: Midterm Review

*Due by 11:59pm on Wednesday, September 14.*

## Starter Files

Download lab03.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.

## Submit

In order to facilitate studying for the exam, solutions to this lab are released with the lab. We encourage you to try out the problems first on your own before referencing the solutions as a guide.

**Note: You do not need to run python ok --submit to receive credit for this assignment.**

# All Questions Are Optional

The questions in this assignment are not graded, but they are highly recommended to help you prepare for the upcoming exam. You will receive credit for this lab even if you do not complete these questions.

The questions in this assignment are not graded, but they are highly recommended to help you prepare for the upcoming exam. You will receive credit for this lab even if you do not complete these questions.

# Suggested Questions

## Walkthrough Videos

These videos provide detailed walkthroughs of the problems presented in this lab.

To see these videos, you should be logged into your berkeley.edu email.

## Control

### Q1: Ordered Digits

Implement the function `ordered_digits`

, which takes as input a
positive integer and returns `True`

if its digits, read left to right,
are in non-decreasing order, and `False`

otherwise. For example, the
digits of 5, 11, 127, 1357 are ordered, but not those of 21 or 1375.

Note:You can solve this with either iteration or recursion. We recommend trying both for practice purposes but you will credit for either one.

```
def ordered_digits(x):
"""Return True if the (base 10) digits of X>0 are in non-decreasing
order, and False otherwise.
>>> ordered_digits(5)
True
>>> ordered_digits(11)
True
>>> ordered_digits(127)
True
>>> ordered_digits(1357)
True
>>> ordered_digits(21)
False
>>> result = ordered_digits(1375) # Return, don't print
>>> result
False
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q ordered_digits`

### Q2: K Runner

An *increasing run* of an integer is a sequence of consecutive digits in
which each digit is larger than the last. For example, the number 123444345
has four increasing runs: 1234, 4, 4 and 345. Each run can be indexed
**from the end** of the number, starting with index 0. In the example, the
0th run is 345, the first run is 4, the second run is 4 and the third run is
1234.

Implement `get_k_run_starter`

, which takes in integers `n`

and `k`

and returns
the 0th digit of the `k`

th increasing run within `n`

. The 0th digit is the
leftmost number in the run. You may assume that there are at least `k+1`

increasing runs in `n`

.

```
def get_k_run_starter(n, k):
"""Returns the 0th digit of the kth increasing run within n.
>>> get_k_run_starter(123444345, 0) # example from description
3
>>> get_k_run_starter(123444345, 1)
4
>>> get_k_run_starter(123444345, 2)
4
>>> get_k_run_starter(123444345, 3)
1
>>> get_k_run_starter(123412341234, 1)
1
>>> get_k_run_starter(1234234534564567, 0)
4
>>> get_k_run_starter(1234234534564567, 1)
3
>>> get_k_run_starter(1234234534564567, 2)
2
"""
i = 0
final = None
while ____________________________:
while ____________________________:
____________________________
final = ____________________________
i = ____________________________
n = ____________________________
return final
```

Use Ok to test your code:

`python3 ok -q get_k_run_starter`

## Higher Order Functions

These are some utility function definitions you may see being used as part of the doctests for the following problems.

```
from operator import add, mul
square = lambda x: x * x
identity = lambda x: x
triple = lambda x: 3 * x
increment = lambda x: x + 1
```

### Q3: Make Repeater

Implement the function `make_repeater`

so that `make_repeater(func, n)(x)`

returns `func(func(...func(x)...))`

, where `func`

is applied `n`

times. That
is, `make_repeater(func, n)`

returns another function that can then be applied
to another argument. For example, `make_repeater(square, 3)(42)`

evaluates to
`square(square(square(42)))`

.

```
def make_repeater(func, n):
"""Return the function that computes the nth application of func.
>>> add_three = make_repeater(increment, 3)
>>> add_three(5)
8
>>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 4)(5) # square(square(square(square(5))))
152587890625
>>> make_repeater(square, 0)(5) # Yes, it makes sense to apply the function zero times!
5
"""
"*** YOUR CODE HERE ***"
def composer(func1, func2):
"""Return a function f, such that f(x) = func1(func2(x))."""
def f(x):
return func1(func2(x))
return f
```

Use Ok to test your code:

`python3 ok -q make_repeater`

### Q4: Apply Twice

Using `make_repeater`

define a function `apply_twice`

that takes a function of
one argument as an argument and returns a function that applies the
original function twice. For example, if `inc`

is a function that
returns `1`

more than its argument, then `double(inc)`

should be a
function that returns two more:

```
def apply_twice(func):
""" Return a function that applies func twice.
func -- a function that takes one argument
>>> apply_twice(square)(2)
16
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q apply_twice`

### Q5: It's Always a Good Prime

Implement `div_by_primes_under`

, which takes in an integer `n`

and returns an
n-divisibility checker. An *n-divisibility-checker* is a function that takes
in an integer k and returns whether `k`

is divisible by any integers between 2
and `n`

, inclusive. Equivalently, it returns whether `k`

is divisible by any
primes less than or equal to `n`

.

Review the Disc 01 `is_prime`

problem for a reminder about prime numbers.

You can also choose to do the no lambda version, which is the same problem, just with defining functions with def instead of lambda.

Hint:If struggling, here is a partially filled out line for after the`if`

statement:`checker = (lambda f, i: lambda x: __________)(checker, i)`

```
def div_by_primes_under(n):
"""
>>> div_by_primes_under(10)(11)
False
>>> div_by_primes_under(10)(121)
False
>>> div_by_primes_under(10)(12)
True
>>> div_by_primes_under(5)(1)
False
"""
checker = lambda x: False
i = ____________________________
while ____________________________:
if not checker(i):
checker = ____________________________
i = ____________________________
return ____________________________
def div_by_primes_under_no_lambda(n):
"""
>>> div_by_primes_under_no_lambda(10)(11)
False
>>> div_by_primes_under_no_lambda(10)(121)
False
>>> div_by_primes_under_no_lambda(10)(12)
True
>>> div_by_primes_under_no_lambda(5)(1)
False
"""
def checker(x):
return False
i = ____________________________
while ____________________________:
if not checker(i):
def outer(____________________________):
def inner(____________________________):
return ____________________________
return ____________________________
checker = ____________________________
i = ____________________________
return ____________________________
```

Use Ok to test your code:

```
python3 ok -q div_by_primes_under
python3 ok -q div_by_primes_under_no_lambda
```

### Q6: Church numerals

The logician Alonzo Church invented a system of representing non-negative integers entirely using functions. The purpose was to show that functions are sufficient to describe all of number theory: if we have functions, we do not need to assume that numbers exist, but instead we can invent them.

Your goal in this problem is to rediscover this representation known as *Church
numerals*. Church numerals are a way to represent non-negative integers via
repeated function application. Specifically, church numerals (such as `zero`

, `one`

, and
`two`

below) are *functions* that take in a function `f`

and return
a new function which, when called, repeats `f`

a number of times on some argument `x`

.
Here are the definitions of `zero`

, as well as a `successor`

function, which takes in a church numeral
`n`

as an argument and returns a function that represents the church numeral one higher than `n`

:

```
def zero(f):
return lambda x: x
def successor(n):
return lambda f: lambda x: f(n(f)(x))
```

First, define functions `one`

and `two`

such that they have the same behavior
as `successor(zero)`

and `successsor(successor(zero))`

respectively, but *do
not call successor in your implementation*.

Next, implement a function `church_to_int`

that converts a church numeral
argument to a regular Python integer.

Finally, implement functions `add_church`

, `mul_church`

, and `pow_church`

that
perform addition, multiplication, and exponentiation on church numerals.

```
def one(f):
"""Church numeral 1: same as successor(zero)"""
"*** YOUR CODE HERE ***"
def two(f):
"""Church numeral 2: same as successor(successor(zero))"""
"*** YOUR CODE HERE ***"
three = successor(two)
def church_to_int(n):
"""Convert the Church numeral n to a Python integer.
>>> church_to_int(zero)
0
>>> church_to_int(one)
1
>>> church_to_int(two)
2
>>> church_to_int(three)
3
"""
"*** YOUR CODE HERE ***"
def add_church(m, n):
"""Return the Church numeral for m + n, for Church numerals m and n.
>>> church_to_int(add_church(two, three))
5
"""
"*** YOUR CODE HERE ***"
def mul_church(m, n):
"""Return the Church numeral for m * n, for Church numerals m and n.
>>> four = successor(three)
>>> church_to_int(mul_church(two, three))
6
>>> church_to_int(mul_church(three, four))
12
"""
"*** YOUR CODE HERE ***"
def pow_church(m, n):
"""Return the Church numeral m ** n, for Church numerals m and n.
>>> church_to_int(pow_church(two, three))
8
>>> church_to_int(pow_church(three, two))
9
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

```
python3 ok -q church_to_int
python3 ok -q add_church
python3 ok -q mul_church
python3 ok -q pow_church
```

## Environment Diagrams

### Q7: Doge

Draw the environment diagram for the following code.

```
wow = 6
def much(wow):
if much == wow:
such = lambda wow: 5
def wow():
return such
return wow
such = lambda wow: 4
return wow()
wow = much(much(much))(wow)
```

You can check out what happens when you run the code block using Python Tutor. Please ignore the “ambiguous parent frame” message on step 18. The parent is in fact f1.

### Q8: Environment Diagrams - Challenge

These questions were originally developed by Albert Wu and are included here for extra practice. We recommend checking your work in PythonTutor after filling in the diagrams for the code below.

#### Challenge 1

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

Guiding Notes: Pay special attention to the names of the frames!

Multiple assignments in a single line: We will first evaluate the expressions on the right of the assignment, and then assign those values to the expressions on the left of the assignment. For example, if we had

`x, y = a, b`

, the process of evaluating this would be to first evaluate`a`

and`b`

, and then assign the value of`a`

to`x`

, and the value of`b`

to`y`

.

```
def funny(joke):
hoax = joke + 1
return funny(hoax)
def sad(joke):
hoax = joke - 1
return hoax + hoax
funny, sad = sad, funny
result = funny(sad(1))
```

#### Challenge 2

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

```
def double(x):
return double(x + x)
first = double
def double(y):
return y + y
result = first(10)
```