We've provided a set of starter files with skeleton code for the exercises in the lab. You can get them in the following places:
Previously, we had dealt with tuples, which are immutable sequences. Python has built-in lists, which are mutable. This means you can modify lists without creating entirely new ones. Lists have state, unlike tuples.
Just like with tuples, you can use slicing notation with lists. In addition, not only can retrieve a slice from a list, you can also assign to a slice of a list. This is possible because lists are mutable.
What does Python print? Think about these before typing it into an interpreter!
>>> lst = [1, 2, 3, 4, 5, 6]
>>> lst[4] = 1
>>> lst
_________
>>> lst[2:4] = [9, 8]
>>> lst
_________
>>> lst[3] = ['hi', 'bye']
>>> lst
_________
>>> lst[3:] = ['jom', 'magrotker']
>>> lst
_________
>>> lst[1:3] = [2, 3, 4, 5, 6, 7, 8]
>>> lst
_________
>>> lst == lst[:]
_________
>>> lst is lst[:]
_________
>>> a = lst[:]
>>> a[0] = 'oogly'
>>> lst
_________
>>> lst = [1, 2, 3, 4]
>>> b = ['foo', 'bar']
>>> lst[0] = b
>>> lst
_________
>>> b[1] = 'ply'
>>> lst
_________
>>> b = ['farply', 'garply']
>>> lst
_________
>>> lst[0] = lst
>>> lst
_________
>>> lst[0][0][0][0][0]
_________
Python has a list class that contains many useful methods. Using the
builtin dir() function will show you all of them, like so:
dir(list)
Some of the most common methods include append(), extend(), and
pop().
>>> l = [3, 5, 6]
>>> l.append(10) # adds an element to the end
>>> l
[3, 5, 6, 10]
>>> l.extend([-1, -6]) # concatenates another list to the end
>>> l
[3, 5, 6, 10, -1, -6]
>>> l.pop() # removes and returns the last element
-6
>>> l
[3, 5, 6, 10, -1]
>>> l.pop(2) # removes and returns the element at the index given
6
>>> l
[3, 5, 10, -1]
Try to solve the following list problems with mutation. This means that each function should mutate the original list. In other words:
>>> original_list = [5, -1, 29, 0]
>>> function(original_list) # doesn't return anything
>>> original_list
# mutated list here
Prioritize solving these problems with iteration, but for extra practice, also solve them using recursion. Remember: these functions should NOT return anything. This is to emphasize that these functions should utilize mutability.
Write a function that reverses the given list.
def reverse(lst):
"""Reverses lst using mutation.
>>> original_list = [5, -1, 29, 0]
>>> reverse(original_list)
>>> original_list
[0, 29, -1, 5]
"""
Write a function that maps a function on the given list.
def map(fn, lst):
"""Maps fn onto lst using mutation.
>>> original_list = [5, -1, 2, 0]
>>> map(lambda x: x * x, original_list)
>>> original_list
[25, 1, 4, 0]
"""
Write a function that filters a list, only keeping elements that satisfy the predicate.
def filter(pred, lst):
"""Filters lst with pred using mutation.
>>> original_list = [5, -1, 2, 0]
>>> filter(lambda x: x % 2 == 0, original_list)
>>> original_list
[2, 0]
"""
So far, we've covered lists, a powerful, mutable data structure that supports various operations including indexing and slicing. Similar to the generator expressions you've seen previously, lists can be created using a syntax called "list comprehension." Using a list comprehension is very similar to using the map or filter functions, but will return a list as opposed to a filter or map object.
>>> [i**2 for i in (1, 2, 3, 4) if i%2 == 0]
[4, 16]
is equivalent to
>>> lst = []
>>> for i in (1, 2, 3, 4):
... if i % 2 == 0:
... lst.append(i**2)
>>> lst
[4, 16]
List comprehensions allow you to apply map and filter at the same time, in very compact syntax. The general syntax for a list comprehension is
[<expression> for <element> in <sequence> if <conditional>]
The syntax is designed to read like English: "Compute the expression for each element in the sequence if the conditional is true."
Implement a function coords, which takes a funciton, a sequence, and
an upper and lower bound on output of the function. coords then
returns a list of x, y coordinate pairs (tuples) such that:
See the doctest if you are still confused.
One other thing: your answer can only be one line long. You should make use of list comprehensions!
def coords(fn, seq, lower, upper):
"""
>>> seq = (-4, -2, 0, 1, 3)
>>> fn = lambda x: x**2
>>> coords(fn, seq, 1, 9)
[(-2, 4), (1, 1), (3, 9)]
"""
return _______________
To practice, write a function that adds two matrices together using generator expression(s). The function should take in two 2D lists of the same dimensions.
def add_matrices(x, y):
"""
>>> add_matrices([[1, 3], [2, 0]], [[-3, 0], [1, 2]])
[[-2, 3], [3, 2]]
"""
return ________________
Now write a list comprehension that will create a deck of cards. Each element in the list will be a card, which is represented by a tuple containing the suit as a string and the value as an int.
def deck():
return ________________
Python also includes a powerful sort method. It can also take a
key function that tells sort how to actually sort the objects. For
more information, look at
Python's documentation for the sort method
Note that sort is a stable sort. Now, use the sort method to
sort a shuffled deck. It should put cards of the same suit together,
and also sort each card in each suit in increasing value.
def sort_deck(deck):
"*** YOUR CODE HERE ***"
First, let's talk about dictionaries. Dictionaries are simple an unordered set of key-value pairs. To create a dictionary, use the following syntax:
>>> webster = {'Shawn': 'pineapple', 'Kim': 'blueberry'}
The curly braces denote the key-value pairs in your dictionary. Each key-value pair is separated by a coma, and for each pair the key appears to the left of the colon and the value appears to the right of the colon. You can retrieve values from your dictionary by 'indexing' using the key:
>>> webster['Shawn']
'pineapple'
>>> webster['Kim']
'blueberry'
You can modify an entry for an existing key in the dictionary using the following syntax. Adding a new key follows identical syntax!
>>> webster['Shawn'] = 'strawberry'
>>> webster['Shawn']
'strawberry'
>>> webster['Carlton'] = 'donut' # new entry!
>>> webster['Carlton']
'donut
Now that you know how dictionaries work, we can move on to our next step -- approximating the entire works of Shakespeare! We're going to use a bigram language model. Here's the idea: We start with some word -- we'll use "The" as an example. Then we look through all of the texts of Shakespeare and for every instance of "The" we record the word that follows "The" and add it to a list, known as the successors of "The". Now suppose we've done this for every word Shakespeare has used, ever.
Let's go back to "The". Now, we randomly choose a word from this list, say "cat". Then we look up the successors of "cat" and randomly choose a word from that list, and we continue this process. This eventually will terminate in a period (".") and we will have generated a Shakespearean sentence!
The object that we'll be looking things up in is called a "successor table", although really it's just a dictionary. The keys in this dictionary are words, and the values are lists of successors to those words.
Here's an incomplete definition of the build_successors_table
function. The input is a list of words (corresponding to a
Shakespearean text), and the output is a successors table. (By
default, the first word is a successor to "."). See the example below:
def build_successors_table(tokens):
"""Return a dictionary: keys are words; values are lists of
successors.
>>> text = ['We', 'came', 'to', 'investigate', ',', 'catch', 'bad', 'guys', 'and', 'to', 'eat', 'pie', '.']
>>> table = build_successors_table(text)
>>> table
{'and': ['to'], 'We': ['came'], 'bad': ['guys'], 'pie': ['.'], ',': ['catch'], '.': ['We'], 'to': ['investigate', 'eat'], 'investigate': [','], 'catch': ['bad'], 'guys': ['and'], 'eat': ['pie'], 'came': ['to']}
"""
table = {}
prev = '.'
for word in tokens:
if prev in table:
"***YOUR CODE HERE ***"
else:
"***YOUR CODE HERE ***"
prev = word
return table
Let's generate some sentences! Suppose we're given a starting word. We can look up this word in our table to find its list of successors, and then randomly select a word from this list to be the next word in the sentence. Then we just repeat until we reach some ending punctuation.
Hint: to randomly select from a list, first make sure you import the
Python random library with import random and then use the expression
random.choice(my_list))
This might not be a bad time to play around with adding strings
together as well. Let's fill in the construct_sent function!
def construct_sent(word, table):
"""Prints a random sentence starting with word, sampling from
table.
"""
import random
result = ''
while word not in ['.', '!', '?']:
"***YOUR CODE HERE ***"
return result + word
Great! Now all that's left is to run our functions with some actual code. The following snippet included in the skeleton code will return a list containing the words in all of the works of Shakespeare.
Warning: do NOT try to print the return result of this function):
def shakespeare_tokens(path = 'shakespeare.txt', url = 'http://goo.gl/SztLfX'):
"""Return the words of Shakespeare's plays as a list"""
import os
from urllib.request import urlopen
if os.path.exists(path):
return open('shakespeare.txt', encoding='ascii').read().split()
else:
shakespeare = urlopen(url)
return shakespeare.read().decode(encoding='ascii').split()
Next, we probably want an easy way to refer to our list of tokens and our successors table. Let's make the following assignments:
>>> tokens = shakespeare_tokens()
>>> table = build_successors_table(tokens)
Finally, let's define an easy to call utility function:
>>> def sent():
return construct_sent('The', table)
>>> sent()
' The plebeians have done us must be news-cramm'd '
>>> sent()
' The ravish'd thee , with the mercy of beauty '
>>> sent()
' The bird of Tunis , or two white and plucker down with better ; that's God's sake '
Now, if we want to start the sentence with a random word, we can use the folowing:
>>> def random_sent():
import random
return construct_sent(random.choice(table['.']), table)
>>> random_sent()
' You have our thoughts to blame his next to be praised and think ?'
>>> random_sent()
' Long live by thy name , then , Dost thou more angel , good Master Deep-vow , And tak'st more ado but following her , my sight Of speaking false !'
>>> random_sent()
' Yes , why blame him , as is as I shall find a case , That plays at the public weal or the ghost .'