for x in (0, 1, 2, 3, 4):
print(x)0
1
2
3
4Nonprimitive Data
Introduction to Software Engineering (CSSE 1001)
Iterating through Tuples
A tuple is an iterable object which means we can for-loop though them (like strings).
Comparing Tuples
(1, 2, 3) == (1, 2, 3) True(1, 2, 3) == (1, 2) False(1, 2, 3) < (1, 2, 4) True(1, 2, 3) < (1, 2) False(1, 2) < (1, 2, 3)
TrueTrueLists
A list is a mutable ordered collection of elements. These elements are not necessarily the same type and are not necessarily distinct.
Square brackets [] are used to create lists in Python.
xs = [1, "apple"]
type(xs)listAnd are indexable like strings.
xs[0]1Note that lists are mutable.
xs[0] = 2*xs[1]
xs[0]'appleapple'Looping Over Lists
xs = ['a', 2, 'c', 4, 'e']
for x in xs:
print(x) a
2
c
4
eComparison
[1,2,3] < [4,5,6] TruePoint-wise comparisons from position zero.
[7,2,3] < [4,5,6] False[] < [1] TrueMembership
1 in [1, 2, 3]True0 in [1, 2, 3] False123 in [1, 2, 3] False[1] in [1, 2, 3] FalseAppend
This is the original list updated.
xs = [0, 1, 2]
xs = xs + [3]
xs[0, 1, 2, 3]Alternatively, using a method that list provides…
xs = [0, 1, 2]
xs.append(3)
xs [0, 1, 2, 3]xs = [1, 2, 3]
xs.append([4,5])
xs [1, 2, 3, [4, 5]]Extend
xs = [1, 2, 3]
xs.extend([4,5]) Is code similar to.
xs = xs + [4, 5]List Aliasing
Take care when (trying to) copy lists.
xs = [1, 2, 3]
ys = xs
ys[-1] = 9ys[1, 2, 9]xs [1, 2, 9]Copying Lists
xs = [1, 2, 3]
ys = xs.copy()
ys[-1] = 9xs[1, 2, 3]ys [1, 2, 9]Passing Lists to Functions
A more nuanced case is when passing lists (but really list references) to functions.
def foo(ys):
ys[0] = -100xs = [1, 2, 3]
foo(xs)
xs [-100, 2, 3]List Aliasing
xs = [1, 2, 3]
ys = xs # ys is an alias of xs
xs.append(4) # Appending to a listys[1, 2, 3, 4]xs += [5] # Appending to a list
ys[1, 2, 3, 4, 5]xs = xs + [6] # Concatenating two lists
ys [1, 2, 3, 4, 5]Here the aliasing relationship broken!
Warning
Type-hinting lists is a new feature in Python 3.9 and greater.
def count(xs: list[int], ys: list[int]) -> int:
""" Return the number of times members of xs are in ys.
>>> count([1, 2], [1, 2, 3, 4])
2
>>> count([1, 2], [1, 2, 2, 2, 3, 1, 4])
5
"""def count(xs: list[int], ys: list[int]) -> int:
""" Count the number of times members of xs are in ys.
"""
ans = 0
for y in ys:
if y in xs:
ans += 1
return ans
# one-line (FP) solution
return sum(y in xs for y in ys)def make_unique(xs: list[int]) -> list[int]:
""" Returns the UNIQUE elements of xs.
>>> make_unique([1, 2, 3, 4])
[1, 2, 3, 4]
>>> make_unique([1, 2, 2, 2, 3, 1, 4, -3])
[1, 2, 3, 4, -3]
"""def make_unique(xs: list[int]) -> list[int]:
""" Return the list of UNIQUE elements of xs.
"""
ans = []
for x in xs:
if x not in ans:
ans.append(x)
return ansSlicing
xs = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
xs[3:6]
[3, 4, 5]
xs[::2]
[0, 2, 4, 6, 8]
xs[7:2:-2]
[7, 5, 3]We say the list
[0, 1, 2, 3, 4, 5]rotated by 2 is
[2, 3, 4, 5, 0, 1].Write a function
def rotate(xs: list, k: int) -> listthat rotates a list by k.
Range
Python’s range keyword allows us to quickly build an iterator for use by for-loops. It has the general form:
range([start], stop[, step])which is similar to list slicing. Note that square braces denote optional arguments.
range(10)range(0, 10)range(0, 10)range(0, 10)type(range(10)) rangelist(range(10)) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]list(range(2, 7)) [2, 3, 4, 5, 6]list(range(2, 7, 3)) [2, 5]list(range(2, 7, -1)) []list(range(7, 2, -1)) [7, 6, 5, 4, 3]range can be used to walk through lists using an index.
xs = [11, 22, 33, 44]
for k in range(len(xs)):
#Code involving xs[k]Enumerate
Python’s enumerate simplifies the pattern on the previous slide. Basically:
enumerate([x0, ..., xn]) = [(0, x0), ..., (n, xn)]However, this is not the full story — enumerate actually returns an iterable.
xs = [1, 2, 3, 4]
for k, xk in enumerate(xs):
#Code involving k and xk == xs[k]Note (0, x0) are immutable lists called tuples.
for k, x in enumerate(["Scientia", "ac", "Labore"]):
print(k,x)
Tip
UQ’s motto
Scientia ac Labore
translates to by means of knowledge and hard work.
Nesting For-Loops
(digits, alphas) = ["0", "1", "2"], ["x", "y"]
for d in digits:
for a in alphas:
print(d + a) 0x
0y
1x
1y
2x
2yNested Lists
A list can have another list as an element
xs = [ [1,2], [5,6,7] ]len(xs)2len(xs[-1]) 3Recall that loops can be nested.
xss = [ [1, 2], ["a", "b", "c"], "hello" ]
for xs in xss:
for x in xs:
print(x, end=' ') # Replaces newline with space.1 2 a b c h e l l o Matrices
Notice that a matrix can be represented by a list-of-lists in Python.
\[ \mathbb{A} = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \equiv [[1, 2, 3], [4, 5, 6], [7, 8, 9]] \]
ass = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ass[-1] [7, 8, 9]ass[1:3] [[4, 5, 6], [7, 8, 9]]ass[1][4, 5, 6]ass[1][-1]6ass[1,-1] TypeError: list indices must be integers or slices, not tupleDeep-Copy
ass = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
bss = ass.copy()
bss[0][0] = 0 bss[[0, 2, 3], [4, 5, 6], [7, 8, 9]]ass[[0, 2, 3], [4, 5, 6], [7, 8, 9]]This is because Python did a shallow-copy. For this to work we need a deep-copy, which is not built-in — see copy.deepcopy.
Converting Lists to Arguments
It is possible to “unbracket” a list when passing to functions.
def f(x, y, z):
return x + y + zx = [1, 2, 3]f(x)TypeError: f() missing 2 required positional arguments: 'y' and 'z'f(*x) 6Exercises
Exercise 1 Write a function
def transpose(ass: List[List[int]]) -> List[List[int]]:that returns the matrix transpose of \(\mathbb{A}\). Recall \[ \begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}^T = \begin{bmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{bmatrix} \] That is the columns and rows are swapped.
Exercise 2 (Caesar Cipher) A Caesar cipher is a type of encryption where each letter in the plaintext is ‘shifted’ a certain number of places down the alphabet to obtain the ciphertext.
For instance, with a shift of -2 we do \[ \begin{align*} A &\to Y \\ B &\to Z \\ C &\to A \\ &\; \vdots \\ Z &\to X \end{align*} \]
Write code for encrypting and decrypting messages using the Caesar cipher.
In particular, write functions with the headers
def encrypt_caeser(plaintext: str, shift: int) -> str:
def decrypt_caeser(ciphertext: str, shift: int) -> str:Summary
Tuples are immutable ordered collections whereas lists are mutable ordered collections.
Both can be sliced and indexed.
Dictionaries
Here is a deliberately vague task: Write a function that returns the character frequency of a string comprised only of lower case characters.
For example, the character frequency of “hello world” would encode that there is one “h”, three “l”s and so on.
What are some viable representations?
Two Lists
[ ['h', 'e', 'l', 'o', ' ', 'w', 'r', 'd'],
[1, 1, 3, 2, 1, 1, 1, 1] ]One-to-one Encoding
a b c d e f g h i j k l m n o p q r s t u v w x y z
[0,0,0,1,1,0,0,1,0,0,0,3,0,0,2,0,0,1,0,0,0,0,1,0,0,0]Hash Function
In both cases we provided a way to map a key (character) to a value (number). \[ \begin{align*} \text{str} &\to \text{int} \\ \text{h} &\mapsto 1 \\ \text{e} &\mapsto 1 \\ \text{k} &\mapsto 3 \\ &\;\; \vdots \end{align*} \] This mapping is called a hash function.
This is the hash-function for the two list encoding.
def hash_1(key:str, xs: list[str], ys: list[str]) -> int:
"""Two list encoding."""
k = xs.index(key) # position of key in xs
return ys[k]This is the hash function for the single list encoding.
def hash_2(key: str, xs: list[int]) -> int:
"""One-to-one encoding."""
pos_in_alpha = ord(key)-ord('a') # position of key in alphabet
return xs[pos_in_alpha]Generally speaking we can index a list by any type of key given some hash-function which takes keys to values.
Python has a magic hash function that will index anything appropriately. The result is implemented as the dict data-type.
Dictionaries
A dictionary in Python is a data-structure that stores tuple(key, value) pairings. Python has a “magic” hash function to find a key among the tuples fast.
The “hello world” example encoded using a dictionary is
>>> char_to_freq = {
'd': 1,
'o': 1,
' ': 1,
'r': 1,
'w': 1,
'e': 1,
'l': 3,
'h': 0
}Dictionaries have no ordering because the keys can be of mixed type but are mutable.
Hash tables are a candidate for the most important/useful data-structure in computer science.
Dictionary Methods
items
h = {
"red": ["apple", "firetrucks", "cars"],
"yellow": ["banana", "cars"],
"blue": ["sky", "cars"]
}h.items()dict_items([('red', ['apple', 'firetrucks', 'cars']), ('yellow', ['banana', 'cars']), ('blue', ['sky', 'cars'])])values
h = {
"red": ["apple", "firetrucks", "cars"],
"yellow": ["banana", "cars"],
"blue": ["sky", "cars"]
}h.values() dict_values([['apple', 'firetrucks', 'cars'], ['banana', 'cars'], ['sky', 'cars']])keys
h = {
"red": ["apple", "firetrucks", "cars"],
"yellow": ["banana", "cars"],
"blue": ["sky", "cars"]
}h.keys() dict_keys(['red', 'yellow', 'blue'])h["blue"] ['sky', 'cars']h["green"]KeyError: 'green'The following is fine because we are assigning not retrieving.
h["green"] = ["leaves"] clear & copy
h = {
"red": ["apple", "firetrucks", "cars"],
"yellow": ["banana", "cars"],
"blue": ["sky", "cars"]
}
f = h.copy()
h.clear()h["blue"] KeyError: 'blue'f["blue"] ['sky', 'cars']copy
h = {
"red": ["apple", "firetrucks", "cars"],
"yellow": ["banana", "cars"],
"blue": ["sky", "cars"]
}
f = h.copy()h["blue"].append("windex")
h["blue"]['sky', 'cars', 'windex']Shallow copy.
f["blue"] ['sky', 'cars', 'windex']get
h = {
"red": ["apple", "firetrucks", "cars"],
"yellow": ["banana", "cars"],
"blue": ["sky", "cars"]
}h.get("red") ['apple', 'firetrucks', 'cars']h["green"] KeyError: 'green'Safer because no error is thrown here
h.get("green") Without Methods
A dictionary is an iterable. When used in a for loop the loop will walk through the keys of the dictionary.
table = {'a': 1, 'b': 2, 'c': 3}for key in table:
value = table[key]
print(key, value)a 1
b 2
c 3One may also avoid key errors using an if-statement.
if key in table:
table[key] += 1
else:
table[key] = 0
Warning
The keys of a dictionary must be an immutable type.
d = dict()d[ [1,2,3] ] = 1TypeError: unhashable type: 'list'Tuples are immutable
d[ (1,2,3) ] = 1Dictionaries are mutable.
h = dict()
d[ h ] = 1TypeError: unhashable type: 'dict'Exercises
Exercise 3 Write a function that when given a string, returns a dictionary whose keys are characters and values are the positions of these characters in the string.
def char_index(xs: str) -> dict[str, list[int]]:
"""
>>> char_index("")
{}
>>> char_index("aaAAbbBB")
{'a': [0, 1], 'b': [4, 5], 'A': [2, 3], 'B': [6, 7]}
"""Exercise 4 Complete the following function.
def combine( d1: dict[int, list[int]],
d2: dict[int, list[int]] ) -> dict[int, int]:
"""Return the dictionary where each key is a key that is in both d1
and d2.
The value associated with each key in the new dictionary is the sum
of all the integers associated with that key in d1 and d2.
>>> combine({1: [2], 4: [5, 6]}, {4: [8]})
{4: 19}
"""Exercise 5 Write a function with the following contract that does a reverse lookup.
def reverse_lookup(d: dict, item) -> list:
"""Returns all keys such that d[keys] == item
Precondition:
item is immutable.
>>> reverse_lookup({1:'bluey', 19:'chilli', -31:'bluey'}, 'bluey')
[1, -31]
>>> reverse_lookup({1:'bluey', 19:'chilli', -31:'bluey'}, 'muffin')
[]
"""Exercise 6 Write a function which inverts the keys and items of a dictionary.
Note: Since there may be many identical values, we will have to map those to lists of keys.
def invert(d: dict) -> dict:
"""Return the inverted version of d.
>>> invert({1: 10, 2: 10})
{10: [1, 2]}
"""Summary
Dictionaries are for storing key-value relationships. A key must be an immutable type and gets mapped to a value using a hash-function that is magically fast.