By the end of this lab, you should have submitted the `lab02`

assignment using the command `submit lab02`

.

**This lab is due by 11:59pm on 07/01/2014.**

Here is a lab02.py starter file for this lab.

By now, you've probably seen a couple of error messages. Even though they might look intimidating, error messages are actually very helpful in debugging code. The following are some common types of errors (found at the bottom of an error message):

**SyntaxError**: Indicates that your code contains improper syntax (e.g. missing a colon after an`if`

statement).**IndentationError**: Indicates that your code contains improper indentation (e.g. inconsistent indentation of a function body)**TypeError**: Indicates an attempted operation on incompatible types (e.g. trying to add a function and an int)**ZeroDivisionError**: Indicates an attempted division by zero.

Using these descriptions of error messages, you should be able to get
a better idea of what went wrong with your code. **If you run into
error messages, try to identify the problem before asking for
help.** You can often Google unknown error messages to see what
similar mistakes others have made to help you debug your own code.

For example:

```
>>> square(3, 3)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: square() takes 1 positional argument but 2 were given
```

Notice that the last line of the error message tells us exactly what
we did wrong - we gave `square`

2 arguments when it only takes in 1
argument. In general, the last line is the most helpful.

Here's a link to a helpful Debugging Guide written by Albert Wu. Pay particular attention to the section called "Error Types" (the other sections are fairly involved but will be useful in the larger projects).

If you haven't found this gem already, tutor.composingprograms.com has a great visualization tool for environment diagrams. Post in your python code and it will generate an environment diagram you can walk through step-by-step! Use it to help you check your answers!

Try drawing environment diagrams for the following examples and predicting what Python will output:

```
>>> def square(x):
... return x * x
>>> def double(x):
... return x + x
>>> a = square(double(4))
>>> a
______64
```

```
>>> x, y = 4, 3
>>> def reassign(arg1, arg2):
... x = arg1
... y = arg2
>>> reassign(5, 6)
>>> x
______4
>>> y
______3
```

```
>>> def f(x):
... f(x)
>>> print, f = f, print
>>> a = f(4)
______4
>>> a
______# Nothing shows up, because a = None
>>> b = print(4)
______4
>>> b
______# Nothing shows up, because b = None
```

```
>>> def adder_maker(x):
... def adder(y):
... return x + y
... return adder
>>> add3 = adder_maker(3)
>>> add3(4)
______7
>>> sub5 = adder_maker(-5)
>>> sub5(6)
______1
>>> sub5(10) == add3(2)
______True
```

Now we'll see where environment diagrams come in **really** handy:
Lambdas and Higher Order Functions.

```
>>> a = lambda: 5
>>> a()
______5
>>> a(5)
______TypeError: <lambda>() takes 0 positional arguments but 1 was given
>>> a()()
______TypeError: 'int' object is not callable
>>> b = lambda: lambda x: 3
>>> b()(15)
______3
```

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

, `f2`

, `f3`

, `f4`

, and `f5`

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 ***"
def f2():
"""
>>> f2()()
3
"""
"*** YOUR CODE HERE ***"
def f3():
"""
>>> f3()(3)
3
"""
"*** YOUR CODE HERE ***"
def f4():
"""
>>> f4()()()
3
"""
"*** YOUR CODE HERE ***"
def f5():
"""
>>> f5()()(3)()
3
"""
"*** YOUR CODE HERE ***"
```

```
def f1():
return 3
def f2():
return lambda: 3
def f3():
return lambda x: x
def f4():
return lambda: lambda: 3
def f5():
return lambda: lambda x: lambda: x
```

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

```
# Q1
a = lambda x : x * 2 + 1
def b(x):
return x * y
y = 3
b(y)
_________
def c(x):
y = a(x)
return b(x) + a(x+y)
c(y)
_________
# Q2: 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)
_________
g = lambda x: x * x
f(3)
_________
```

Please use the online environment diagram drawer, linked at the bottom of the class webpage.

- 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!

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(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(16)
______second
39
```

```
>>> def foo(x):
... def bar(y):
... return x + y
... return bar
>>> boom = foo(23)
>>> boom(42)
______65
>>> foo(6)(7)
______13
>>> func = boom
>>> func is boom
______True
>>> func = foo(23)
>>> func is boom
______False
```

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

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 make_buzzer(n):
def buzz(m):
i = 0
while i < m:
if i % n == 0:
print('Buzz!')
else:
print(i)
i += 1
return buzz
```

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 cycle(f1, f2, f3):
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
```

Write a function that takes in a linked list `lst`

of numbers and returns
the sum of the elements in the linked list.

```
def sum_linked_list(lst, term):
""" Applies a function TERM to each number in LST and returns the sum
of the resulting values
>>> square = lambda x: x*x
>>> double = lambda y: 2*y
>>> lst1 = link(1, link(2, link(3, link(4, empty))))
>>> sum_linked_list(lst1, square)
30
>>> lst2 = link(3, link(5, link(4, link(10, empty))))
>>> sum_linked_list(lst2, double)
44
"""
"*** YOUR CODE HERE ***"
```

Recursive solution:

```
def sum_linked_list(lst, term):
if lst == empty:
return 0
return term(first(lst)) + sum_linked_list(rest(lst), term)
```

Iterative solution:

```
def sum_linked_list(lst, term):
sum = 0
while lst != empty:
sum += term(first(lst))
lst = rest(lst)
return sum
```

If you have extra time, go back to the environment diagram problems in Questions 1 and 2 to get some extra practice.