10-tuples.tex

% LaTeX source for ``Python for Informatics: Exploring Information''
% Copyright (c)  2010-  Charles R. Severance, All Rights Reserved

\chapter{Tuples}
\label{tuplechap}

\section{Tuples are immutable}

\index{tuple}
\index{type!tuple}
\index{sequence}

A tuple\footnote{Fun fact: The word ``tuple'' comes from the names
given to sequences of numbers of varying lengths: single, 
double, triple, quadruple, quituple, sextuple, septuple, etc.}
is a sequence of values much like a list.  
The values stored in a tuple can be any type, and
they are indexed by integers.
The important difference is that tuples are {\bf immutable}.
Tuples are also {\bf comparable} and {\bf hashable} so we can 
sort lists of them and use tuples as key values in Python
dictionaries.

\index{mutability}
\index{hashable}
\index{comparable}
\index{immutability}

Syntactically, a tuple is a comma-separated list of values:

\beforeverb
\begin{verbatim}
>>> t = 'a', 'b', 'c', 'd', 'e'
\end{verbatim}
\afterverb
%
Although it is not necessary, it is common to enclose tuples in
parentheses to help us quickly identify tuples when we look at
Python code:

\index{parentheses!tuples in}

\beforeverb
\begin{verbatim}
>>> t = ('a', 'b', 'c', 'd', 'e')
\end{verbatim}
\afterverb
%
To create a tuple with a single element, you have to include the final
comma:

\index{singleton}
\index{tuple!singleton}

\beforeverb
\begin{verbatim}
>>> t1 = ('a',)
>>> type(t1)
<type 'tuple'>
\end{verbatim}
\afterverb
%
Without the comma Python treats \verb"('a')" as an expression 
with a string in parentheses that evaluates to a string:

\beforeverb
\begin{verbatim}
>>> t2 = ('a')
>>> type(t2)
<type 'str'>
\end{verbatim}
\afterverb
%
Another way to construct a tuple is the built-in function {\tt tuple}.
With no argument, it creates an empty tuple:

\index{tuple function}
\index{function!tuple}

\beforeverb
\begin{verbatim}
>>> t = tuple()
>>> print t
()
\end{verbatim}
\afterverb
%
If the argument is a sequence (string, list or tuple), the result
of the call to {\tt tuple}
is a tuple with the elements of the sequence:

\beforeverb
\begin{verbatim}
>>> t = tuple('lupins')
>>> print t
('l', 'u', 'p', 'i', 'n', 's')
\end{verbatim}
\afterverb
%
Because {\tt tuple} is the name of a constructor, you should
avoid using it as a variable name.

Most list operators also work on tuples.  The bracket operator
indexes an element:

\index{bracket operator}
\index{operator!bracket}

\beforeverb
\begin{verbatim}
>>> t = ('a', 'b', 'c', 'd', 'e')
>>> print t[0]
'a'
\end{verbatim}
\afterverb
%
And the slice operator selects a range of elements.

\index{slice operator}
\index{operator!slice}
\index{tuple!slice}
\index{slice!tuple}

\beforeverb
\begin{verbatim}
>>> print t[1:3]
('b', 'c')
\end{verbatim}
\afterverb
%
But if you try to modify one of the elements of the tuple, you get
an error:

\index{exception!TypeError}
\index{TypeError}
\index{item assignment}
\index{assignment!item}

\beforeverb
\begin{verbatim}
>>> t[0] = 'A'
TypeError: object doesn't support item assignment
\end{verbatim}
\afterverb
%
You can't modify the elements of a tuple, but you can replace
one tuple with another:

\beforeverb
\begin{verbatim}
>>> t = ('A',) + t[1:]
>>> print t
('A', 'b', 'c', 'd', 'e')
\end{verbatim}
\afterverb
%

\section{Comparing tuples}

\index{comparison!tuple}
\index{tuple!comparison}
\index{sort method}
\index{method!sort}

The comparison operators work with tuples and other sequences;
Python starts by comparing the first element from each
sequence.  If they are equal, it goes on to the next element,
and so on, until it finds elements that differ.  Subsequent
elements are not considered (even if they are really big).

\beforeverb
\begin{verbatim}
>>> (0, 1, 2) < (0, 3, 4)
True
>>> (0, 1, 2000000) < (0, 3, 4)
True
\end{verbatim}
\afterverb
%
The {\tt sort} function works the same way.  It sorts 
primarily by first element, but in the case of a tie, it sorts
by second element, and so on.  

This feature lends itself to a pattern called {\bf DSU} for 

\begin{description}

\item[Decorate] a sequence by building a list of tuples
with one or more sort keys preceding the elements from the sequence,

\item[Sort] the list of tuples using the Python built-in {\tt sort}, and

\item[Undecorate] by extracting the sorted elements of the sequence.

\end{description}

\label{DSU}
\index{DSU pattern}
\index{pattern!DSU}
\index{decorate-sort-undecorate pattern}
\index{pattern!decorate-sort-undecorate}
\index{Romeo and Juliet}

For example, suppose you have a list of words and you want to
sort them from longest to shortest:

\beforeverb
\begin{verbatim}
txt = 'but soft what light in yonder window breaks'
words = txt.split()
t = list()
for word in words:
   t.append((len(word), word))

t.sort(reverse=True)

res = list()
for length, word in t:
    res.append(word)

print res
\end{verbatim}
\afterverb
%
The first loop builds a list of tuples, where each
tuple is a word preceded by its length.

{\tt sort} compares the first element, length, first, and
only considers the second element to break ties.  The keyword argument
{\tt reverse=True} tells {\tt sort} to go in decreasing order.

\index{keyword argument}
\index{argument!keyword}
\index{traversal}

The second loop traverses the list of tuples and builds a list of
words in descending order of length.  So among the five character words,
they are sorted in {\em reverse} alphabetical order.  So ``what'' appears
before ``soft'' in the following list.

The output of the program is as follows:
%
\beforeverb
\begin{verbatim}
['yonder', 'window', 'breaks', 'light', 'what', 
'soft', 'but', 'in']
\end{verbatim}
\afterverb
%
Of course the line loses much of its poetic impact 
when turned into a Python list and sorted in 
descending word length order.

\section{Tuple assignment}
\label{tuple assignment}

\index{tuple!assignment}
\index{assignment!tuple}
\index{swap pattern}
\index{pattern!swap}

One of the unique syntactic features of the Python language
is the ability to have a tuple on the left hand
side of an assignment statement.  This allows you to assign
more than one variable at a time when the left hand side is a 
sequence.

In this example we have a two element list (which is a sequence) and
assign the first and second elements of the sequence
to the variables {\tt x} and {\tt y} in a single statement.

\beforeverb
\begin{verbatim}
>>> m = [ 'have', 'fun' ]
>>> x, y = m
>>> x
'have'
>>> y
'fun'
>>> 
\end{verbatim}
\afterverb
%
It is not magic, Python \emph{roughly} translates the 
tuple assignment syntax
to be the following:\footnote{Python does not translate the 
syntax literally.  For example if you try this with a dictionary
it will not work as might expect.}

\beforeverb
\begin{verbatim}
>>> m = [ 'have', 'fun' ]
>>> x = m[0]
>>> y = m[1]
>>> x
'have'
>>> y
'fun'
>>> 
\end{verbatim}
\afterverb

Stylistically when we use a tuple on the left hand side of the assignment
statement, we omit the parentheses, but the following is an equally 
valid syntax:

\beforeverb
\begin{verbatim}
>>> m = [ 'have', 'fun' ]
>>> (x, y) = m
>>> x
'have'
>>> y
'fun'
>>> 
\end{verbatim}
\afterverb
%
A particularly clever application of tuple assignment allows
us to {\bf swap} the values of two variables in a single statement:

\beforeverb
\begin{verbatim}
>>> a, b = b, a
\end{verbatim}
\afterverb
%
Both sides of this statement are tuples, but
the left side is a tuple of variables; the right side is a tuple of
expressions.  Each value on the right side 
is assigned to its respective variable on the left side.  
All the expressions on the right side are evaluated before any
of the assignments.

The number of variables on the left and the number of
values on the right have to be the same:

\index{exception!ValueError}
\index{ValueError}

\beforeverb
\begin{verbatim}
>>> a, b = 1, 2, 3
ValueError: too many values to unpack
\end{verbatim}
\afterverb
%
More generally, the right side can be any kind of sequence
(string, list or tuple).  For example, to split an email address
into a user name and a domain, you could write:

\index{split method}
\index{method!split}
\index{email address}

\beforeverb
\begin{verbatim}
>>> addr = 'monty@python.org'
>>> uname, domain = addr.split('@')
\end{verbatim}
\afterverb
%
The return value from {\tt split} is a list with two elements;
the first element is assigned to {\tt uname}, the second to
{\tt domain}.

\beforeverb
\begin{verbatim}
>>> print uname
monty
>>> print domain
python.org
\end{verbatim}
\afterverb
%

\section{Dictionaries and tuples}

\index{dictionary}
\index{items method}
\index{method!items}
\index{key-value pair}

Dictionaries have a method called {\tt items} that returns a list of
tuples, where each tuple is a key-value 
pair\footnote{This behavior is slightly different in Python 3.0.}.

\beforeverb
\begin{verbatim}
>>> d = {'a':10, 'b':1, 'c':22}
>>> t = d.items()
>>> print t
[('a', 10), ('c', 22), ('b', 1)]
\end{verbatim}
\afterverb
%
As you should expect from a dictionary, the items are in no
particular order.

However, since the list of tuples is a list, and tuples are comparable,
we can now sort the list of tuples.  Converting a dictionary
to a list of tuples is a way for us to output the contents of a 
dictionary sorted by key:

\beforeverb
\begin{verbatim}
>>> d = {'a':10, 'b':1, 'c':22}
>>> t = d.items()
>>> t
[('a', 10), ('c', 22), ('b', 1)]
>>> t.sort()
>>> t
[('a', 10), ('b', 1), ('c', 22)]
\end{verbatim}
\afterverb
%
The new list is sorted in ascending alphabetical order by the key value.

\section{Multiple assignment with dictionaries}

\index{traverse!dictionary}
\index{dictionary!traversal}

Combining {\tt items}, tuple assignment and {\tt for}, you
can see a nice code pattern for traversing the keys and values of a dictionary
in a single loop:

\beforeverb
\begin{verbatim}
for key, val in d.items():
    print val, key
\end{verbatim}
\afterverb
%
This loop has two {\bf iteration variables} because {\tt items} returns
a list of tuples and {\tt key, val} is a tuple assignment
that successively iterates through each of the key/value pairs in the dictionary.  

For each iteration
through the loop, both {\tt key} and {\tt value} are advanced to the
next key/value pair in the dictionary (still in hash order).

The output of this loop is:

\beforeverb
\begin{verbatim}
10 a
22 c
1 b
\end{verbatim}
\afterverb
%
Again in hash key order (i.e. no particular order).

If we combine these two techniques, we can print out the contents
of a dictionary sorted by the \emph{value} stored in each key/value
pair.

To do this, we first make a list of tuples where each tuple is 
{\tt (value, key)}.  The {\tt items} method would give us a list of 
{\tt (key, value)} tuples--but this time we want to sort by value not key.
Once we have constructed the list with the value/key tuples, it is a simple
matter to sort the list in reverse order and print out the new, sorted list.

\beforeverb
\begin{verbatim}
>>> d = {'a':10, 'b':1, 'c':22}
>>> l = list()
>>> for key, val in d.items() :
...     l.append( (val, key) )
... 
>>> l
[(10, 'a'), (22, 'c'), (1, 'b')]
>>> l.sort(reverse=True)
>>> l
[(22, 'c'), (10, 'a'), (1, 'b')]
>>> 
\end{verbatim}
\afterverb
%
By carefully constructing the list of tuples to have the value as the first
element of each tuple, we can sort the list of tuples and get our dictionary
contents sorted by value.

\section{The most common words}

\index{Romeo and Juliet}
Coming back to our running example of the text from \emph{Romeo and Juliet} 
Act 2, Scene 2, we can augment our program to use this technique to 
print the ten most common words in the text as follows:

\beforeverb
\begin{verbatim}
import string
fhand = open('romeo-full.txt')
counts = dict()
for line in fhand:
    line = line.translate(None, string.punctuation)
    line = line.lower()
    words = line.split()
    for word in words:
        if word not in counts:
            counts[word] = 1
        else:
            counts[word] += 1

# Sort the dictionary by value
lst = list()
for key, val in counts.items():
    lst.append( (val, key) )

lst.sort(reverse=True)

for key, val in lst[:10] :
    print key, val
\end{verbatim}
\afterverb
%
The first part of the program which reads the file and computes 
the dictionary that maps each word to the count of words in the 
document is unchanged.  But instead of simply printing out 
{\tt counts} and ending the program, we construct a list 
of {\tt (val, key)} tuples and then sort the list in reverse order.

Since the value is first, it will be used for the comparisons and 
if there is more than one tuple with the same value, it will look
at the second element (the key) so tuples where the value is the
same will be further sorted by the alphabetical order of the key.

At the end we write a nice {\tt for loop} which does a multiple
assignment iteration and prints out the ten most common words
by iterating through a slice of the list ({\tt lst[:10]}).

So now the output finally looks like what we want for our word 
frequency analysis.

\beforeverb
\begin{verbatim}
61 i
42 and
40 romeo
34 to
34 the
32 thou
32 juliet
30 that
29 my
24 thee
\end{verbatim}
\afterverb
%
The fact that this complex data parsing and analysis 
can be done with an easy-to-understand 19 line Python
program is one reason why Python is a good choice as a language 
for exploring information.

\section{Using tuples as keys in dictionaries}

\index{tuple!as key in dictionary}
\index{hashable}

Because tuples are {\bf hashable} and lists are not, if we want to 
create a {\bf composite} key to use in a dictionary we must use a tuple as
the key.

We would encounter a composite key if we wanted to create a 
telephone directory that maps
from last-name, first-name pairs to telephone numbers.  Assuming
that we have defined the variables 
{\tt last}, {\tt first} and {\tt number}, we could write
a dictionary assignment statement as follows:

\beforeverb
\begin{verbatim}
directory[last,first] = number
\end{verbatim}
\afterverb
%
The expression in brackets is a tuple.  We could use tuple
assignment in a {\tt for} loop to traverse this dictionary.

\index{tuple!in brackets}

\beforeverb
\begin{verbatim}
for last, first in directory:
    print first, last, directory[last,first]
\end{verbatim}
\afterverb
%
This loop traverses the keys in {\tt directory}, which are tuples.  It
assigns the elements of each tuple to {\tt last} and {\tt first}, then
prints the name and corresponding telephone number.

\section{Sequences: strings, lists, and tuples--Oh My!}
\index{sequence}

I have focused on lists of tuples, but almost all of the examples in
this chapter also work with lists of lists, tuples of tuples, and
tuples of lists.  To avoid enumerating the possible combinations, it
is sometimes easier to talk about sequences of sequences.

In many contexts, the different kinds of sequences (strings, lists and
tuples) can be used interchangeably.  So how and why do you choose one
over the others?

\index{string}
\index{list}
\index{tuple}
\index{mutability}
\index{immutability}

To start with the obvious, strings are more limited than other
sequences because the elements have to be characters.  They are
also immutable.  If you need the ability to change the characters
in a string (as opposed to creating a new string), you might
want to use a list of characters instead.

Lists are more common than tuples, mostly because they are mutable.
But there are a few cases where you might prefer tuples:

\begin{enumerate}

\item In some contexts, like a {\tt return} statement, it is
syntactically simpler to create a tuple than a list.  In other
contexts, you might prefer a list.

\item If you want to use a sequence as a dictionary key, you
have to use an immutable type like a tuple or string.

\item If you are passing a sequence as an argument to a function,
using tuples reduces the potential for unexpected behavior
due to aliasing.

\end{enumerate}

Because tuples are immutable, they don't provide methods
like {\tt sort} and {\tt reverse}, which modify existing lists.
However Python provides the built-in functions {\tt sorted}
and {\tt reversed}, which take any sequence as a parameter
and return a new list with the same elements in a different
order.

\index{sorted function}
\index{function!sorted}
\index{reversed function}
\index{function!reversed}


\section{Debugging}

\index{debugging}
\index{data structure}
\index{shape error}
\index{error!shape}

Lists, dictionaries and tuples are known generically as {\bf data
  structures}; in this chapter we are starting to see compound data
structures, like lists of tuples, and dictionaries that contain tuples
as keys and lists as values.  Compound data structures are useful, but
they are prone to what I call {\bf shape errors}; that is, errors
caused when a data structure has the wrong type, size or composition
or perhaps you write some code and forget the shape of your data
and introduce an error.

For example, if you are expecting a list with one integer and I
give you a plain old integer (not in a list), it won't work.

When you are debugging a program, and especially if you are
working on a hard bug, there are four things to try:

\begin{description}

\item[reading:] Examine your code, read it back to yourself, and
check that it says what you meant to say.

\item[running:] Experiment by making changes and running different
versions.  Often if you display the right thing at the right place
in the program, the problem becomes obvious, but sometimes you have to
spend some time to build scaffolding.

\item[ruminating:] Take some time to think!  What kind of error
is it: syntax, runtime, semantic?  What information can you get from
the error messages, or from the output of the program?  What kind of
error could cause the problem you're seeing?  What did you change
last, before the problem appeared?

\item[retreating:] At some point, the best thing to do is back
off, undoing recent changes, until you get back to a program that
works and that you understand.  Then you can start rebuilding.

\end{description}

Beginning programmers sometimes get stuck on one of these activities
and forget the others.  Each activity comes with its own failure
mode.

\index{typographical error}

For example, reading your code might help if the problem is a
typographical error, but not if the problem is a conceptual
misunderstanding.  If you don't understand what your program does, you
can read it 100 times and never see the error, because the error is in
your head.

\index{experimental debugging}

Running experiments can help, especially if you run small, simple
tests.  But if you run experiments without thinking or reading your
code, you might fall into a pattern I call ``random walk programming,''
which is the process of making random changes until the program
does the right thing.  Needless to say, random walk programming
can take a long time.

\index{random walk programming}
\index{development plan!random walk programming}

You have to take time to think.  Debugging is like an
experimental science.  You should have at least one hypothesis about
what the problem is.  If there are two or more possibilities, try to
think of a test that would eliminate one of them.

Taking a break helps with the thinking.  So does talking.
If you explain the problem to someone else (or even yourself), you
will sometimes find the answer before you finish asking the question.

But even the best debugging techniques will fail if there are too many
errors, or if the code you are trying to fix is too big and
complicated.  Sometimes the best option is to retreat, simplifying the
program until you get to something that works and that you
understand.

Beginning programmers are often reluctant to retreat because
they can't stand to delete a line of code (even if it's wrong).
If it makes you feel better, copy your program into another file
before you start stripping it down.  Then you can paste the pieces
back in a little bit at a time.

Finding a hard bug requires reading, running, ruminating, and
sometimes retreating.  If you get stuck on one of these activities,
try the others.


\section{Glossary}

\begin{description}

\item[comparable:] A type where one value can be checked to see if it is
greater than, less than or equal to another value of the same type.
Types which are comparable can be put in a list and sorted.
\index{comparable}

\item[data structure:] A collection of related values, often
organized in lists, dictionaries, tuples, etc.
\index{data structure}

\item[DSU:] Abbreviation of ``decorate-sort-undecorate,'' a
pattern that involves building a list of tuples, sorting, and
extracting part of the result.
\index{DSU pattern}

\item[gather:] The operation of assembling a variable-length
argument tuple.
\index{gather}

\item[hashable:] A type that has a hash function.  Immutable
types like integers,
floats and strings are hashable; mutable types like lists and
dictionaries are not.
\index{hashable}

\item[scatter:] The operation of treating a sequence as a list of
arguments.
\index{scatter}

\item[shape (of a data structure):] A summary of the type,
size and composition of a data structure.
\index{shape}

\item[singleton:] A list (or other sequence) with a single element.
\index{singleton}

\item[tuple:] An immutable sequence of elements.
\index{tuple}

\item[tuple assignment:] An assignment with a sequence on the
right side and a tuple of variables on the left.  The right
side is evaluated and then its elements are assigned to the
variables on the left.
\index{tuple assignment}
\index{assignment!tuple}

\end{description}


\section{Exercises}

\begin{ex}
Revise a previous program as follows:  Read and 
parse the ``From'' lines and pull out the 
addresses from the line.   Count the number of
messages from each person using a dictionary.

After all the data has been read print 
the person with the most commits by creating
a list of (count, email) tuples from the 
dictionary and then sorting the list in reverse
order and print out the person who has the most
commits.

\beforeverb
\begin{verbatim}
Sample Line:
From stephen.marquard@uct.ac.za Sat Jan  5 09:14:16 2008

Enter a file name: mbox-short.txt
cwen@iupui.edu 5

Enter a file name: mbox.txt
zqian@umich.edu 195
\end{verbatim}
\afterverb
\end{ex}
\begin{ex}
This program counts the distribution of the hour of the day for 
each of the messages. You can pull the hour from the ``From'' 
line by finding the time string and then splitting that string 
into parts using the colon character. Once you have accumulated 
the counts for each hour, print out the counts, one per line, 
sorted by hour as shown below. 
\beforeverb
\begin{verbatim}
Sample Execution:
python timeofday.py
Enter a file name: mbox-short.txt
04 3
06 1
07 1
09 2
10 3
11 6
14 1
15 2
16 4
17 2
18 1
19 1
\end{verbatim}
\afterverb
\end{ex}


\begin{ex}
Write a program that reads a file and 
prints the {\em letters} in decreasing order of frequency.  Your program
should convert all the input to lower case and only count the letters a-z.
Your program should not count spaces, digits, punctuation or anything 
other than the letters a-z.
Find text samples from several different languages and see how letter frequency
varies between languages.  Compare your results with the tables at
\url{wikipedia.org/wiki/Letter_frequencies}.

\index{letter frequency}
\index{frequency!letter}

\end{ex}