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)
: Appendsel
to the end of the list and returnsNone
.extend(lst)
: Extends the list by concatenating it withlst
and returnsNone
.remove(el)
: Removes the first occurence ofel
from the list and returnsNone
.insert(i, el)
: Insertsel
at indexi
and returnsNone
.pop(i)
: Removes and returns the element at indexi
. 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 thatl
evaluates to is being mutated. - The only method here that has a return value is
pop
! All of the other methods returnNone
.
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 allCar
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 theCar
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
instanceself.wheels
andself.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 methodsdrive
andpop_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 theself.wheels
andself.color
attributes.self
: in Python,self
is the first parameter for many methods (in this class, we will only use methods whose first parameter isself
). 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 inself
as an argument, but it looks like we didn't pass one in! This is because the dot notation implicitly passes incar
asself
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, andNothing
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, andNothing
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
andelem
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 ayear
stamp. Theupdate
method sets theyear
stamp to thepresent_year
class attribute of theMinty
class. - The
create
method returns an instance ofCoin
stamped with theminty
's year (which may be different fromMinty.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 correctcents
value. - A
Coin
'sworth
method returns thecents
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 thepresent_year
class attribute of theMinty
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