Lab 4: Python Lists, Data Abstraction

Due by 11:59pm on Wednesday, July 8.

Starter Files

Download Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.


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


Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.


Lists are Python data structures that can store multiple values. Each value can be any type and can even be another list! A list is written as a comma separated list of expressions within square brackets:

>>> list_of_nums = [1, 2, 3, 4]
>>> list_of_bools = [True, True, False, False]
>>> nested_lists = [1, [2, 3], [4, [5]]]

Each element in a list is assigned an index. Lists are zero-indexed, meaning their indices start at 0 and increase in sequential order. To retrieve an element from a list, use list indexing:

>>> lst = [6, 5, 4, 3, 2, 1]
>>> lst[0]
>>> lst[3]

Often times we need to know how long a list is when we're working with it. To find the length of a list, call the function len on it:

>>> len([])
>>> len([2, 4, 6, 8, 10])

Tip: Recall that empty lists, [], are false-y values. Therefore, you can use an if statement like the following if you only want to do operations on non-empty lists:

if lst:
    # Do stuff with the elements of list

This is equivalent to:

if len(lst) > 0:
    # Do stuff

You can also create a copy of some portion of the list using list slicing. To slice a list, use this syntax: lst[<start index>:<end index>]. This expression evaluates to a new list containing the elements of lst starting at and including the element at <start index> up to but not including the element at end index.

>>> lst = [True, False, True, True, False]
>>> lst[1:4]
[False, True, True]
>>> lst[:3]  # Start index defaults to 0
[True, False, True]
>>> lst[3:]  # End index defaults to len(lst)
[True, False]
>>> lst[:]  # Creates a copy of the whole list
[True, False, True, True, False]

Data Abstraction

Data abstraction is a powerful concept in computer science that allows programmers to treat code as objects -- for example, car objects, chair objects, people objects, etc. That way, programmers don't have to worry about how code is implemented -- they just have to know what it does.

Data abstraction mimics how we think about the world. When you want to drive a car, you don't need to know how the engine was built or what kind of material the tires are made of. You just have to know how to turn the wheel and press the gas pedal.

An abstract data type consists of two types of functions:

  • Constructors: functions that build the abstract data type.
  • Selectors: functions that retrieve information from the data type.

Programmers design ADTs to abstract away how information is stored and calculated such that the end user does not need to know how constructors and selectors are implemented. The nature of abstract data types allows whoever uses them to assume that the functions have been written correctly and work as described.

Required Questions

Lists Practice

Q1: List Indexing

Use Ok to test your knowledge with the following "List Indexing" questions:

python3 ok -q list-indexing -u

For each of the following lists, what is the list indexing expression that evaluates to 7? For example, if x = [7], then the answer would be x[0]. You can use the interpreter or Python Tutor to experiment with your answers. If the code would cause an error, type Error.

>>> x = [1, 3, [5, 7], 9]
>>> x = [[3, [5, 7], 9]]

What would Python display? If you get stuck, try it out in the Python interpreter!

>>> lst = [3, 2, 7, [84, 83, 82]]
>>> lst[4]
>>> lst[3][0]

Q2: Reverse (iteratively)

Write a function reverse_iter that takes a list and returns a new list that is the reverse of the original. Use iteration! Do not use lst[::-1], lst.reverse(), or reversed(lst)!

def reverse_iter(lst):
    """Returns the reverse of the given list.

    >>> reverse_iter([1, 2, 3, 4])
    [4, 3, 2, 1]
    >>> import inspect, re
    >>> cleaned = re.sub(r"#.*\\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(reverse_iter)))
    >>> print("Do not use lst[::-1], lst.reverse(), or reversed(lst)!") if any([r in cleaned for r in ["[::", ".reverse", "reversed"]]) else None
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q reverse_iter

Q3: Reverse (recursively)

Write a function reverse_recursive that takes a list and returns a new list that is the reverse of the original. Use recursion! You may also use slicing notation. Do not use lst[::-1], lst.reverse(), or reversed(lst)!

def reverse_recursive(lst):
    """Returns the reverse of the given list.

    >>> reverse_recursive([1, 2, 3, 4])
    [4, 3, 2, 1]
    >>> import inspect, re
    >>> cleaned = re.sub(r"#.*\\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(reverse_recursive)))
    >>> print("Do not use lst[::-1], lst.reverse(), or reversed(lst)!") if any([r in cleaned for r in ["[::", ".reverse", "reversed"]]) else None
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q reverse_recursive

City Data Abstraction

Say we have an abstract data type for cities. A city has a name, a latitude coordinate, and a longitude coordinate.

Our ADT has one constructor:

  • make_city(name, lat, lon): Creates a city object with the given name, latitude, and longitude.

We also have the following selectors in order to get the information for each city:

  • get_name(city): Returns the city's name
  • get_lat(city): Returns the city's latitude
  • get_lon(city): Returns the city's longitude

Here is how we would use the constructor and selectors to create cities and extract their information:

>>> berkeley = make_city('Berkeley', 122, 37)
>>> get_name(berkeley)
>>> get_lat(berkeley)
>>> new_york = make_city('New York City', 74, 40)
>>> get_lon(new_york)

All of the selector and constructor functions can be found in the lab file, if you are curious to see how they are implemented. However, the point of data abstraction is that we do not need to know how an abstract data type is implemented, but rather just how we can interact with and use the data type.

Q4: Distance

We will now implement the function distance, which computes the distance between two city objects. Recall that the distance between two coordinate pairs (x1, y1) and (x2, y2) can be found by calculating the sqrt of (x1 - x2)**2 + (y1 - y2)**2. We have already imported sqrt for your convenience. Use the latitude and longitude of a city as its coordinates; you'll need to use the selectors to access this info!

from math import sqrt
def distance(city_a, city_b):
    >>> city_a = make_city('city_a', 0, 1)
    >>> city_b = make_city('city_b', 0, 2)
    >>> distance(city_a, city_b)
    >>> city_c = make_city('city_c', 6.5, 12)
    >>> city_d = make_city('city_d', 2.5, 15)
    >>> distance(city_c, city_d)
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q distance

Q5: Closer city

Next, implement closer_city, a function that takes a latitude, longitude, and two cities, and returns the name of the city that is relatively closer to the provided latitude and longitude.

You may only use the selectors and constructors introduced above and the distance function you just defined for this question.

Hint: How can use your distance function to find the distance between the given location and each of the given cities?

def closer_city(lat, lon, city_a, city_b):
    Returns the name of either city_a or city_b, whichever is closest to
    coordinate (lat, lon).

    >>> berkeley = make_city('Berkeley', 37.87, 112.26)
    >>> stanford = make_city('Stanford', 34.05, 118.25)
    >>> closer_city(38.33, 121.44, berkeley, stanford)
    >>> bucharest = make_city('Bucharest', 44.43, 26.10)
    >>> vienna = make_city('Vienna', 48.20, 16.37)
    >>> closer_city(41.29, 174.78, bucharest, vienna)
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q closer_city

Q6: Don't violate the abstraction barrier!

Note: this question has no code-writing component (if you implemented distance and closer_city correctly!)

When writing functions that use an ADT, we should use the constructor(s) and selector(s) whenever possible instead of assuming the ADT's implementation. Relying on a data abstraction's underlying implementation is known as violating the abstraction barrier, and we never want to do this!

It's possible that you passed the doctests for distance and closer_city even if you violated the abstraction barrier. To check whether or not you did so, run the following command:

Use Ok to test your code:

python3 ok -q check_abstraction

The make_check_abstraction function exists only for the doctest, which swaps out the implementations of the city abstraction with something else, runs the tests from the previous two parts, then restores the original abstraction.

The nature of the abstraction barrier guarantees that changing the implementation of an ADT shouldn't affect the functionality of any programs that use that ADT, as long as the constructors and selectors were used properly.

If you passed the Ok tests for the previous questions but not this one, the fix is simple! Just replace any code that violates the abstraction barrier, i.e. creating a city with a new list object or indexing into a city, with the appropriate constructor or selector.

Make sure that your functions pass the tests with both the first and the second implementations of the City ADT and that you understand why they should work for both before moving on.


Make sure to submit this assignment by running:

python3 ok --submit

Optional Questions

While "Add Characters" is optional, it is good practice for the Cats project and is thus highly recommended!

Q7: Add Characters

Given two words, w1 and w2, we say w1 is a subsequence of w2 if all the letters in w1 appear in w2 in the same order (but not necessarily all together). That is, you can add letters to any position in w1 to get w2. For example, "sing" is a substring of "absorbing" and "cat" is a substring of "contrast".

Implement add_chars, which takes in w1 and w2, where w1 is a substring of w2. This means that w1 is shorter than w2. It should return a string containing the characters you need to add to w1 to get w2. Your solution must use recursion.

In the example above, you need to add the characters "aborb" to "sing" to get "absorbing", and you need to add "ontrs" to "cat" to get "contrast".

The letters in the string you return should be in the order you have to add them from left to right. If there are multiple characters in the w2 that could correspond to characters in w1, use the leftmost one. For example, add_words("coy", "cacophony") should return "acphon", not "caphon" because the first "c" in "coy" corresponds to the first "c" in "cacophony".

def add_chars(w1, w2):
    Return a string containing the characters you need to add to w1 to get w2.

    You may assume that w1 is a subsequence of w2.

    >>> add_chars("owl", "howl")
    >>> add_chars("want", "wanton")
    >>> add_chars("rat", "radiate")
    >>> add_chars("a", "prepare")
    >>> add_chars("resin", "recursion")
    >>> add_chars("fin", "effusion")
    >>> add_chars("coy", "cacophony")
    >>> from construct_check import check
    >>> # ban iteration and sets
    >>> check(LAB_SOURCE_FILE, 'add_chars',
    ...       ['For', 'While', 'Set', 'SetComp']) # Must use recursion
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q add_chars