Lab 4: Sequences, Mutability, Object-Oriented Programming

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

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.

Topics

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

A list is a data structure that can store multiple elements. Each element can be of any type, even a list itself. We write a list as a comma-separated list of expressions in square brackets:

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

Each element in the list has an index, with the index of the first element starting at 0. We say that lists are therefore "zero-indexed."

With list indexing, we can specify the index of the element we want to retrieve. A negative index represents starting from the end of the list, so the negative index -i is equivalent to the positive index len(lst)-i.

>>> lst = [6, 5, 4, 3, 2, 1, 0]
>>> lst[0]
6
>>> lst[3]
3
>>> lst[-1] # Same as lst[6]
0

To create a copy of part or all of a list, we can use list slicing. The syntax to slice a list lst is: lst[<start index>:<end index>:<step size>].

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>.
  • With <step size> as the difference between indices of elements to include.

If the start, end, or step size are not explicitly specified, Python has default values for them. A negative step size indicates that we are stepping backwards through a list when including elements.

>>> lst[:3]   # Start index defaults to 0
[6, 5, 4]
>>> lst[3:]   # End index defaults to len(lst)
[3, 2, 1, 0]
>>> lst[::-1]   # Make a reversed copy of the entire list
[0, 1, 2, 3, 4, 5, 6]
>>> lst[::2]  # Skip every other; step size defaults to 1 otherwise
[6, 4, 2, 0]


List Comprehensions

List comprehensions are a compact and powerful way of creating new lists out of sequences. The general syntax for a list comprehension is the following:

[<expression> for <element> in <sequence> if <conditional>]

where the if <conditional> section is optional.

The syntax is designed to read like English: "Compute the expression for each element in the sequence (if the conditional is true for that element)."

>>> [i**2 for i in [1, 2, 3, 4] if i % 2 == 0]
[4, 16]

This list comprehension will:

  • Compute the expression i**2
  • For each element i in the sequence [1, 2, 3, 4]
  • Where i % 2 == 0 (i is an even number),

and then put the resulting values of the expressions into a new list.

In other words, this list comprehension will create a new list that contains the square of every even element of the original list [1, 2, 3, 4].

We can also rewrite a list comprehension as an equivalent for statement, such as for the example above:

>>> lst = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         lst = lst + [i**2]
>>> lst
[4, 16]


Mutability

We say that an object is mutable if its state can change as code is executed. The process of changing an object's state is called mutation. Examples of mutable objects include lists and dictionaries. Examples of objects that are not mutable include tuples and functions.

There are many built-in methods that we can use to mutate lists. Here are some of the most useful ones:

  • append(el): Appends el to the end of the list and returns None.
  • extend(lst): Extends the list by concatenating it with lst and returns None.
  • remove(el): Removes the first occurence of el from the list and returns None.
  • insert(i, el): Inserts el at index i and returns None.
  • pop(i): Removes and returns the element at index i. If no index is given, removes and returns the last element in the list.

To call methods, we use dot notation:

>>> lst = [1, 2, 3, 4]
>>> lst.append(5)
>>> lst.insert(2, 2.5)

The list that we are mutating precedes the . and the method we are calling follows it, using regular call expression syntax to pass in arguments. We will learn more about methods in detail later in the course when we discuss object oriented programming.

Let's see these methods in action:

>>> l = [3, 5, 6]
>>> l.append(10)    # Append 10 to the end of the list
>>> l
[3, 5, 6, 10]
>>> l.extend([30, 40])
>>> l
[3, 5, 6, 10, 30, 40]
>>> l.remove(5)     # Remove the first occurrence of 5
>>> l
[3, 6, 10, 30, 40]
>>> l.insert(2, -2) # Insert -2 at index 2
>>> l
[3, 6, -2, 10, 30, 40]
>>> l.pop()         # Remove and return the last element
40
>>> l
[3, 6, -2, 10, 30]
>>> l.pop(2)        # Remove and return the element at index 2
-2
>>> l
[3, 6, 10, 30]

Take note of two things:

  • The name l refers to the same list object during this entire session; it is never reassigned. The reason the output looks different each time we call a method is because the list that l evaluates to is being mutated.
  • The only method here that has a return value is pop! All of the other methods return None.

Here are the above method calls displayed in an environment diagram:



Object Oriented Programming

Object-oriented programming (OOP) is a style of programming that allows you to think of code in terms of "objects." Here's an example of a Car class:

class Car:
    num_wheels = 4

    def __init__(self, color):
        self.wheels = Car.num_wheels
        self.color = color

    def drive(self):
        if self.wheels <= Car.num_wheels:
            return self.color + ' car cannot drive!'
        return self.color + ' car goes vroom!'

    def pop_tire(self):
        if self.wheels > 0:
            self.wheels -= 1

Here's some terminology:

  • class: a blueprint for how to build a certain type of object. The Car class (shown above) describes the behavior and data that all Car objects have.
  • instance: a particular occurrence of a class. In Python, we create instances of a class like this:

    >>> my_car = Car('red')

    my_car is an instance of the Car class.

  • data attributes: a variable that belongs to the instance (also called instance variables). Think of a data attribute as a quality of the object: cars have wheels and color, so we have given our Car instance self.wheels and self.color attributes. We can access attributes using dot notation:

    >>> my_car.color
    'red'
    >>> my_car.wheels
    4
  • method: Methods are just like normal functions, except that they are bound to an instance. Think of a method as a "verb" of the class: cars can drive and also pop their tires, so we have given our Car instance the methods drive and pop_tire. We call methods using dot notation:

    >>> my_car = Car('red')
    >>> my_car.drive()
    'red car goes vroom!'
  • constructor: Constructors build an instance of the class. The constructor for car objects is Car(color). When Python calls that constructor, it immediately calls the __init__ method. That's where we initialize the data attributes:

    def __init__(self, color):
        self.wheels = Car.num_wheels
        self.color = color

    The constructor takes in one argument, color. As you can see, this constructor also creates the self.wheels and self.color attributes.

  • self: in Python, self is the first parameter for many methods (in this class, we will only use methods whose first parameter is self). When a method is called, self is bound to an instance of the class. For example:

    >>> my_car = Car('red')
    >>> car.drive()

    Notice that the drive method takes in self as an argument, but it looks like we didn't pass one in! This is because the dot notation implicitly passes in car as self for us.


Required Questions

What Would Python Do?

Q1: WWPD: List-Mutation

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

python3 ok -q list-mutation -u

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

>>> lst = [5, 6, 7, 8]
>>> lst.append(6)
______
None
>>> lst
______
[5, 6, 7, 8, 6]
>>> lst.insert(0, 9) >>> lst
______
[9, 5, 6, 7, 8, 6]
>>> x = lst.pop(2) >>> lst
______
[9, 5, 7, 8, 6]
>>> lst.remove(x) >>> lst
______
[9, 5, 7, 8]
>>> a, b = lst, lst[:] >>> a is lst
______
True
>>> b == lst
______
True
>>> b is lst
______
False
>>> lst = [1, 2, 3] >>> lst.extend([4,5]) >>> lst
______
[1, 2, 3, 4, 5]
>>> lst.extend([lst.append(9), lst.append(10)]) >>> lst
______
[1, 2, 3, 4, 5, 9, 10, None, None]

Q2: WWPD: Classy Cars

Below is the definition of a Car class that we will be using in the following WWPD questions.

class Car:
    num_wheels = 4
    gas = 30
    headlights = 2
    size = 'Tiny'

    def __init__(self, make, model):
        self.make = make
        self.model = model
        self.color = 'No color yet. You need to paint me.'
        self.wheels = Car.num_wheels
        self.gas = Car.gas

    def paint(self, color):
        self.color = color
        return self.make + ' ' + self.model + ' is now ' + color

    def drive(self):
        if self.wheels < Car.num_wheels or self.gas <= 0:
            return 'Cannot drive!'
        self.gas -= 10
        return self.make + ' ' + self.model + ' goes vroom!'

    def pop_tire(self):
        if self.wheels > 0:
            self.wheels -= 1

    def fill_gas(self):
        self.gas += 20
        return 'Gas level: ' + str(self.gas)

You can find the unlocking questions below.

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

python3 ok -q no-wwpd-car -u

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

>>> deneros_car = Car('Tesla', 'Model S')
>>> deneros_car.model
______
'Model S'
>>> deneros_car.gas = 10 >>> deneros_car.drive()
______
'Tesla Model S goes vroom!'
>>> deneros_car.drive()
______
'Cannot drive!'
>>> deneros_car.fill_gas()
______
'Gas level: 20'
>>> deneros_car.gas
______
20
>>> Car.gas
______
30
>>> deneros_car = Car('Tesla', 'Model S')
>>> deneros_car.wheels = 2
>>> deneros_car.wheels
______
2
>>> Car.num_wheels
______
4
>>> deneros_car.drive()
______
'Cannot drive!'
>>> Car.drive()
______
Error (TypeError)
>>> Car.drive(deneros_car)
______
'Cannot drive!'

Code Writing Questions

Q3: Flatten

Write a function flatten that takes a list and returns a "flattened" version of it. The list could be a deep list, meaning that there could be a multiple layers of nesting within the list.

Make sure your solution does not mutate the input list.

For example, one use case of flatten could be the following:

>>> lst = [1, [[2], 3], 4, [5, 6]]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6]

Hint: you can check if something is a list by using the built-in type function. For example:

>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True
def flatten(s):
    """Returns a flattened version of list s.

    >>> flatten([1, 2, 3])     # normal list
    [1, 2, 3]
    >>> x = [1, [2, 3], 4]     # deep list
    >>> flatten(x)
    [1, 2, 3, 4]
    >>> x # Ensure x is not mutated
    [1, [2, 3], 4]
    >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
    >>> flatten(x)
    [1, 1, 1, 1, 1, 1]
    >>> x
    [[1, [1, 1]], 1, [1, 1]]
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q flatten

Q4: Insert Items

Write a function which takes in a list lst, an argument entry, and another argument elem. This function will check through each item in lst to see if it is equal to entry. Upon finding an item equal to entry, the function should modify the list by placing elem into lst right after the item. At the end of the function, the modified list should be returned.

See the doctests for examples on how this function is utilized.

Important: Use list mutation to modify the original list. No new lists should be created or returned.

Note: If the values passed into entry and elem are equivalent, make sure you're not creating an infinitely long list while iterating through it. If you find that your code is taking more than a few seconds to run, the function may be in an infinite loop of inserting new values.

def insert_items(lst, entry, elem):
    """Inserts elem into lst after each occurrence of entry and then returns lst.

    >>> test_lst = [1, 5, 8, 5, 2, 3]
    >>> new_lst = insert_items(test_lst, 5, 7)
    >>> new_lst
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> double_lst = [1, 2, 1, 2, 3, 3]
    >>> double_lst = insert_items(double_lst, 3, 4)
    >>> double_lst
    [1, 2, 1, 2, 3, 4, 3, 4]
    >>> large_lst = [1, 4, 8]
    >>> large_lst2 = insert_items(large_lst, 4, 4)
    >>> large_lst2
    [1, 4, 4, 8]
    >>> large_lst3 = insert_items(large_lst2, 4, 6)
    >>> large_lst3
    [1, 4, 6, 4, 6, 8]
    >>> large_lst3 is large_lst
    True
    >>> # Ban creating new lists
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'insert_items',
    ...       ['List', 'ListComp', 'Slice'])
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q insert_items

Q5: Minty

A mint is a place where coins are made. In this question, you'll implement a Minty class that can output a Coin with the correct year and worth.

  • Each Minty instance has a year stamp. The update method sets the year stamp to the present_year class attribute of the Minty class.
  • The create method returns an instance of Coin stamped with the minty's year (which may be different from Minty.present_year if it has not been updated.)
  • The Coin constructor should ensure that each coin has the correct year and that each type of Coin ('Dime' or 'Nickel' in our case) has the correct cents value.
  • A Coin's worth method returns the cents value of the coin plus one extra cent for each year of age beyond 50. A coin's age can be determined by subtracting the coin's year from the present_year class attribute of the Minty class.
class Minty:
    """A mint creates coins by stamping on years. The update method sets the mint's stamp to Minty.present_year.
    >>> mint = Minty()
    >>> mint.year
    2021
    >>> dime = mint.create('Dime')
    >>> dime.year
    2021
    >>> Minty.present_year = 2101  # Time passes
    >>> nickel = mint.create('Nickel')
    >>> nickel.year     # The mint has not updated its stamp yet
    2021
    >>> nickel.worth()  # 5 cents + (80 - 50 years)
    35
    >>> mint.update()   # The mint's year is updated to 2101
    >>> Minty.present_year = 2176     # More time passes
    >>> mint.create('Dime').worth()    # 10 cents + (75 - 50 years)
    35
    >>> Minty().create('Dime').worth()  # A new mint has the current year
    10
    >>> dime.worth()     # 10 cents + (155 - 50 years)
    115
    """
    present_year = 2021

    def __init__(self):
        self.update()

    def create(self, type):
        "*** YOUR CODE HERE ***"

    def update(self):
        "*** YOUR CODE HERE ***"

class Coin:
    cents = 50

    def __init__(self, year, type):
        "*** YOUR CODE HERE ***"

    def worth(self):
        "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q Minty

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Optional Question

Q6: Couple

Implement the function couple, which takes in two lists and returns a list that contains lists with i-th elements of two sequences coupled together. You can assume the lengths of two sequences are the same. Try using a list comprehension.

Hint: You may find the built in range function helpful.

def couple(s, t):
    """Return a list of two-element lists in which the i-th element is [s[i], t[i]].

    >>> a = [1, 2, 3]
    >>> b = [4, 5, 6]
    >>> couple(a, b)
    [[1, 4], [2, 5], [3, 6]]
    >>> c = ['c', 6]
    >>> d = ['s', '1']
    >>> couple(c, d)
    [['c', 's'], [6, '1']]
    """
    assert len(s) == len(t)
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q couple