# Lab 4: Higher Order Functions

*Due at 11:59:59 pm on 10/01/2019.*

## Starter Files

Download lab04.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. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

- To receive full credit for this lab, all questions must be attempted.

When you are ready to submit, run `ok`

with the `--submit`

option:

`python3 ok --submit`

After submitting, `ok`

will display a submission URL, with which you can view your submission on okpy.org.

In the previous lab, you went through a crash course going through the wonders of list comprehension, conditionals and iteration! In this week’s lab, we will begin to explore the world of higher order functions!

## Environment Diagrams

Environment diagrams are one of the best learning tools for understanding higher order functions because you're able to keep track of all the different names, function objects, and arguments to functions. We highly recommend drawing environment diagrams or using Python tutor if you get stuck doing the WWPD problems below. For examples of what environment diagrams should look like, try running some code in Python tutor. Here are the rules:

### Assignment Statements

- Evaluate the expression on the right hand side of the
`=`

sign. - If the name found on the left hand side of the
`=`

doesn't already exist in the current frame, write it in. If it does, erase the current binding. Bind the*value*obtained in step 1 to this name.

If there is more than one name/expression in the statement, evaluate all the expressions first from left to right before making any bindings.

### def Statements

- Draw the function object with its intrinsic name, formal parameters, and parent frame. A function's parent frame is the frame in which the function was defined.
- If the intrinsic name of the function doesn't already exist in the current frame, write it in. If it does, erase the current binding. Bind the newly created function object to this name.

### Call expressions

Note: you do not have to go through this process for a built-in Python function like

`max`

or

- Evaluate the operator, whose value should be a function.
- Evaluate the operands left to right.
- Open a new frame. Label it with the sequential frame number, the intrinsic name of the function, and its parent.
- Bind the formal parameters of the function to the arguments whose values you found in step 2.
- Execute the body of the function in the new environment.

## Functions as Arguments (Funargs)

So far we have used several types of data - ints, floats, booleans,
strings, lists, tuples, and numpy.arrays. We perform operations on them by
constructing expressions; we assign them to variables; we pass them to functions
and return them as results. So what about functions themselves? So far we have
*called them*, that is we applied them to arguments. Sometimes we *compose* them -
just like in math; apply a function to the result of applying a function. You
did that several times above.

In modern programming languages like Python, functions are *first class citizens*;
we can pass them around and put them in data structures. Take a look at the following
and try it out for various functions that you have available in the `.py`

file for this
lab.

```
>>> square(square(3))
81
>>> square
<function square at 0x102033d90>
>>> x = square
>>> x(3)
9
>>> x(x(2))
16
>>>
```

## Introduction to 'Map'

Higher order functions fit into a domain of programming known as "functional" or "functional form" programming, centered around this idea of passing and returning functions as parameters and arguments. In class, you learned the command `map`

that is a fundamental example of higher order functions.

Let's take a closer look at how `map`

works. At its core, `map`

applies a function to all items in an input list. It takes in a function as the first parameter and a series of inputs as the second parameter.

`map(function_to_apply, list_of_inputs)`

A potentially easier way to think about `map`

is to draw an equivalent with a list comprehension! Given the `func`

(function to apply) and `inputs`

(list of inputs), a map is similar to this:

`[func(x) for x in inputs]`

Keep in mind that the `map`

function actually returns a `map`

object, not a list. We need to convert this object to a `list`

by passing it into the `list()`

function.

Let's do a Python Tutor example to understand how map works.

Open Python Tutor in a new tab.

This code should already be there:

```
INCR = 2
def inc(x):
return x+INCR
def mymap(fun, seq):
return [fun(x) for x in seq]
result = mymap(inc, [5, 6, 7])
print(result)
```

So what's happening here? In the first 3 lines, we're defining a function `inc`

which increments an input `x`

by a certain amount, `INCR`

.

Notice that `INCR`

is defined once in the Global frame. This is a nice review of how Python resolves references when there are both local and global variables. When the `inc`

method executes, python needs to find the value `INCR`

. Since the `INCR`

variable isn't declared locally, within the `inc`

function, Python will look at the parent frame, the frame in which `inc`

was declared, for the value of `INCR`

. In this case, since the `inc`

function was declared in the Global frame, the global `INC`

variable value will be used.

The second function, `mymap`

, is an example of how map works in the form of a list comprehension! Notice that `mymap`

takes in a function as its first argument and a sequence as its second. Just like `map`

, this list comprehension runs each element of `seq`

through the `fun`

method.

As you run through the program in Python Tutor, notice how the list comprehension in `mymap`

will repeatedly call the `inc`

function. The functional anatomy of how `map`

works is exactly encapsulated by the `mymap`

function.

### Question 1: Converter

Given a list of temperatures in Celsius format, convert each temperature value in the list from Celsius to Fahrenheit.A couple tips:

- Make sure to use the
`map`

keyword for this solution! - The temperature converter function will be passed in as a method, so there is no need for you to write it again!

If you're feeling stuck, think about the parameters of `map`

. This is meant to be a simple problem that provides hands-on experience of understanding what `map`

does.

```
def converter(temperatures, convert):
"""Returns a sequence that converts each Celsius temperature to Fahrenheit
>>> def convert(x):
... return 9.0*x/5.0 + 32
>>> temperatures = [10, 20, 30, 40, 50]
>>> converter(temperatures, convert)
[50.0, 68.0, 86.0, 104.0, 122.0]
"""
"*** YOUR CODE HERE ***"
return list(map(convert, temperatures))
```

Use OK to test your code:

`python3 ok -q converter`

## Introduction to 'Filter'

The `filter`

keyword is similar in nature to `map`

with a very important distinction. In `map`

, the function we pass in is being applied to every item in our sequence. In `filter`

, the function we pass in *filters* the elements, only leaving the elements for which the function returns true. For example, if I wanted to remove all negative numbers from a list, I could use the `filter`

function to identify values that are greater than or equal to 0, and filter out the rest.

```
def isPositive(number):
return number >= 0
numbers = [-1, 1, -2, 2, -3, 3, -4, 4]
positive_nums = list(filter(isPositive, numbers))
```

Again, similar to `map`

, the output of the `filter`

function is a `filter`

object, not a list, so you need to call `list()`

. The equivalent for filter in the form of a list comprehension would look something along the lines of this:

`positive_nums = [number for number in numbers if isPositive(number)]`

## Introduction to 'Reduce'

`Reduce`

takes in three different parameters: A function, a sequence, and an identity. The function and sequence are the same parameters that we saw in `map`

and `filter`

. The identity can be thought of as the container where you are going to store all of your results. In the above case, the identity would be the `product`

variable.

`Reduce`

is very useful for performing computations on lists that involve every element in the list. Computations are performed in a rolling fashion, where the function acts upon each element one at a time.

Let's say I wanted to calculate the product of the square roots of a list of numbers. The non-`reduce`

version of this code would look something along the lines of this:

```
product = 1
numbers = [4, 9, 16, 25, 36]
for num in numbers:
product = product * num**.5
```

Here's the `reduce`

version

```
multiplicative_identity = 1
nums = [4, 9, 16, 25, 36]
def sqrtProd(x, y):
return x * y ** .5
reduce(sqrtProd, nums, multiplicative_identity)
```

### Question 2: reduce

Write the higher order function `reduce`

which takes

- reducer - a two-argument function that reduces elements to a single value
- s - a sequence of values
- base - the starting value in the reduction. This is usually the identity of the reducer

If you're feeling stuck, think about the parameters of `reduce`

. This is meant to be a simple problem that provides hands-on experience of understanding what `reduce`

does.

```
from operator import add, mul
def reduce(reducer, s, base):
"""Reduce a sequence under a two-argument function starting from a base value.
>>> def add(x, y):
... return x + y
>>> def mul(x, y):
... return x*y
>>> reduce(add, [1,2,3,4], 0)
10
>>> reduce(mul, [1,2,3,4], 0)
0
>>> reduce(mul, [1,2,3,4], 1)
24
"""
"*** YOUR CODE HERE ***"
for x in s:
base = reducer(base, x)
return base
```

Use OK to test your code:

`python3 ok -q reduce`

## Higher Order Functions

Thus far, in Python Tutor, we’ve visualized Python programs in the form of environment diagrams that display which variables are tied to which values within different frames. However, as we noted when introducing Python, values are not necessarily just primitive expressions or types like float, string, integer, and boolean.

In a nutshell, a higher order function is any function that takes a function as a parameter or provides a function has a return value. We will be exploring many applications of higher order functions.

Let's think about a more practical use of higher order functions. Pretend you’re a math teacher, and you want to teach your students how coefficients affect the shape of a parabola.

Open Python Tutor in a new tab

Paste this code into the interpreter:

```
def define_parabola(a, b, c):
def parabola(x):
return a*(x**2) + b*x + c
return parabola
parabola = define_parabola(-2, 3, -4)
y1 = parabola(1)
y2 = parabola(10)
print(y1, y2)
```

Now step through the code. In the `define_parabola`

function, the coefficient values of 'a', 'b', and 'c' are taken in, and in return, a parabolic function with those coefficient values is returned.

As you step through the second half of the code, notice how the value of `parabola`

points at a function object! The `define_parabola`

higher order nature comes from the fact that its return value is a function.

Another thing noting is where the pointer moves after the `parabola`

function is called. Notice that the pointer goes to line 2, where `parabola`

was originally defined. In a nutshell, this example is meant to show how a closure is returned from the `define_parabola`

function.

### Question 3: Piecewise

Implement `piecewise`

, which takes two one-argument functions, `f`

and `g`

,
along with a number `b`

. It returns a new function that takes a number `x`

and
returns either `f(x)`

if `x`

is less than `b`

, or `g(x)`

if `x`

is greater than
or equal to `b`

.

```
def piecewise(f, g, b):
"""Returns the piecewise function h where:
h(x) = f(x) if x < b,
g(x) otherwise
>>> def negate(x):
... return -x
>>> def identity(x):
... return x
>>> abs_value = piecewise(negate, identity, 0)
>>> abs_value(6)
6
>>> abs_value(-1)
1
"""
"*** YOUR CODE HERE ***"
def h(x):
if x < b:
return f(x)
return g(x)
return h
```

Use OK to test your code:

`python3 ok -q piecewise`

### Question 4: Intersect

Two functions intersect at an argument `x`

if they return equal values.
Implement `intersects`

, which takes a one-argument functions `f`

and a value
`x`

. It returns a function that takes another function `g`

and returns whether
`f`

and `g`

intersect at `x`

.

```
def intersects(f, x):
"""Returns a function that returns whether f intersects g at x.
>>> def square(x):
... return x * x
>>> def triple(x):
... return x * 3
>>> def increment(x):
... return x + 1
>>> def identity(x):
... return x
>>> at_three = intersects(square, 3)
>>> at_three(triple) # triple(3) == square(3)
True
>>> at_three(increment)
False
>>> at_one = intersects(identity, 1)
>>> at_one(square)
True
>>> at_one(triple)
False
"""
"*** YOUR CODE HERE ***"
def at_x(g):
return f(x) == g(x)
return at_x
```

Use OK to test your code:

`python3 ok -q intersects`