Due at 11:59pm on 02/04/2015.
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.
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 but excluding
range) but print
instead for all the numbers that are divisible by
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
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
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 3def f2(): """ >>> f2()() 3 """"*** YOUR CODE HERE ***"return lambda: 3def f3(): """ >>> f3()(3) 3 """"*** YOUR CODE HERE ***"return lambda x: xdef 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
g = lambda x: x * xdoesn'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:
Let's look at the canonical example,
def factorial(n): if n == 0: return 1 return n * factorial(n - 1)
We know by its definition that
1. So we choose
n = 0 as our
base case. The recursive step also follows from the definition of
n! = n * (n-1)!.
The next few questions in lab will have you writing recursive functions. Here are some general tips:
Write a function
sum that takes a single argument
and computes the sum of all integers between 0 and
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
sum_every_other_number(3) will return
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
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)
hailstone function from homework 1, you pick a positive
n as the start. If
n is even, divide it by 2. If
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
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
x, depending on what
was. Here's the what the final function should do to
x for a few
n = 0, return
n = 1, apply
x, or return
n = 2, apply
f2to the result of that, or return
n = 3, apply
f2to the result of applying
f1, and then
f3to the result of applying
n = 4, start the cycle again applying
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
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
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
b is one of the following:
In other words, if
a is greater than
a is not divisible by
gcd(a, b) == gcd(b, a % b)
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