Lab 5: Data Abstraction, Mutability

Due by 11:59pm on Tuesday, July 9.

Starter Files

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

Required Questions


Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

Mutability

Consult the drop-down if you need a refresher on mutability. It's okay to skip directly to the questions and refer back here should you get stuck.

Some objects in Python, such as lists and dictionaries, are mutable, meaning that their contents or state can be changed. Other objects, such as numeric types, tuples, and strings, are immutable, meaning they cannot be changed once they are created.

The two most common mutation operations for lists are item assignment and the append method.

>>> s = [1, 3, 4]
>>> t = s  # A second name for the same list
>>> t[0] = 2  # this changes the first element of the list to 2, affecting both s and t
>>> s
[2, 3, 4]
>>> s.append(5)  # this adds 5 to the end of the list, affecting both s and t
>>> t
[2, 3, 4, 5]

There are many other list mutation methods:

  • append(elem): Add elem to the end of the list. Return None.
  • extend(s): Add all elements of iterable s to the end of the list. Return None.
  • insert(i, elem): Insert elem at index i. If i is greater than or equal to the length of the list, then elem is inserted at the end. This does not replace any existing elements, but only adds the new element elem. Return None.
  • remove(elem): Remove the first occurrence of elem in list. Return None. Errors if elem is not in the list.
  • pop(i): Remove and return the element at index i.
  • pop(): Remove and return the last element.

Dictionaries also have item assignment (often used) and pop (rarely used).

>>> d = {2: 3, 4: 16}
>>> d[2] = 4
>>> d[3] = 9
>>> d
{2: 4, 4: 16, 3: 9}
>>> d.pop(4)
16
>>> d
{2: 4, 3: 9}

Dictionaries are data structures which map keys to values. Dictionaries in Python are unordered, unlike real-world dictionaries --- in other words, key-value pairs are not arranged in the dictionary in any particular order. Let's look at an example:

>>> pokemon = {'pikachu': 25, 'dragonair': 148, 'mew': 151}
>>> pokemon['pikachu']
25
>>> pokemon['jolteon'] = 135
>>> pokemon
{'jolteon': 135, 'pikachu': 25, 'dragonair': 148, 'mew': 151}
>>> pokemon['ditto'] = 25
>>> pokemon
{'jolteon': 135, 'pikachu': 25, 'dragonair': 148,
'ditto': 25, 'mew': 151}

The keys of a dictionary can be any immutable value, such as numbers, strings, and tuples.[1] Dictionaries themselves are mutable; we can add, remove, and change entries after creation. There is only one value per key, however --- if we assign a new value to the same key, it overrides any previous value which might have existed.

To access the value of dictionary at key, use the syntax dictionary[key].

Element selection and reassignment work similarly to sequences, except the square brackets contain the key, not an index.

[1]To be exact, keys must be hashable, which is out of scope for this course. This means that some mutable objects, such as classes, can be used as dictionary keys.

Q1: WWPD: List-Mutation

Important: For all WWPD questions, type Function if you believe the answer is <function...>, Error if it errors, and Nothing if nothing is displayed.

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q list-mutation -u

>>> s = [6, 7, 8]
>>> print(s.append(6))

______
None

>>> s

______
[6, 7, 8, 6]

>>> s.insert(0, 9)
>>> s

______
[9, 6, 7, 8, 6]

>>> x = s.pop(1)
>>> s

______
[9, 7, 8, 6]

>>> s.remove(x)
>>> s

______
[9, 7, 8]

>>> a, b = s, s[:]
>>> a is s

______
True

>>> b == s

______
True

>>> b is s

______
False

>>> a.pop()

______
8

>>> a + b

______
[9, 7, 9, 7, 8]

>>> s = [3]
>>> s.extend([4, 5])
>>> s

______
[3, 4, 5]

>>> a

______
[9, 7]

>>> s.extend([s.append(9), s.append(10)])
>>> s

______
[3, 4, 5, 9, 10, None, None]

Q2: WWPD: Dictionary Mutation

Important: For all WWPD questions, type Function if you believe the answer is <function...>, Error if it errors, and Nothing if nothing is displayed.

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q dictionaries-wwpd -u

>>> pokemon = {'pikachu': 25, 'dragonair': 148}
>>> pokemon

______
{'pikachu': 25, 'dragonair': 148}

>>> 'mewtwo' in pokemon

______
False

>>> len(pokemon)  

______
2

>>> pokemon['mew'] = pokemon['pikachu']   #If this errors, just type Error
>>> pokemon[25] = 'pikachu'
>>> pokemon

______
{'pikachu': 25, 'dragonair': 148, 'mew': 25, 25: 'pikachu'}

>>> pokemon['mewtwo'] = pokemon['mew'] * 2  
>>> pokemon

______
{'pikachu': 25, 'dragonair': 148, 'mew': 25, 25: 'pikachu', 'mewtwo': 50}

>>> pokemon[['firetype', 'flying']] = 146  # If this errors, just type Error. Note that dictionary keys must be hashable.

______
Error

Q3: Partial Reverse

When working with lists, it is often useful to reverse the list. For example, reversing the list [1, 2, 3, 4, 5] will give [5, 4, 3, 2, 1]. However, in some situations, it may be more useful to only partially reverse the list and keep some of its elements in the same order. For example, partially reversing the list [1, 2, 3, 4, 5] starting from index 2 until the end of the list will give [1, 2, 5, 4, 3].

Implement the function partial_reverse which reverses a list starting from start until the end of the list. This reversal should be in-place, meaning that the original list is modified. Do not create a new list inside your function, even if you do not return it. The partial_reverse function returns None.

Hint: You can swap elements at index i and j in list s with multiple assignment: s[i], s[j] = s[j], s[i]

def partial_reverse(s, start):
    """Reverse part of a list in-place, starting with start up to the end of
    the list.

    >>> a = [1, 2, 3, 4, 5, 6, 7]
    >>> partial_reverse(a, 2)
    >>> a
    [1, 2, 7, 6, 5, 4, 3]
    >>> partial_reverse(a, 5)
    >>> a
    [1, 2, 7, 6, 5, 3, 4]
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q partial_reverse

Q4: Group By

Write a function that takes in a list s and a function fn, and returns a dictionary.

In this dictionary, each key should be the result of applying fn to the elements in s, and each corresponding value should be a list of elements from s that produce the same result when fn is applied to them.

For example, if an element e in s results in fn(e), then e should be added to the list corresponding to the key fn(e) in the dictionary.

def group_by(s, fn):
    """Return a dictionary of lists that together contain the elements of s.
    The key for each list is the value that fn returns when called on any of the
    values of that list.

    >>> group_by([12, 23, 14, 45], lambda p: p // 10)
    {1: [12, 14], 2: [23], 4: [45]}
    >>> group_by(range(-3, 4), lambda x: x * x)
    {9: [-3, 3], 4: [-2, 2], 1: [-1, 1], 0: [0]}
    """
    grouped = {}
    for ____ in ____:
        key = ____
        if key in grouped:
            ____
        else:
            grouped[key] = ____
    return grouped

Use Ok to test your code:

python3 ok -q group_by

Data Abstraction

Consult the drop-down if you need a refresher on data abstraction. It's okay to skip directly to the questions and refer back here should you get stuck.

A data abstraction is a set of functions that compose and decompose compound values. One function called the constructor puts together two or more parts into a whole (such as a rational number; also known as a fraction), and other functions called selectors return parts of that whole (such as the numerator or denominator).

def rational(n, d):
    "Return a fraction n / d for integers n and d."

def numer(r):
    "Return the numerator of rational number r."

def denom(r):
    "Return the denominator of rational number r."

Crucially, one can use a data abstraction without knowing how these functions are implemented. For example, we (humans) can verify that mul_rationals is implemented correctly just by knowing what rational, numer, and denom do without knowing how they are implemented.

def mul_rationals(r1, r2):
    "Return the rational number r1 * r2."
    return rational(numer(r1) * numer(r2), denom(r1) * denom(r2))

However, for Python to run the program, the data abstraction requires an implementation. Using knowledge of the implementation crosses the abstraction barrier, which separates the part of a program that depends on the implementation of the data abstraction from the part that does not. A well-written program typically will minimize the amount of code that depends on the implementation so that the implementation can be changed later on without requiring much code to be rewritten.

When using a data abstraction that has been provided, write your program so that it will still be correct even if the implementation of the data abstraction changes.

Cities

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

Our data abstraction 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)
'Berkeley'
>>> get_lat(berkeley)
122
>>> new_york = make_city('New York City', 74, 40)
>>> get_lon(new_york)
40

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, when writing a program about cities, we do not need to know the implementation.

Q5: 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)
    1.0
    >>> city_c = make_city('city_c', 6.5, 12)
    >>> city_d = make_city('city_d', 2.5, 15)
    >>> distance(city_c, city_d)
    5.0
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q distance

Q6: 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 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 you 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). If the two cities are the same distance away
    from the coordinate, consider city_b to be the closer city.

    >>> berkeley = make_city('Berkeley', 37.87, 112.26)
    >>> stanford = make_city('Stanford', 34.05, 118.25)
    >>> closer_city(38.33, 121.44, berkeley, stanford)
    '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)
    'Bucharest'
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q closer_city

Q7: Don't violate the abstraction barrier!

Note: this question has no code-writing component (if you implemented the previous two questions correctly).

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

It's possible that you passed the doctests for the previous questions 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_city_abstraction

The check_city_abstraction function exists only for the doctest, which swaps out the implementations of the original 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 data abstraction shouldn't affect the functionality of any programs that use that data abstraction, 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 with the appropriate constructor or selector.

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

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.

In addition, all students who are not in the mega lab must submit the attendance form for credit. Ask your section TA for the link! Submit this form for each section, whether you attended lab or missed it for a good reason. The attendance form is not required for mega section students.