# Lab 4: Sequences, Mutability, Object-Oriented Programming lab04.zip

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
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``