Solutions: You can find the file with solutions for all questions here.

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!

Functions as Arguments (Funargs)

So far we have used several type of data - ints, floats, booleans, strings, lists, tuples, and numpy.arrays. We perform operations on them in 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, by default. Consequently, in order to make the result actionable, it's important for us to adjust the return value of map to a list by passing the map object into the list() function.

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

Open Python Tutor in a new tab.

Paste this code into the interpreter:

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, remember that since the INCR variable isn't declared locally within the inc function, the Python compiler 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 apply.

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: Data Cleaning

Given a list of float numbers, round each number in the list down to the nearest tens place. (i.e. 17 -> 10, 23 -> 20)

We recommend writing a nested function that performs the rounding, then use map to perform the rounding on each element of the list.

You can assume that none of the values in the problem's tests will be floats or negative.

def data_clean(a):
    """Write a function that rounds each element of the list down to the nearest tens place.

    >>> a = [12, 23, 34]
    >>> data_clean(a)
    [10, 20, 30]
    >>> b = [238, 193, 928]
    >>> data_clean(b)
    [230, 190, 920]
    >>> c = [10, 20, 30]
    >>> data_clean(c)
    [10, 20, 30]
    >>> d = [9, 9, 9]
    >>> data_clean(d)
    [0, 0, 0]
    """
    "*** YOUR CODE HERE ***"
    return _____
    def truncateNumber(x):
        return x - (x%10)
    return list(map(truncateNumber, a))

Toggle Solution

Use OK to test your code:

python3 ok -q data_clean --local

Introduction to 'Filter'

The filter keyword is similar in nature to the 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 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 satisfy the greater than or equal to 0 criterion.

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 casting is required. In addition, continuing off the above example, the equivalent for filter in the form of a list comprehension would look something along the lines of this:

positive_nums = [x for x in numbers if isPositive(numbers)]

Introduction to 'Reduce'

One of the most useful functional functions we'll encounter in this class is the reduce keyword. Before diving into the inner workings, it's best to start off with a iterative equivalent that will helps us better appreciate the benefits of using reduce.

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 * sqrt(num)

Reduce can be broken down into three different parameters: A function, a sequence, and an identity. The function and sequence are the same parameters as before. The identity can be thought of as the value through which function outputs are aggregated. 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.

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 ***"
    return _____
    result = base
    for x in s:
        result = reducer(result, x)
    return result

Toggle Solution

Use OK to test your code:

python3 ok -q reduce --local

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

PythonTutor

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 ***"
    return _____
    def h(x):
        if x < b:
            return f(x)
        return g(x)
    return h

Toggle Solution

Use OK to test your code:

python3 ok -q piecewise --local

Question 4: Flight of the Bumblebee

Write a function that takes in a number n and returns a function that takes in a number m which will print all numbers from 0 to m - 1 (including 0 but excluding m) 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 ***"
    return _____
    def buzz(m):
        i = 0
        while i < m:
            if i % n == 0:
                print('Buzz!')
            else:
                print(i)
            i += 1
    return buzz

Toggle Solution

Use OK to test your code:

python3 ok -q make_buzzer --local

Question 5: 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 ***"
    return _____
    def at_x(g):
        return f(x) == g(x)
    return at_x

Toggle Solution

Use OK to test your code:

python3 ok -q intersects --local

Tools Installation

Congrats on finishing the lab this week! Before you leave, we're going to introduce two new Python libraries that we'd like to add to your development toolkit this week. These two kits are the "datascience" module developed locally here at Berkeley for Data 8, and Anaconda, one of the most popular data science platforms today for Python developers!

To install the above libraries, please do the following:

1. 'datascience' module: Please open a new Terminal / Git-bash locally on your computer. Then, type in pip3 install datascience and click enter. If that does not work, try pip install datascience.

pip3 is a package management system for Python. To put it simply, it helps you install and manage software packages written in Python. Your machine should come pre-installed with pip3 (or pip). After running the above line, you'll see some output indication that the datascience module and its related dependencies are being installed.

The module installed successfully if the last line of the output looks something along the lines of Successfully installed coveralls-0.5 datascience-0.10.6.

The datascience module was written by Professors John Denero and David Culler (your instructor!) along with the help of several undergraduate students. It was originally written for the Data 8 class as a friendly introduction to analytical tools used by data science developers. To learn more about this library, you can follow this link.

1. Anaconda: Please visit the Anaconda downloads link. From there, follow the online directions and install the corresponding version of Anaconda for your operating system. Make sure to install Python version 3.6.

Anaconda is essentially the industry standard when it comes to developing data science and machine learning related applications using Python. The Anaconda installation comes chock full with useful data science libraries such as numpy and pandas that will become increasingly useful as you pursue and study data science. Installing Anaconda will equip you with the appropriate tools that we'll be using later on in this course.