Week 6: Notes

conditional expressions

In Python, you may use if and else inside an expression; this is called a conditional expression.

For example, consider this code:

if x > 100:
    print('x is big')
else:
    print('x is not so big')

We may rewrite it using a conditional expression:

print('x is ' + ('big' if x > 100 else 'not so big'))

As another example, here is a function that takes two integers and returns whichever has the greater magnitude (i.e. absolute value):

def greater(i, j):
   if abs(i) >= abs(j):
       return i
   else:
       return j

We can rewrite it using a conditional expression:

def greater(i, j):
    return i if abs(i) >= abs(j) else j

A conditional expression always has the form

expression if condition else expression

The keyword else must always be present (unlike in an ordinary if statement).

(If you already know C or another C-like language, you may notice this feature's resemblance to the ternary operator (? :) in those languages.)

file input/output

The open() function opens a file. It takes two parameters: a filename plus an optional mode string, which can contain one or more of these characters:

If you don't specify a mode string, the file will be opened for reading in text mode.

When you open a file in text mode, Python will perform universal newline translation, i.e. translate any sort of newlines to '\n'. We will only use text mode in this course.

open() returns a file object. When reading, the file object is iterable: you can loop over it with for to receive a sequence of lines, just like with sys.stdin. When a file is opened for writing, you may write lines to the file by calling the write() method on the file object once for each output line.

When we are finished reading or writing data, you should call close() to close the file.

Here's a program that opens two files called 'input.txt' and 'output.txt'. It reads lines from the input file and writes them to the output file, duplicating every line as it writes:

input = open('input.txt', 'r')    # open for reading ('r' is default mode)
output = open('output.txt', 'w')     # open for writing

for line in input:
    output.write(line)      # write line to output
    output.write(line)      # write it again

input.close()
output.close()

You can read about more methods for input and output in our Python quick library reference.

The with statement

Whenever you open a file, you'll want to close it, even if your program exits unexpectedly with an error. Python has a special statement that makes this easy. The with statement assigns a file object (or other resource) to a variable, then runs a block of code. When the block of code exits for any reason, the object is automatically closed, just as if you had called close() on the object.

Let's rewrite the previous program using 'with':

with open('input.txt', 'r') as input:    # open for reading ('r' is default mode)
    with open('output.txt', 'w') as output:     # open for writing
        for line in input:
            output.write(line)      # write line to output
            output.write(line)      # write it again

It's good practice to use 'with' whenever you open a file, to ensure that the file will be closed even if the program exits with an error.

In fact with also works with other types of objects that need to be closed, such as network sockets. We may see some of these later in this course.

command-line arguments

When we run a program from the command line, we may specify command-line arguments. For example:

$ python prog.py hello one two three

In a Python program, sys.argv holds a list of all command-line arguments. Actually the first element in the list is the name of the program itself, and subsequent elements hold the arguments. For example, suppose that prog.py holds this program:

import sys

print(sys.argv)

Let's run it:

$ python3 prog.py hello one two three
['prog.py', 'hello', 'one', 'two', 'three']

As an example, let's write a program that imitates the Unix utility 'wc' ("word count"), which prints out the number of lines, words, and characters in a file:

import sys

if len(sys.argv) != 2:
    print(f'usage: {sys.argv[0]} <filename>')
    exit()

filename = sys.argv[1]
chars = words = lines = 0

with open(filename) as f:
    for line in f:
        chars += len(line)
        words += len(line.split())
        lines += 1

print(f'{lines} lines, {words} words, {chars} chars')

Notice that the program prints out a usage message if we attempt to invoke it without arguments. This is a good practice:

$ python wc.py
usage: wc.py <filename>

Let's use the program to count the lines, words and characters in its own source code:

$ python wc.py wc.py
16 lines, 43 words, 324 chars

This matches the counts printed by the Unix wc utility itself:

$ wc wc.py
 16  43 324 wc.py

Command-line programs will often accept arguments with names beginning with a hyphen, such as -d or ‑e. Typically these denote options that affect a program's behavior.

As another example, let's implement a simple variant of the Unix utility 'grep', which searches for a string in a given file, and prints out all lines containing the string. Our program will accept two options:

Here's the program:

import sys

def usage():
    print(f'usage: {sys.argv[0]} [-i] [-v] <string> <filename>')
    exit()

insensitive = invert = False

i = 1
while i < len(sys.argv):
    arg = sys.argv[i]
    if arg.startswith('-'):
        if arg == '-i':
            insensitive = True
        elif arg == '-v':
            invert = True
        else:
            usage()
    else:
        break    # end of options
    i += 1

if len(sys.argv) - i < 2:
    usage()

find = sys.argv[i]
if insensitive:
    find = find.lower()
filename = sys.argv[i + 1]

with open(filename) as f:
    for line in f:
        line = line.rstrip()
        if insensitive:
            line = line.lower()
        match = find in line
        if (match and not invert) or (not match and invert):
            print(line)

Let's use it to find all lines containing "sys" in the program's own source code:

$ python grep.py -i sys grep.py
import sys
    print(f'usage: {sys.argv[0]} [-i] [-v] <string> <filename>')
while i < len(sys.argv):
    arg = sys.argv[i]
if len(sys.argv) - i < 2:
find = sys.argv[i]
filename = sys.argv[i + 1]

sets

A set in Python is a useful built-in data structure that represents a mutable set of values. The function set() returns an empty set:

>>> set()
set()

Alternatively, you may construct a set of values by listing them within braces:

>>> s = {3, 5, 10}

By the way, do not attempt to create an empty set by writing '{}'. That is an empty dictionary, not a set! (We will discuss dictionaries below.)

We may add a value to a set using the add() method. If the value is already present, the call does nothing:

>>> s.add(4)
>>> s
{10, 3, 4, 5}
>>> s.add(4)
>>> s
{10, 3, 4, 5}

The remove() method removes a value from a set. If it's not present, Python will report an error:

>>> s.remove(5)
>>> s
{10, 3, 4}
>>> s.remove(5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 5

The 'in' operator tests whether a value is present in a set:

>>> s = { 'red', 'green', 'yellow', 'turquoise' }
>>> 'yellow' in s
True
>>> 'purple' in s
False

All of these operations are efficient: add(), remove(), and 'in' will run in O(1) on average. For this reason, a set is sometimes a better choice of data structure than a list, especially in situations when we want to be able to quickly test whether an element is present.

However, be aware that sets are unordered. In other words, the values in a set are not in any particular order, and you cannot access values by index:

>>> s = { 'red', 'green', 'yellow', 'turquoise' }
>>> s[2]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'set' object is not subscriptable

Python will print a set's values in an arbitrary order, unrelated to the order in which values were added:

>>> s = set()
>>> s.add(5)
>>> s.add(2)
>>> s.add(10)
>>> s
{2, 10, 5}

Sets are iterable, meaning that you can use a 'for' statement to loop over a set's values (in some arbitrary order):

>>> s = { 'red', 'green', 'yellow', 'turquoise' }
>>> for c in s:
...   print(c)
... 
green
turquoise
red
yellow

Note that every value in a set must be immutable. So you cannot create a set of lists, for example:

>>> s = { [1, 2, 3], [6, 5, 8], [10, 11, 12] }
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

However, a set of tuples will work fine, since tuples are immutable:

>>> s = { (1, 2, 3), (6, 5, 8), (10, 11, 12) }
>>> s
{(6, 5, 8), (1, 2, 3), (10, 11, 12)}
>>>

Python provides handy operators for performing Boolean operations on sets. The '&', '|', and '-' operators compute the intersection, union, or difference of two sets:

>>> s = { 5, 8, 2, 10, 3, 6, 12 }
>>> t = { 8, 77, 3, 14, 12 }
>>> s & t
{8, 3, 12}
>>> s | t
{2, 3, 5, 6, 8, 10, 12, 77, 14}
>>> s - t
{2, 10, 5, 6}

The set operators 's <= t' and 's >= t' test whether s is a subset or superset of t, respectively:

>>> s = { 2, 4, 6 }
>>> t = { 1, 2, 3, 4, 5, 6, 8 }
>>> s <= t
True
>>> t <= s
False

For more information about built-in operators and functions that work on sets, see our quick library reference.

dictionaries

A dictionary is a built-in Python data type that represents a mutable map from keys to values. Dictionaries are useful in many situations.

Here's a dictionary that maps the names of some animals in English to their Czech equivalents:

>>> d = {'cat' : 'kočka', 'dog' : 'pes', 'guinea pig' : 'morče'}

The keys in this dictionary are the strings 'cat', 'dog' and 'guinea pig'. The corresponding values are 'kočka', 'pes' and 'morče'. Notice that each key and its value are separated by a colon (':') in the declaration above.

We may look up the value for any key:

>>> d['dog']
'pes'
>>> d['guinea pig']
'morče'

We can use an assignment to add a new key/value pair to the dictionary:

>>> d['cow'] = 'kráva'
>>> d
{'cat': 'kočka', 'dog': 'pes', 'guinea pig': 'morče', 'cow': 'kráva'}

We may use the same syntax to replace the value at any key:

>>> d['cat'] = 'gato'
>>> d
{'cat': 'gato', 'dog': 'pes', 'guinea pig': 'morče', 'cow': 'kráva'}

The del statement will delete a key and its value from a dictionary:

>>> del d['dog']
>>> d
{'cat': 'gato', 'guinea pig': 'morče', 'cow': 'kráva'}

The in operator tests whether a key is present in a dictionary:

>>> 'guinea pig' in d
True
>>> 'horse' in d
False

All of these operations are efficient. Looking up a key's value, replacing a key's value, deleting a key, and testing for a key will all run in O(1) on average.

Notice that all keys in a dictionary are unique. Values, however, may be repeated. Also note that dictionaries are indexed by key, but not by value. In other words, you can quickly look up the value for any key, but if you want to know whether a particular value is present in the dictionary, you must scan the entire dictionary, which takes O(N).

Python provides methods that let us conveniently access the keys and values in a dictionary. First, d.keys() returns an iterable object containing all keys in the dictionary. You can iterate over this object using 'for', or convert it to a list:

>>> d = {'cat' : 'kočka', 'dog' : 'pes', 'guinea pig' : 'morče'}
>>> for k in d.keys():
        print(k)
cat
dog
guinea pig
>>> list(d.keys())
['cat', 'dog', 'guinea pig']

Similarly, d.values() lists all values in a dictionary. Another helpful method is d.items(), which is an iterable of key‑value pairs:

>>> list(d.items())
[('cat', 'kočka'), ('dog', 'pes'), ('guinea pig', 'morče')]

Recall that in a 'for' statement we may use pattern matching to assign to multiple variables on each loop iteration:

>>> for x, y in [(1, 2), (3, 4), (5, 6)]:
         print(x + y)
3
7
11

And so we may conveniently use pattern matching to loop over the keys and values of a dictionary simultaneously:

>>> d
{'cat': 'kočka', 'dog': 'pes', 'guinea pig': 'morče'}
>>> for key, value in d.items():
        print(f'key = {key}, value = {value}')
key = cat, value = kočka
key = dog, value = pes
key = guinea pig, value = morče

Note that dictionary keys, like values in a set, must be immutable. So you can't create a dictionary whose keys are lists:

>>> d = { [1, 2, 3]: 7, [5, 3, 2]: 8 }
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

However, tuples will work fine as dictionary keys:

>>> d = { (1, 2, 3): 7, (5, 3, 2): 8 }

See our quick library reference for more information about built-in operators and functions that work on dictionaries.

counting words

As an example of the practical utility of dictionaries, suppose that we'd like to determine which words in a file appear the most times. For example, here is the entire text of the classic novel War and Peace. Let's write a program to read the text and print out its most common words. We'll only consider words with at least 5 letters, since shorter common words (e.g. 'the', 'a') are not usually so interesting.

We'll assume that the text is in a file 'war_and_peace'. We'll read the file and construct a dictionary that maps each word to its count. After that, we'll extract a list of pairs (count, word) from the dictionary. Then we'll sort the list. Python orders tuples lexicographically, so that will sort by count since the count appears first in each pair.

Here is the program:

f = open('war_and_peace')

count = {}

for line in f:
    words = line.strip().split()
    for w in words:
        if len(w) >= 5:
            if w in count:
                count[w] += 1
            else:
                count[w] = 1

# Extract a list of pairs.
pairs = []
for word, n in count.items():
    pairs.append( (n, word) )

pairs.sort(reverse = True)

for n, word in pairs[:10]:
    print(f'{word}: {n}')

Let's run it:

$ py words.py
which: 1924
Prince: 1499
their: 1407
would: 1333
Pierre: 1260
could: 1090
about: 908
there: 895
CHAPTER: 730
Andrew: 700

recursion

A recursive function calls itself. Recursion is a powerful technique that can help us solve many problems.

When we solve a problem recursively, we express its solution in terms of smaller instances of the same problem. The idea of recursion is fundamental in mathematics as well as in computer science.

As a first example, suppose we we'd like to write a function that computes n! for any positive integer n. Recall that

n! = n · (n – 1) · … · 3 · 2 · 1

We may write this function iteratively, i.e. using a loop:

def factorial_iter(n):
    p = 1

    for i in range(1, n + 1):
        p *= i

    return p

Alternatively, we can rewrite this function using recursion. Now it calls itself:

def factorial(n):
    if n == 0:
        return 1     # 0! is 1
    
    return n * factorial(n - 1)

Whenever we write a recursive function, there is a base case and a recursive case.

The base case is an instance that we can solve immediately. In the function above, the base case is when n == 0. A recursive function must always have a base case – otherwise it would loop forever since it would always call itself!

In the recursive case, a function calls itself, passing it a smaller instance of the given problem. Then it uses the return value from the recursive call to construct a value that it itself can return.

In the recursive case in this example, we recursively call factorial(n - 1). We then multiply its return value by n, and return that value. That works because

n! = n · (n – 1)! whenever n ≥ 1

(In fact, we may treat this equation as a recursive definition of the factorial function, mathematically speaking.)

How does this function work, exactly? Suppose that we call factorial(3). It will call factorial(2), which calls factorial(1), which calls factorial(0). The call stack in memory now looks like this:

factorial(3)
→ factorial(2)
  → factorial(1)
    → factorial(0)

Now

We see that given any n, the function returns the sum 1 * 2 * 3 * … * n = n!.

We have seen that we can write the factorial function either iteratively (i.e. using loops) or recursively. In theory, any function can be written either iteratively or recursively. We will see that for some problems a recursive solution is easy and an iterative solution would be quite difficult. Conversely, some problems are easier to solve iteratively. Python lets us write functions either way.

Here is some general advice for writing a recursive function. First look for a base case where the function can return immediately. (In some problems there will actually be more than one base case.) Now you need to write the recursive case, where the function calls itself. At this point you may wish to pretend that the function "already works". Write the recursive call and believe that it will return a correct solution to a subproblem, i.e. a smaller instance of the problem. Now you must somehow transform that subproblem solution into a solution to the entire problem, and return it. This is really the key step: understanding the recursive structure of the problem, i.e. how a solution can be derived from a subproblem solution.

more recursive examples

Here's another example. Consider this implementation of Euclid's algorithm that we saw in Introduction to Algorithms:

# gcd, iteratively
def gcd(a, b):
    while b > 0:
        a, b = b, a % b

    return a

We can rewrite this function using recursion:

# gcd, recursively
def gcd(a, b):
    if b == 0:
        return a

    return gcd(b, a % b)

Broadly speaking, we will see that "easy" recursive functions such as gcd call themselves only once, and it would be straightforward to write them either iteratively or recursively. Soon (in our algorithms class) we will see recursive functions that call themselves two or more times. Those functions will let us solve more difficult tasks that we could not easily solve iteratively.

Here is another example of a recursive function:

def hi(x):
    if x == 0:
        print('hi')
        return
    
    print('start', x)
    hi(x - 1)
    print('done', x)

If we call hi(3), the output will be

start 3
start 2
start 1
hi
done 1
done 2
done 3

Be sure you understand why the lines beginning with 'done' are printed. hi(3) calls hi(2), which calls hi(1), which calls hi(0). At the moment that hi(0) runs, all of these function invocations are active and are present in memory on the call stack:

hi(3)
→ hi(2)
  → hi(1)
    → hi(0)

Each function invocation has its own value of the parameter x. (If this procedure had local variables, each invocation would have a separate set of variable values as well.)

When hi(0) returns, it does not exit from this entire set of calls. It returns to its caller, i.e. hi(1). hi(1) now resumes execution and writes 'done 1'. Then it returns to hi(2), which writes 'done 2', and so on.