Due at 11:59:59 pm on 02/14/2020.

Starter Files

Download lab02.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.

Introduction

In the last lab, you learned some basic expressions and wrote some python code. In this lab, we will introduce lists and explore higher order functions (HOFs).

Lists

In Data 8, you have recently started working with Tables. Tables are an extremely useful and powerful data type. In CS88 we will work with other data types. Python provides several important built-in data types that we can build from. So far, you have met numberical data types (ints, floats, and booleans) and one sequence type (strings). Lists, tuples, and dictionaries are other sequence data types in Python. Here, we will take a closer look at lists. A list can contain a sequence of values of any type.

You can create a list just by placing the values, separated by commas, within square brackets. Here are some examples. As you will see in one of the examples, lists can contain other lists.

>>> [1,2,3]
[1, 2, 3]
>>> ["frog", 3, 3.1415]
['frog', 3, 3.1415]
>>> [True, [1, 2], 42]
[True, [1, 2], 42]

Open up your python interpreter and create some lists of your own.
You learned last week that what really makes a data type useful is the operations that you can perform on it. What can you do with lists?

>>> x = [1,2,3]    # assign them to variables
>>> len(x)         # get their length, i.e., the number of elements in them
3
>>> x + [4,5]      # + is concatenation
[1, 2, 3, 4, 5]
>>> [1,2] * 3        # * is replication
[1, 2, 1, 2, 1, 2]
>>> len([1,2] * 3)
6
>>> [1,2] * [3,4]    # what's this?
TypeError: can't multiply sequence by non-int of type 'list'

The in operator is very useful when working with lists. It operates on the entire list and produces a boolean that answers the question, "Is this item in the list?".

>>> 2 in [1,2,3]
True
>>> "frog" in [1,2,3]
False
>>> [1,2] in [1,2,3]
False
>>> [1,2] in [[1,2],3]
True

Question 1: Second Max

Write a function that finds the second highest number in a list of positive integers. You can assume that the list always has at least two integers.

def second_max(lst):
    """ 
    Return the second highest number in a list of positive integers.

    >>> second_max([3, 2, 1, 0])
    2
    >>> second_max([2, 3, 3, 4, 5, 6, 7, 2, 3])
    6
    >>> second_max([1, 5, 5, 5, 1])
    5
    >>> second_max([5, 6, 6, 7, 1])
    6
    >>> second_max([5, 6, 7, 7, 1])
    7
    """

    "*** YOUR CODE HERE ***"
    highest = 0
    second_highest = 0
    for num in lst:
        if num >= highest:
            second_highest = highest
            highest = num
        elif num < highest and num > second_highest:
            second_highest = num
    return second_highest

Use OK to test your code:

python3 ok -q second_max

List Comprehensions

Now that we can create lists, assign variables, write expressions, and define functions, we can compose these concepts to do lots of interesting things. Python's list comprehensions open a beautiful world of data-centric programming.
The comprehension is in brackets, just like a list, but rather than a static sequence of literals, it is a dynamically computed list.

>>> somelist = [1, 2, 9, -1, 0]
>>> [x+1 for x in somelist]
[2, 3, 10, 0, 1]
>>> [x*x for x in somelist]
[1, 4, 81, 1, 0]

In general, the expression just inside the [ is evaluated for each element in the list, using the variable between the for and the in to name each element in succession. The result is the transformed list.

>>> def square(x):
...     return x*x
...
>>> def squares(s):
...     return [square(x) for x in s]
...
>>> squares([0,1,2,4])
[0, 1, 4, 16]

>>>x, y = 2, 3
>>> x+y
5
>>> [x+y for x,y in [[1,2], [2,3], [3,4]]
[3, 5, 7]

This is a powerful design pattern, called map, that you will use in often in analyzing data. It maps, or transforms, one data structure into another under some expression, often by applying a function to each of the elements.

Do you remember the Table.apply( ) function from Data 8? The Table.apply function is another great example of the map design pattern as it applies a "transformation" or a function to a row or column.

Sometimes you need a sequence to get started, and Python provides handy tools for that. One of them is range.

>>> [x*x for x in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

You can review range in Section 2.3 of Composing Programs.

Question 2: Perfect squares

Implement the function squares, which takes in a list of positive integers, and returns a new list which contains only elements of the original list that are perfect squares. Use a list comprehension.

from math import sqrt

def is_square(n):
    return float(sqrt(n)) == int(sqrt(n))

def squares(seq):
    """Returns a new list containing elements of the original list that are
    perfect squares.

    >>> seq = [49, 8, 2, 1, 102]
    >>> squares(seq)
    [49, 1]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """
    "*** YOUR CODE HERE ***"
    
    return [n for n in seq if is_square(n)]

Use OK to test your code:

python3 ok -q squares

Question 3: Perfect Pairs

Implement the function pairs, which takes in an integer n, and returns a new list of lists which contains pairs of numbers from 1 to n. Use a list comprehension.

def pairs(n):
    """Returns a new list containing two element lists from values 1 to n
    >>> pairs(1)
    [[1, 1]]
    >>> x = pairs(2)
    >>> x
    [[1, 1], [2, 2]]
    >>> pairs(5)
    [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]]
    >>> pairs(-1)
    []
    """
    "*** YOUR CODE HERE ***"
    
    return [[i, i] for i in range(1, n + 1)]

Use OK to test your code:

python3 ok -q pairs

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 4: 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 5: 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

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 6: 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 7: 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

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Extra Credit Practice Open in a new window

These questions are new this semester. They're a mix of Parsons Problems, Code Tracing questions, and Code Writing questions.

Confused about how to use the tool? Check out https://codestyle.herokuapp.com/cs88-lab01 for some problems designed to demonstrate how to solve these types of problems.

These cover some similar material to lab, so can be helpful to further review or try to learn the material. Unlike lab and homework, after you've worked for long enough and tested your code enough times on any of these questions, you'll have the option to view an instructor solution. You'll unlock each question one at a time, either by correctly answering the previous question or by viewing an instructor solution.

Starting from lab 2 onward, each set of questions are worth half (0.5) a point per lab, for a total opportunity of 4-5 points throughout the semester.

Use OK to test your code:

python3 ok -q extra_credit

More FUN with FUNctions (Optional)

The questions in lab02_extra.py are optional problems for you to solve if you want more practice with functions. Be warned—question 9 is quite a challenge!

Question 8: Applying Function Arguments

def square(x):
    return x * x

def twice(f,x):
    """Apply f to the result of applying f to x"
    >>> twice(square,3)
    81
    """
    "*** YOUR CODE HERE ***"
    return f(f(x))

Use OK to test your code:

python3 ok -q twice

def increment(x):
    return x + 1

def apply_n(f, x, n):
    """Apply function f to x n times.

    >>> apply_n(increment, 2, 10)
    12
    """
    "*** YOUR CODE HERE ***"
    res = x
    for i in range(n):
        res = f(res)
    return res

Use OK to test your code:

python3 ok -q apply_n

Question 9: Church numerals

The logician Alonzo Church invented a system of representing non-negative integers entirely using functions. The purpose was to show that functions are sufficient to describe all of number theory: if we have functions, we do not need to assume that numbers exist, but instead we can invent them.

Your goal in this problem is to rediscover this representation known as Church numerals. Here are the definitions of zero, as well as a function that returns one more than its argument:

def zero(f):
    def _zero(x):
        return x

    return _zero

def successor(n):
    def _succ(f):
        def t(x):
            return f(n(f)(x))

        return t
    return _succ

First, define functions one and two such that they have the same behavior as successor(zero) and successsor(successor(zero)) respectively, but do not call successor in your implementation.

def one(f):
    """Church numeral 1: same as successor(zero)"""
    "*** YOUR CODE HERE ***"
    def _one(x):
        return f(x)

    return _one
def two(f):
    """Church numeral 2: same as successor(successor(zero))"""
    "*** YOUR CODE HERE ***"
    def _two(x):
        return f(f(x))

    return _two

Next, implement a function church_to_int that converts a church numeral argument to a regular Python integer.

def church_to_int(n):
    """Convert the Church numeral n to a Python integer.

    >>> church_to_int(zero)
    0
    >>> church_to_int(one)
    1
    >>> church_to_int(two)
    2
    >>> church_to_int(three)
    3
    """
    "*** YOUR CODE HERE ***"
    return n(lambda x: x + 1)(0)

Use OK to test your code:

python3 ok -q church_to_int

Finally, implement functions add_church, mul_church, and pow_church that perform addition, multiplication, and exponentiation on church numerals.

def add_church(m, n):
    """Return the Church numeral for m + n, for Church numerals m and n.

    >>> church_to_int(add_church(two, three))
    5
    """
    "*** YOUR CODE HERE ***"
    return lambda f: lambda x: m(f)(n(f)(x))
def mul_church(m, n):
    """Return the Church numeral for m * n, for Church numerals m and n.

    >>> four = successor(three)
    >>> church_to_int(mul_church(two, three))
    6
    >>> church_to_int(mul_church(three, four))
    12
    """
    "*** YOUR CODE HERE ***"
    return lambda f: m(n(f))
def pow_church(m, n):
    """Return the Church numeral m ** n, for Church numerals m and n.

    >>> church_to_int(pow_church(two, three))
    8
    >>> church_to_int(pow_church(three, two))
    9
    """
    "*** YOUR CODE HERE ***"
    return n(m)

Use OK to test your code:

python3 ok -q add_church
python3 ok -q mul_church
python3 ok -q pow_church

Church numerals are a way to represent non-negative integers via repeated function application. The definitions of zero, one, and two show that each numeral is a function that takes a function and repeats it a number of times on some argument x.

The church_to_int function reveals how a Church numeral can be mapped to our normal notion of non-negative integers using the increment function.

Addition of Church numerals is function composition of the functions of x, while multiplication (added to the question for these solutions) is composition of the functions of f.

Lab 2: Lists and Higher Order Functions

Starter Files

Submission

Introduction

Lists

Question 1: Second Max

List Comprehensions

Question 2: Perfect squares

Question 3: Perfect Pairs

Functions as Arguments (Funargs)

Introduction to 'Map'

Question 4: Converter

Introduction to 'Filter'

Introduction to 'Reduce'

Question 5: reduce

Higher Order Functions

Question 6: Piecewise

Question 7: Intersect

Submit

Extra Credit Practice Open in a new window

More FUN with FUNctions (Optional)

Question 8: Applying Function Arguments

Question 9: Church numerals