Due at 11:59pm on Friday, 02/03/2017.

## Starter Files

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

## Submission

By the end of this lab, you should have submitted the lab with `python3 ok --submit`. You may submit more than once before the deadline; only the final submission will be graded.

• Questions 1 - 4 must be completed in order to receive credit for this lab. Starter code for questions 3 and 4 is in lab02.py.
• Questions 5 and 6 (Environment Diagrams) are optional. It is recommended that you work on these should you finish the required section early.
• Questions 7 - 11 are also optional. It is recommended that you complete these problems on your own time. Starter code for the questions are in lab02_extra.py.

# Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.

## Lambdas

Lambda expressions are one-line functions that specify two things: the parameters and the return value.

``lambda <parameters>: <return value>``

While both `lambda` and `def` statements are related to functions, there are some differences.

lambda def
Type `lambda` is an expression `def` is a statement
Description Evaluating a `lambda` expression does not create or modify any variables. Lambda expressions just create new function values. Executing a `def` statement will create a new function value and bind it to a variable in the current environment.
Example
``````lambda x: x * x
``````
``````def square(x):
return x * x``````

A `lambda` expression by itself is not very interesting. As with any values such as numbers, Booleans, strings, we usually:

• assign lambdas to variables (`foo = lambda x: x`)
• pass them in to other functions (`bar(lambda x: x)`)

## Higher Order Functions

A higher order function is a function that manipulates other functions by taking in functions as arguments, returning a function, or both. We will be exploring many applications of higher order functions.

# Required Questions

## What Would Python Display?

### Question 1: WWPD: Lambda the Free

Use OK to test your knowledge with the following "What Would Python Display?" questions:

``python3 ok -q lambda -u``

Hint: Remember for all WWPD questions, input `Function` if you believe the answer is `<function...>`, `Error` if it errors, and `Nothing` if nothing is displayed.

``````>>> lambda x: x
______<function <lambda> at ...>
>>> a = lambda x: x
>>> a(5)  # x is the parameter for the lambda function
______5
>>> b = lambda: 3
>>> b()
______3
>>> c = lambda x: lambda: print('123')
>>> c(88)
______<function <lambda> at ...>
>>> c(88)()
______123
>>> d = lambda f: f(4)  # They can have functions as arguments as well.
>>> def square(x):
...     return x * x
>>> d(square)
______16``````
``````>>> t = lambda f: lambda x: f(f(f(x)))
>>> s = lambda x: x + 1
>>> t(s)(0)
______3
>>> bar = lambda y: lambda x: pow(x, y)
>>> bar()(15)
______TypeError: <lambda>() missing 1 required positional argument: 'y'
>>> foo = lambda: 32
>>> foobar = lambda x, y: x // y
>>> a = lambda x: foobar(foo(), bar(4)(x))
>>> a(2)
______2
>>> b = lambda x, y: print('summer')
______# Nothing gets printed by the interpreter
>>> c = b(4, 'dog')
______summer
>>> print(c)
______None``````
``````>>> a = lambda b: b * 2
______# Nothing gets printed by the interpreter
>>> a
______Function
>>> a(a(a(2)))
______16
>>> a(a(a()))
______TypeError: <lambda>() missing 1 required positional argument: 'b'
>>> def d():
...     print(None)
...     print('whoo')
>>> b = d()
______None
whoo
>>> b
______# Nothing gets printed by the interpreter``````
``````>>> x, y, z = 1, 2, 3
>>> a = lambda b: x + y + z
>>> x += y
>>> y -= z
>>> a('b')
______5``````
``````>>> z = 3
>>> e = lambda x: lambda y: lambda: x + y + z
>>> e(0)(1)()
______4``````

### Question 2: WWPD: Higher Order Functions

Use OK to test your knowledge with the following "What Would Python Display?" questions:

``python3 ok -q hof -u``

Hint: Remember for all WWPD questions, input `Function` if you believe the answer is `<function...>`, `Error` if it errors, and `Nothing` if nothing is displayed.

``````>>> def even(f):
...     def odd(x):
...         if x < 0:
...             return f(-x)
...         return f(x)
...     return odd
>>> stevphen = lambda x: x
>>> stewart = even(stevphen)
>>> stewart
______<function ...>
>>> stewart(61)
______61
>>> stewart(-4)
______4``````
``````>>> def cake():
...    print('beets')
...    def pie():
...        print('sweets')
...        return 'cake'
...    return pie
>>> a = cake()
______beets
>>> a
______Function
>>> a()
______sweets
'cake'
>>> x, b = a(), cake
______sweets
>>> def snake(x):
...    if cake == b:
...        x += 3
...        return lambda y: y + x
...    else:
...        return y - x
>>> snake(24)(23)
______50
>>> cake = 2
>>> snake(26)
______Error
>>> y = 50
>>> snake(26)
______24``````

## Coding Practice

### Question 3: Lambdas and Currying

We can transform multiple-argument functions into a chain of single-argument, higher order functions by taking advantage of lambda expressions. This is useful when dealing with functions that take only single-argument functions. We will see some examples of these later on.

Write a function `lambda_curry2` that will curry any two argument function using lambdas. See the doctest or refer to the textbook if you're not sure what this means.

``````def lambda_curry2(func):
"""
Returns a Curried version of a two-argument function FUNC.
8
"""
return ______
return lambda arg1: lambda arg2: func(arg1, arg2)``````

Use OK to test your code:

``python3 ok -q lambda_curry2``

### Question 4: Composite Identity Function

Write a function that takes in two single-argument functions, `f` and `g`, and returns another function that has a single parameter `x`. The returned function should return `True` if `f(g(x))` is equal to `g(f(x))`. You can assume the output of `g(x)` is a valid input for `f` and vice versa. You may use the `compose1` function defined below.

``````def compose1(f, g):
"""Return the composition function which given x, computes f(g(x)).

>>> add_one = lambda x: x + 1        # adds one to x
>>> square = lambda x: x**2
>>> a1 = compose1(square, add_one)   # (x + 1)^2
>>> a1(4)
25
>>> mul_three = lambda x: x * 3      # multiplies 3 to x
>>> a2 = compose1(mul_three, a1)    # ((x + 1)^2) * 3
>>> a2(4)
75
>>> a2(5)
108
"""
return lambda x: f(g(x))

def composite_identity(f, g):
"""
Return a function with one parameter x that returns True if f(g(x)) is
equal to g(f(x)). You can assume the result of g(x) is a valid input for f
and vice versa.

>>> add_one = lambda x: x + 1        # adds one to x
>>> square = lambda x: x**2
>>> b1(0)                            # (0 + 1)^2 == 0^2 + 1
True
>>> b1(4)                            # (4 + 1)^2 != 4^2 + 1
False
"""
def identity(x):
return compose1(f, g)(x) == compose1(g, f)(x)
return identity

# Alternative solution
return lambda x: f(g(x)) == g(f(x))``````

Use OK to test your code:

``python3 ok -q composite_identity``

# Optional Questions

## Environment Diagrams

### Question 5: Lambda the Environment Diagram

Try drawing an environment diagram for the following code and predict what Python will output.

You do not need to submit or unlock this question through Ok. Instead, you can check your work with the Online Python Tutor, but try drawing it yourself first!

``````>>> a = lambda x: x * 2 + 1
>>> def b(b, x):
...     return b(x + a(x))
>>> x = 3
>>> b(a, x)
______21``````

Draw the environment diagram for the following code:

``````n = 9
return lambda k: k + n

There are 3 frames total (including the Global frame). In addition, consider the following questions:

1. In the Global frame, the name `add_ten` points to a function value. What is the intrinsic name of that function value, and what frame is its parent?
2. In frame `f2`, what name is the frame labeled with (`add_ten` or λ)? Which frame is the parent of `f2`?
3. What value is the variable `result` bound to in the Global frame?

You can try out the environment diagram at tutor.cs61a.org.

1. The intrinsic name of the function object that `add_ten` points to is λ (specifically, the lambda whose parameter is `k`). The parent frame of this lambda is `f1`.
2. `f2` is labeled with the name λ the parent frame of `f2` is `f1`, since that is where λ is defined.
3. The variable `result` is bound to 19.

## Recursion

A recursive function is a function that calls itself in its body, either directly or indirectly. Recursive functions have three important components:

1. Base case(s), the simplest possible form of the problem you're trying to solve.
2. Recursive case(s), where the function calls itself with a simpler argument as part of the computation.
3. Using the recursive calls to solve the full problem.

Let's look at the canonical example, `factorial`:

``````def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)``````

We know by its definition that 0! is 1. So we choose `n == 0` as our base case. The recursive step also follows from the definition of factorial, i.e., `n`! = `n` * (`n`-1)!.

The next few questions in lab will have you writing recursive functions. Here are some general tips:

• Consider how you can solve the current problem using the solution to a simpler version of the problem. Remember to trust the recursion: assume that your solution to the simpler problem works correctly without worrying about how.
• Think about what the answer would be in the simplest possible case(s). These will be your base cases - the stopping points for your recursive calls. Make sure to consider the possibility that you're missing base cases (this is a common way recursive solutions fail).
• It may help to write the iterative version first.

Note: The following questions are in lab02_extra.py.

### Question 7: Common Misconception

Find the bug in the following recursive function.

``````def factorial(n):
"""Return n * (n - 1) * (n - 2) * ... * 1.

>>> factorial(5)
120
"""
if n == 0:
return 1
else:
return factorial(n-1)``````

Fix the code in `lab02_extra.py` and run:

``python3 ok -q factorial``

The result of the recursive calls is not combined into the correct solution.

``````def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)``````

### Question 8: Common Misconception

Find the bug with this recursive function.

``````def skip_mul(n):
"""Return the product of n * (n - 2) * (n - 4) * ...

>>> skip_mul(5) # 5 * 3 * 1
15
>>> skip_mul(8) # 8 * 6 * 4 * 2
384
"""
if n == 2:
return 2
else:
return n * skip_mul(n - 2)``````

Fix the code in `lab02_extra.py` and run:

``python3 ok -q skip_mul``

Consider what happens when we choose an odd number for `n`. `skip_mul(3)` will return `3 * skip_mul(1)`. `skip_mul(1)` will return `1 * skip_mul(-1)`. You may see the problem now. Since we are decreasing `n` by two at a time, we've completed missed our base case of `n == 2`, and we will end up recursing indefinitely. We need to add another base case to make sure this doesn't happen.

``````def skip_mul(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return n * skip_mul(n - 2)``````

### Question 9: GCD

The greatest common divisor of two positive integers `a` and `b` is the largest integer which evenly divides both numbers (with no remainder). Euclid, a Greek mathematician in 300 B.C., realized that the greatest common divisor of `a` and `b` is one of the following:

• the smaller value if it evenly divides the larger value, or
• the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value

In other words, if `a` is greater than `b` and `a` is not divisible by `b`, then

``gcd(a, b) = gcd(b, a % b)``

Write the `gcd` function recursively using Euclid's algorithm.

``````def gcd(a, b):
"""Returns the greatest common divisor of a and b.
Should be implemented using recursion.

>>> gcd(34, 19)
1
>>> gcd(39, 91)
13
>>> gcd(20, 30)
10
>>> gcd(40, 40)
40
"""
a, b = max(a, b), min(a, b)
if a % b == 0:
return b
else:
return gcd(b, a % b)

# Iterative solution, if you're curious
def gcd_iter(a, b):
"""Returns the greatest common divisor of a and b, using iteration.

>>> gcd_iter(34, 19)
1
>>> gcd_iter(39, 91)
13
>>> gcd_iter(20, 30)
10
>>> gcd_iter(40, 40)
40
"""
if a < b:
return gcd_iter(b, a)
while a > b and not a % b == 0:
a, b = b, a % b
return b``````

Use OK to test your code:

``python3 ok -q gcd``

## More Coding Practice

### Question 10: Count van Count

Consider the following implementations of `count_factors` and `count_primes`:

``````def count_factors(n):
"""Return the number of positive factors that n has."""
i, count = 1, 0
while i <= n:
if n % i == 0:
count += 1
i += 1
return count

def count_primes(n):
"""Return the number of prime numbers up to and including n."""
i, count = 1, 0
while i <= n:
if is_prime(i):
count += 1
i += 1
return count

def is_prime(n):
return count_factors(n) == 2 # only factors are 1 and n``````

The implementations look quite similar! Generalize this logic by writing a function `count_cond`, which takes in a two-argument predicate function ```condition(n, i)```. `count_cond` returns a one-argument function that counts all the numbers from 1 to `n` that satisfy `condition`.

``````def count_cond(condition):
"""Returns a function with one parameter N that counts all the numbers from
1 to N that satisfy the two-argument predicate function CONDITION.

>>> count_factors = count_cond(lambda n, i: n % i == 0)
>>> count_factors(2)   # 1, 2
2
>>> count_factors(4)   # 1, 2, 4
3
>>> count_factors(12)  # 1, 2, 3, 4, 6, 12
6

>>> is_prime = lambda n, i: count_factors(i) == 2
>>> count_primes = count_cond(is_prime)
>>> count_primes(2)    # 2
1
>>> count_primes(3)    # 2, 3
2
>>> count_primes(4)    # 2, 3
2
>>> count_primes(5)    # 2, 3, 5
3
>>> count_primes(20)   # 2, 3, 5, 7, 11, 13, 17, 19
8
"""
def counter(n):
i, count = 1, 0
while i <= n:
if condition(n, i):
count += 1
i += 1
return count
return counter``````

Use OK to test your code:

``python3 ok -q count_cond``

### Question 11: I Heard You Liked Functions...

Define a function `cycle` that takes in three functions `f1`, `f2`, `f3`, as arguments. `cycle` will return another function that should take in an integer argument `n` and return another function. That final function should take in an argument `x` and cycle through applying `f1`, `f2`, and `f3` to `x`, depending on what `n` was. Here's what the final function should do to `x` for a few values of `n`:

• `n = 0`, return `x`
• `n = 1`, apply `f1` to `x`, or return `f1(x)`
• `n = 2`, apply `f1` to `x` and then `f2` to the result of that, or return `f2(f1(x))`
• `n = 3`, apply `f1` to `x`, `f2` to the result of applying `f1`, and then `f3` to the result of applying `f2`, or `f3(f2(f1(x)))`
• `n = 4`, start the cycle again applying `f1`, then `f2`, then `f3`, then `f1` again, or `f1(f3(f2(f1(x))))`
• And so forth.

Hint: most of the work goes inside the most nested function.

``````def cycle(f1, f2, f3):
"""Returns a function that is itself a higher-order function.

...     return x + 1
>>> def times2(x):
...     return x * 2
...     return x + 3
>>> identity = my_cycle(0)
>>> identity(5)
5
4
>>> do_all_functions = my_cycle(3)
>>> do_all_functions(2)
9
>>> do_more_than_a_cycle = my_cycle(4)
>>> do_more_than_a_cycle(2)
10
>>> do_two_cycles = my_cycle(6)
>>> do_two_cycles(1)
19
"""
def ret_fn(n):
def ret(x):
i = 0
while i < n:
if i % 3 == 0:
x = f1(x)
elif i % 3 == 1:
x = f2(x)
else:
x = f3(x)
i += 1
return x
return ret
return ret_fn``````

Use OK to test your code:

``python3 ok -q cycle``