*Due at 11:59pm on 02/04/2015.*

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.

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.

- To receive credit for this lab, you must complete Questions 2, 4, 6, 7, and 8 in lab03.py and submit through OK.
- Questions 1, 3 (What Would Python Print?), and 5 (Environment Diagrams) are designed to help introduce concepts and test your understanding.
- Questions 9, 10, 11, 12, and 13 are optional
**extra practice**(all except 11 are in lab03_extra.py). It is recommended that you complete these problems on your own time.

- Higher Order Functions
- Lambdas
- Question 3: What would Python print?
- Question 4: Make your own lambdas
- Question 5: Environment Diagrams with Lambdas
- Recursion
- Extra Questions

Now we'll see where environment diagrams come in **really** handy:
When dealing with lambda expressions in addition to other higher-order functions.

Higher order functions are functions that take a function as an input, and/or output a function. We will be exploring many applications of higher order functions.

```
>>> def square(x):
... return x*x
...
>>> def neg(f, x):
... return -f(x)
...
>>> neg(square, 4)
______-16
```

```
>>> def even(f):
... def odd(x):
... if x < 0:
... return f(-x)
... return f(x)
... return odd
...
>>> def identity(x):
... return x
...
>>> triangle = even(identity)
>>> triangle
______<function ...>
>>> triangle(61)
______61
>>> triangle(-4)
______4
```

```
>>> def first(x):
... x += 8
... def second(y):
... print('second')
... return x + y
... print('first')
... return second
...
>>> f = first(15)
______first
>>> f
______<function ...>
>>> f(16)
______second
39
```

Write a function that takes in a number `n`

and returns a function
that takes in a number `range`

which will print all numbers from `0`

to `range`

(including `0`

but excluding `range`

) but print `Buzz!`

instead for all the numbers that are divisible by `n`

.

```
def make_buzzer(n):
""" Returns a function that prints numbers in a specified
range except those divisible by n.
>>> i_hate_fives = make_buzzer(5)
>>> i_hate_fives(10)
Buzz!
1
2
3
4
Buzz!
6
7
8
9
"""
"*** YOUR CODE HERE ***"
def buzz(m):
i = 0
while i < m:
if i % n == 0:
print('Buzz!')
else:
print(i)
i += 1
return buzz
```

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

`lambda <parameters>: <return value>`

One difference between using the `def`

keyword and `lambda`

expressions is that `def`

is a *statement*, while lambda is an
*expression*. Evaluating a `def`

statement will have a side effect;
namely, it creates a new function binding in the current environment.
On the other hand, evaluating a `lambda`

expression will not change the
environment unless we do something with this expression. For instance,
we could assign it to a variable or pass it in as a function argument.

```
>>> a = lambda: 5
>>> a()
______5
>>> a(5)
______TypeError: <lambda>() takes 0 positional arguments but 1 was given
>>> a()()
______TypeError: 'int' object is not callable
>>> lambda x: x # Can we access this function?
______<function <lambda> at ...>
>>> b = lambda: lambda x: 3
>>> b()(15)
______3
>>> c = lambda x, y: x + y
>>> c(4, 5)
______9
>>> d = lambda x: c(a(), b()(x))
>>> d(2)
______8
>>> b = lambda: lambda x: x
>>> d(2)
______7
>>> e = lambda x: lambda y: x * y
>>> e(3)
______<function ...>
>>> e(3)(3)
______9
>>> f = e(2)
>>> f(5)
______10
>>> f(6)
______12
>>> g = lambda: print(1) # When is the body of this function run?
______# Nothing gets printed by the interpreter
>>> h = g()
______1
>>> print(h)
______None
```

For each of the following expressions, write functions `f1`

, `f2`

,
`f3`

, and `f4`

such that the evaluation of each expression
succeeds, without causing an error. Be sure to use lambdas in your
function definition instead of nested `def`

statements. Each function
should have a one line solution.

```
def f1():
"""
>>> f1()
3
"""
"*** YOUR CODE HERE ***"
return 3
def f2():
"""
>>> f2()()
3
"""
"*** YOUR CODE HERE ***"
return lambda: 3
def f3():
"""
>>> f3()(3)
3
"""
"*** YOUR CODE HERE ***"
return lambda x: x
def f4():
"""
>>> f4()()(3)()
3
"""
"*** YOUR CODE HERE ***"
return lambda: lambda x: lambda: x
```

Try drawing environment diagrams for the following code and predicting what Python will output.

You can check your work with the Online Python Tutor. Please try drawing it yourself first!

```
>>> # Part 1
>>> a = lambda x : x * 2 + 1
>>> def b(x):
... return x * y
...
>>> y = 3
>>> b(y)
______9
>>> def c(x):
... y = a(x)
... return b(x) + a(x+y)
...
>>> c(y)
______30
>>> # Part 2: This one is pretty tough. A carefully drawn environment
>>> # diagram will be really useful.
>>> g = lambda x: x + 3
>>> def wow(f):
... def boom(g):
... return f(g)
... return boom
...
>>> f = wow(g)
>>> f(2)
______5
>>> g = lambda x: x * x
>>> f(3)
______6
```

Please use Python Tutor, the online environment diagram drawer.

- 9 (for the first blank), 30 (for the second blank).
- 5 (for the first blank), 6 (for the second blank). Notice that the
line
`g = lambda x: x * x`

doesn't change what f(3) does!

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

- Base case(s), where the function directly computes an answer without calling itself. Usually the base case deals with the simplest possible form of the problem you're trying to solve.
- Recursive case(s), where the function calls itself with a simpler argument as part of the computation.

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

Write a function `sum`

that takes a single argument `n`

and computes the sum of all integers between 0 and `n`

inclusive.
Assume `n`

is non-negative.

```
def sum(n):
"""Computes the sum of all integers between 1 and n, inclusive.
Assume n is positive.
>>> sum(1)
1
>>> sum(5) # 1 + 2 + 3 + 4 + 5
15
"""
"*** YOUR CODE HERE ***"
if n == 1:
return 1
return n + sum(n - 1)
```

The following examples of recursive functions show some examples of common recursion mistakes. Fix them so that they work as intended.

```
def sum_every_other_number(n):
"""Return the sum of every other natural number
up to n, inclusive.
>>> sum_every_other_number(8)
20
>>> sum_every_other_number(9)
25
"""
if n == 0:
return 0
else:
return n + sum_every_other_number(n - 2)
```

Consider what happens when we choose an odd number for `n`

.
`sum_every_other_number(3)`

will return ```
3 +
sum_every_other_number(1)
```

. `sum_every_other_number(1)`

will return
`1 + sum_every_other_number(-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 == 0`

, and we will end up recursing indefinitely. We need to
add another base case to make sure this doesn't happen.

```
def sum_every_other_number(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return n + sum_every_other_number(n - 2)
```

```
def fibonacci(n):
"""Return the nth fibonacci number.
>>> fibonacci(11)
89
"""
if n == 0:
return 0
elif n == 1:
return 1
else:
fibonacci(n - 1) + fibonacci(n - 2)
```

The result of the recursive calls is not returned.

```
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
```

For the `hailstone`

function from homework 1, you pick a positive
integer `n`

as the start. If `n`

is even, divide it by 2. If `n`

is
odd, multiply it by 3 and add 1. Repeat this process until `n`

is 1.
Write a recursive version of hailstone that prints out the values of
the sequence and returns the number of steps.

```
def hailstone(n):
"""Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.
>>> a = hailstone(10)
10
5
16
8
4
2
1
>>> a
7
"""
"*** YOUR CODE HERE ***"
print(n)
if n == 1:
return 1
elif n % 2 == 0:
return 1 + hailstone(n // 2)
else:
return 1 + hailstone(3 * n + 1)
```

Questions in this section are not required for submission. However, we encourage you to try them out on your own time for extra practice.

**This question is extremely challenging.** Use it to test if you have really
mastered the material!

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 the 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
>>> def add1(x):
... return x + 1
>>> def times2(x):
... return x * 2
>>> def add3(x):
... return x + 3
>>> my_cycle = cycle(add1, times2, add3)
>>> identity = my_cycle(0)
>>> identity(5)
5
>>> add_one_then_double = my_cycle(2)
>>> add_one_then_double(1)
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
"""
"*** YOUR CODE HERE ***"
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
```

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 if you're not sure what this
means.

```
def lambda_curry2(func):
"""
Returns a Curried version of a two argument function func.
>>> from operator import add
>>> x = lambda_curry2(add)
>>> y = x(3)
>>> y(5)
8
"""
"*** YOUR CODE HERE ***"
return ______
return lambda arg1: lambda arg2: func(arg1, arg2)
```

Fill in the blanks as to what Python would do here. Please try this problem first with an environment diagram, and then again without an environment diagram.

```
>>> def troy():
... abed = 0
... while abed < 10:
... britta = lambda: abed
... abed += 1
... abed = 20
... return britta
...
>>> jeff = troy()
>>> shirley = lambda : jeff
>>> pierce = shirley()
>>> pierce()
______20
```

Consider an insect in an *M* by *N* grid. The insect starts at the
bottom left corner, *(0, 0)*, and wants to end up at the top right
corner, *(M-1, N-1)*. The insect is only capable of moving right or
up. Write a function `paths`

that takes a grid length and width
and returns the number of different paths the insect can take from the
start to the goal. (There is a closed-form solution to this problem,
but try to answer it procedurally using recursion.)

For example, the 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 diferent paths (only 3 are shown above).

```
def paths(m, n):
"""Return the number of paths from one corner of an
M by N grid to the opposite corner.
>>> paths(2, 2)
2
>>> paths(5, 7)
210
>>> paths(117, 1)
1
>>> paths(1, 157)
1
"""
"*** YOUR CODE HERE ***"
if m == 1 or n == 1:
return 1
return paths(m - 1, n) + paths(m, n - 1)
```

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
"""
"*** YOUR CODE HERE ***"
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
```