Lab 6: Mutability, Iterators
Due by 11:59pm on Wednesday, March 1.
Starter Files
Download lab06.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.
Mutability
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.
Let's imagine you order a mushroom and cheese pizza from La Val's, and they represent your order as a list:
>>> pizza = ['cheese', 'mushrooms']
With list mutation, they can update your order by mutate pizza
directly
rather than having to create a new list:
>>> pizza.append('onions')
>>> pizza
['cheese', 'mushrooms', 'onions']
Aside from append
, there are various other list mutation methods:
append(el)
: Addel
to the end of the list. ReturnNone
.extend(lst)
: Extend the list by concatenating it withlst
. ReturnNone
.insert(i, el)
: Insertel
at indexi
. This does not replace any existing elements, but only adds the new elementel
. ReturnNone
.remove(el)
: Remove the first occurrence ofel
in list. Errors ifel
is not in the list. ReturnNone
otherwise.pop(i)
: Remove and return the element at indexi
.
We can also use list indexing with an assignment statement to change an existing element in a list. For example:
>>> pizza[1] = 'tomatoes'
>>> pizza
['cheese', 'tomatoes', 'onions']
Iterators
An iterable is any object that can be iterated through, or gone through one element at a time. One construct that we've used to iterate through an iterable is a for loop:
for elem in iterable:
# do something
for
loops work on any object that is iterable. We previously described it
as working with any sequence -- all sequences are iterable, but there are other
objects that are also iterable! We define an iterable as an object on which
calling the built-in iter
function returns an iterator. An
iterator is another type of object that allows us to iterate through an
iterable by keeping track of which element is next in the sequence.
To illustrate this, consider the following block of code, which does the exact
same thing as the for
statement above:
iterator = iter(iterable)
try:
while True:
elem = next(iterator)
# do something
except StopIteration:
pass
Here's a breakdown of what's happening:
- First, the built-in
iter
function is called on the iterable to create a corresponding iterator. - To get the next element in the sequence, the built-in
next
function is called on this iterator. - When
next
is called but there are no elements left in the iterator, aStopIteration
error is raised. In the for loop construct, this exception is caught and execution can continue.
Calling iter
on an iterable multiple times returns a new iterator each time
with distinct states (otherwise, you'd never be able to iterate through a
iterable more than once). You can also call iter
on the iterator itself, which
will just return the same iterator without changing its state. However, note
that you cannot call next
directly on an iterable.
Let's see the iter
and next
functions in action with an iterable we're
already familiar with -- a list.
>>> lst = [1, 2, 3, 4]
>>> next(lst) # Calling next on an iterable
TypeError: 'list' object is not an iterator
>>> list_iter = iter(lst) # Creates an iterator for the list
>>> list_iter
<list_iterator object ...>
>>> next(list_iter) # Calling next on an iterator
1
>>> next(list_iter) # Calling next on the same iterator
2
>>> next(iter(list_iter)) # Calling iter on an iterator returns itself
3
>>> list_iter2 = iter(lst)
>>> next(list_iter2) # Second iterator has new state
1
>>> next(list_iter) # First iterator is unaffected by second iterator
4
>>> next(list_iter) # No elements left!
StopIteration
>>> lst # Original iterable is unaffected
[1, 2, 3, 4]
Since you can call iter
on iterators, this tells us that that they are also
iterables! Note that while all iterators are iterables, the converse is not
true - that is, not all iterables are iterators. You can use iterators wherever
you can use iterables, but note that since iterators keep their state, they're
only good to iterate through an iterable once:
>>> list_iter = iter([4, 3, 2, 1])
>>> for e in list_iter:
... print(e)
4
3
2
1
>>> for e in list_iter:
... print(e)
Analogy: An iterable is like a book (one can flip through the pages) and an iterator for a book would be a bookmark (saves the position and can locate the next page). Calling
iter
on a book gives you a new bookmark independent of other bookmarks, but callingiter
on a bookmark gives you the bookmark itself, without changing its position at all. Callingnext
on the bookmark moves it to the next page, but does not change the pages in the book. Callingnext
on the book wouldn't make sense semantically. We can also have multiple bookmarks, all independent of each other.
Iterable Uses
We know that lists are one type of built-in iterable objects. You may have also
encountered the range(start, end)
function, which creates an iterable of
ascending integers from start (inclusive) to end (exclusive).
>>> for x in range(2, 6):
... print(x)
...
2
3
4
5
Ranges are useful for many things, including performing some operations for a particular number of iterations or iterating through the indices of a list.
There are also some built-in functions that take in iterables and return useful results:
map(f, iterable)
- Creates an iterator overf(x)
forx
initerable
. In some cases, computing a list of the values in this iterable will give us the same result as [func(x)
forx
initerable
]. However, it's important to keep in mind that iterators can potentially have infinite values because they are evaluated lazily, while lists cannot have infinite elements.filter(f, iterable)
- Creates an iterator overx
for eachx
initerable
iff(x)
zip(iterables*)
- Creates an iterator over co-indexed tuples with elements from each of theiterables
reversed(iterable)
- Creates an iterator over all the elements in the input iterable in reverse orderlist(iterable)
- Creates a list containing all the elements in the inputiterable
tuple(iterable)
- Creates a tuple containing all the elements in the inputiterable
sorted(iterable)
- Creates a sorted list containing all the elements in the inputiterable
reduce(f, iterable)
- Must be imported withfunctools
. Apply function of two argumentsf
cumulatively to the items ofiterable
, from left to right, so as to reduce the sequence to a single value.
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.
Mutability
Q1: WWPD: List-Mutation
Important: For all WWPD questions, type
Function
if you believe the answer is<function...>
,Error
if it errors, andNothing
if nothing is displayed.
Use Ok to test your knowledge with the following "What Would Python Display?" questions:
python3 ok -q list-mutation -u
>>> 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: 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]
>>> test_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
Iterators
Q3: WWPD: Iterators
Important: Enter
StopIteration
if aStopIteration
exception occurs,Error
if you believe a different error occurs, andIterator
if the output is an iterator object.
Use Ok to test your knowledge with the following "What Would Python Display?" questions:
python3 ok -q iterators-wwpd -u
Python's built-in
map
,filter
, andzip
functions return iterators, not lists. These built-in functions are different from themy_map
andmy_filter
functions we implemented in Discussion 05.
>>> s = [1, 2, 3, 4]
>>> t = iter(s)
>>> next(s) #
______Error
>>> next(t)
______1
>>> next(t)
______2
>>> iter(s)
______Iterator
>>> next(iter(s))
______1
>>> next(iter(t))
______3
>>> next(iter(s))
______1
>>> next(iter(t))
______4
>>> next(t)
______StopIteration
>>> r = range(6)
>>> r_iter = iter(r)
>>> next(r_iter)
______0
>>> [x + 1 for x in r]
______[1, 2, 3, 4, 5, 6]
>>> [x + 1 for x in r_iter]
______[2, 3, 4, 5, 6]
>>> next(r_iter)
______StopIteration
>>> list(range(-2, 4)) # Converts an iterable into a list
______[-2, -1, 0, 1, 2, 3]
>>> map_iter = map(lambda x : x + 10, range(5))
>>> next(map_iter)
______10
>>> next(map_iter)
______11
>>> list(map_iter)
______[12, 13, 14]
>>> for e in filter(lambda x : x % 2 == 0, range(1000, 1008)):
... print(e)
______1000
1002
1004
1006
>>> [x + y for x, y in zip([1, 2, 3], [4, 5, 6])]
______[5, 7, 9]
>>> for e in zip([10, 9, 8], range(3)):
... print(tuple(map(lambda x: x + 2, e)))
______(12, 2)
(11, 3)
(10, 4)
Q4: Count Occurrences
Implement count_occurrences
,
which takes in an iterator t
and returns the number of times the value x
appears in the first n
elements of t
.
A value appears in a sequence of elements
if it is equal to an entry in the sequence.
Note: You can assume that
t
will have at leastn
elements.
Hint: When the same iterator is passed into a function twice, it should pick up where it left off. Take note of how we pass the iterator
s
twice in the doctests into two consecutive calls tocount_occurrences
. Here,s
didn't restart from the beginning of the iterable since in the secondcount_occurrences
call, the iterator goes through three2
s, starting from the second value in the iterator, not the first.
def count_occurrences(t, n, x):
"""Return the number of times that x appears in the first n elements of iterator t.
>>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
>>> count_occurrences(s, 10, 9)
3
>>> s2 = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
>>> count_occurrences(s2, 3, 10)
2
>>> s = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
>>> count_occurrences(s, 1, 3)
1
>>> count_occurrences(s, 3, 2)
3
>>> next(s)
1
>>> s2 = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
>>> count_occurrences(s2, 6, 6)
2
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q count_occurrences
Q5: Repeated
Implement repeated
,
which takes in an iterator t
and returns the first value in t
that appears k
times in a row.
Note: You can assume that the iterator
t
will have a value that appears at leastk
times in a row. If you are receiving aStopIteration
, yourrepeated
function is likely not identifying the correct value.
Your implementation should iterate through the items in a way such that
if the same iterator is passed into repeated
twice,
it should continue in the second call at the point it left off in the first.
An example of this behavior is in the doctests.
def repeated(t, k):
"""Return the first value in iterator T that appears K times in a row.
Iterate through the items such that if the same iterator is passed into
the function twice, it continues in the second call at the point it left
off in the first.
>>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
>>> repeated(s, 2)
9
>>> s2 = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
>>> repeated(s2, 3)
8
>>> s = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
>>> repeated(s, 3)
2
>>> repeated(s, 3)
5
>>> s2 = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
>>> repeated(s2, 3)
2
"""
assert k > 1
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q repeated
Submit
Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.
Optional Questions
These questions are optional, but you must complete them in order to be checked off before the end of the lab period. They are also useful practice!
Leonardo da Vinci is well know for his inventions, his paintings, and his numerous contributions to many other fields. It is less known that he only turned to art after failing miserably as an apprentice in a pizzeria. (Granted, modern pizza was invented centuries after his era, but its precursors have been around since Roman times.)
One day, little Leonardo was at the pizzeria, mindlessly flipping over partially cooked crusts with a spatula. At that moment, inspiration struck, and he realized that he could sort the crusts in a stack, so that the largest ended up at the bottom and the smallest at the top, with each crust smaller than the one below it. He named his procedure "pizza sort" and wrote it down in a journal.
Unfortunately, that journal was lost to time, so pizza sort, perhaps Leonardo's greatest invention, remained unknown. Until now. Last year, a previously unknown journal was found in the hands of a private collector, and it appears to be that elusive journal in which Leonardo recorded his pizza sort. Unfortunately, time has not been kind to the journal, so many details are missing. But archaeologists have managed to recover one key piece of the puzzle: the only allowed move in pizza sort is to place the spatula under a crust in the stack and flip the set of crusts above the spatula:
====
==
========== <--- spatula underneath this crust
========
||
||
\||/
\/
========== }
== } flipped
==== }
========
Q6: Partial Reverse
Implement this flip operation in code, with the stack of crusts
represented as a list starting from the bottom of the stack. Write a
function partial_reverse
to reverse the subset of 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.
Note: As can be seen from the doctests,
partial_reverse
should returnNone
. (Don't put in an explicitreturn None
, however; either leave out any return statement or just usereturn
with no expression.)
def partial_reverse(lst, 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
Q7: Index Largest
The archaeologists also found some indecipherable symbols along with the description of the above procedure. As they could make neither heads nor tails of it, they called it "the da Vinci code." Hoping to crack it, they asked Eva Lu Ator, a leading computer scientist, for help. Upon closer examination, she realized that the da Vinci code was actual code, in a rudimentary programming language that Leonardo had invented. This code would find the position of the largest crust in a stack of pizzas.
Help Eva to translate the da Vinci code into Python. Write a function that takes in a sequence and returns the index of the largest element in the sequence:
def index_largest(seq):
"""Return the index of the largest element in the sequence.
>>> index_largest([8, 5, 7, 3 ,1])
0
>>> index_largest((4, 3, 7, 2, 1))
2
"""
assert len(seq) > 0
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q index_largest
Q8: Pizza Sort
Finally, help the world learn the secret of the da Vinci code by
writing the pizza_sort
function. This function takes in a list and
sorts its elements in descending order, using only the previous two
functions and the built-in len
function. It is well-known that
Leonardo hated iteration, so make sure to use recursion instead. (You
may define a helper function if you want.) Lastly, you may use slicing;
we are talking about pizza, after all.
Keep in mind, however, that slicing returns a new list, but you need to sort the existing list in place.
def pizza_sort(lst):
"""Perform an in-place pizza sort on the given list, resulting in
elements in descending order.
>>> a = [8, 5, 7, 3, 1, 9, 2]
>>> pizza_sort(a)
>>> a
[9, 8, 7, 5, 3, 2, 1]
"""
pizza_sort_helper(________, ________)
def pizza_sort_helper(lst, start):
if _______________:
partial_reverse(________, ________)
partial_reverse(________, ________)
_______________(________, ________)
Use Ok to test your code:
python3 ok -q pizza_sort
Marvel in the genius that was Leonardo da Vinci!