-
Notifications
You must be signed in to change notification settings - Fork 31
/
Copy paththinkpython2013.html
601 lines (573 loc) · 38.9 KB
/
thinkpython2013.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<meta name="generator" content="hevea 2.09">
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css" integrity="sha384-1q8mTJOASx8j1Au+a5WDVnPi2lkFfwwEAa8hDDdjZlpLegxhjVME1fgjWPGmkzs7" crossorigin="anonymous">
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap-theme.min.css" integrity="sha384-fLW2N01lMqjakBkx3l/M9EahuwpSfeNvV63J5ezn3uZzapT0u7EYsXMjQV+0En5r" crossorigin="anonymous">
<link rel="stylesheet" type="text/css" href="thinkpython2.css">
<title>Tuples</title>
</head>
<body>
<nav class="navbar navbar-default navbar-fixed-top">
<div class="container-fluid">
<!-- Brand and toggle get grouped for better mobile display -->
<div class="navbar-header">
<button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#bs-example-navbar-collapse-1" aria-expanded="false">
<span class="sr-only">Toggle navigation</span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
<a class="navbar-brand" href="#"><strong>Think Python</strong> - How to Think like a Computer Scientist (2e) <em>by Allen B. Downey</em></a>
</div>
<div>
<ul class="nav navbar-nav navbar-right">
<li><a href="http://greenteapress.com/thinkpython2/html/index.html"><span class="glyphicon glyphicon glyphicon-book" aria-hidden="true"></span></a></li>
<li><a href="thinkpython2012.html"><span class="glyphicon glyphicon glyphicon-menu-left" aria-hidden="true"></span></a></li>
<li><a href="index.html"><span class="glyphicon glyphicon glyphicon-home" aria-hidden="true"></span></a></li>
<li><a href="thinkpython2014.html"><span class="glyphicon glyphicon glyphicon-menu-right" aria-hidden="true"></span></a></li>
<li><a href="http://amzn.to/1VUYQUU"><span class="glyphicon glyphicon glyphicon-shopping-cart" aria-hidden="true"></span></a></li>
</ul>
<div>
</div><!-- /.container-fluid -->
</nav>
<table>
<tr>
<td valign="top" width="100" bgcolor="#b6459a" id="col-left">
</td>
<td valign="top" id="content">
<p>
<h1 class="chapter" id="sec140">Chapter 12  Tuples</h1>
<p>
<a id="tuplechap"></a></p><p>This chapter presents one more built-in type, the tuple, and then
shows how lists, dictionaries, and tuples work together.
I also present a useful feature for variable-length argument lists,
the gather and scatter operators.</p><p>One note: there is no consensus on how to pronounce “tuple”.
Some people say “tuh-ple”, which rhymes with “supple”. But
in the context of programming, most people say “too-ple”, which
rhymes with “quadruple”.</p>
<h2 class="section" id="sec141">12.1  Tuples are immutable</h2>
<p>
<a id="hevea_default1004"></a>
<a id="hevea_default1005"></a>
<a id="hevea_default1006"></a></p><p>A tuple is a sequence of values. The values can be any type, and
they are indexed by integers, so in that respect tuples are a lot
like lists. The important difference is that tuples are immutable.
<a id="hevea_default1007"></a>
<a id="hevea_default1008"></a></p><p>Syntactically, a tuple is a comma-separated list of values:</p><pre class="verbatim">>>> t = 'a', 'b', 'c', 'd', 'e'
</pre><p>Although it is not necessary, it is common to enclose tuples in
parentheses:
<a id="hevea_default1009"></a></p><pre class="verbatim">>>> t = ('a', 'b', 'c', 'd', 'e')
</pre><p>To create a tuple with a single element, you have to include a final
comma:
<a id="hevea_default1010"></a>
<a id="hevea_default1011"></a></p><pre class="verbatim">>>> t1 = 'a',
>>> type(t1)
<class 'tuple'>
</pre><p>A value in parentheses is not a tuple:</p><pre class="verbatim">>>> t2 = ('a')
>>> type(t2)
<class 'str'>
</pre><p>Another way to create a tuple is the built-in function <span class="c004">tuple</span>.
With no argument, it creates an empty tuple:
<a id="hevea_default1012"></a>
<a id="hevea_default1013"></a></p><pre class="verbatim">>>> t = tuple()
>>> t
()
</pre><p>If the argument is a sequence (string, list or tuple), the result
is a tuple with the elements of the sequence:</p><pre class="verbatim">>>> t = tuple('lupins')
>>> t
('l', 'u', 'p', 'i', 'n', 's')
</pre><p>Because <span class="c004">tuple</span> is the name of a built-in function, you should
avoid using it as a variable name.</p><p>Most list operators also work on tuples. The bracket operator
indexes an element:
<a id="hevea_default1014"></a>
<a id="hevea_default1015"></a></p><pre class="verbatim">>>> t = ('a', 'b', 'c', 'd', 'e')
>>> t[0]
'a'
</pre><p>And the slice operator selects a range of elements.
<a id="hevea_default1016"></a>
<a id="hevea_default1017"></a>
<a id="hevea_default1018"></a>
<a id="hevea_default1019"></a></p><pre class="verbatim">>>> t[1:3]
('b', 'c')
</pre><p>But if you try to modify one of the elements of the tuple, you get
an error:
<a id="hevea_default1020"></a>
<a id="hevea_default1021"></a>
<a id="hevea_default1022"></a>
<a id="hevea_default1023"></a></p><pre class="verbatim">>>> t[0] = 'A'
TypeError: object doesn't support item assignment
</pre><p>Because tuples are immutable, you can’t modify the elements. But you
can replace one tuple with another:</p><pre class="verbatim">>>> t = ('A',) + t[1:]
>>> t
('A', 'b', 'c', 'd', 'e')
</pre><p>This statement makes a new tuple and then makes <span class="c004">t</span> refer to it.</p><p>The relational 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 elements,
and so on, until it finds elements that differ. Subsequent
elements are not considered (even if they are really big).
<a id="hevea_default1024"></a>
<a id="hevea_default1025"></a></p><pre class="verbatim">>>> (0, 1, 2) < (0, 3, 4)
True
>>> (0, 1, 2000000) < (0, 3, 4)
True
</pre>
<h2 class="section" id="sec142">12.2  Tuple assignment</h2>
<p>
<a id="tuple.assignment"></a>
<a id="hevea_default1026"></a>
<a id="hevea_default1027"></a>
<a id="hevea_default1028"></a>
<a id="hevea_default1029"></a></p><p>It is often useful to swap the values of two variables.
With conventional assignments, you have to use a temporary
variable. For example, to swap <span class="c004">a</span> and <span class="c004">b</span>:</p><pre class="verbatim">>>> temp = a
>>> a = b
>>> b = temp
</pre><p>This solution is cumbersome; <span class="c010">tuple assignment</span> is more elegant:</p><pre class="verbatim">>>> a, b = b, a
</pre><p>The left side is a tuple of variables; the right side is a tuple of
expressions. Each value is assigned to its respective variable.
All the expressions on the right side are evaluated before any
of the assignments.</p><p>The number of variables on the left and the number of
values on the right have to be the same:
<a id="hevea_default1030"></a>
<a id="hevea_default1031"></a></p><pre class="verbatim">>>> a, b = 1, 2, 3
ValueError: too many values to unpack
</pre><p>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:
<a id="hevea_default1032"></a>
<a id="hevea_default1033"></a>
<a id="hevea_default1034"></a></p><pre class="verbatim">>>> addr = '[email protected]'
>>> uname, domain = addr.split('@')
</pre><p>The return value from <span class="c004">split</span> is a list with two elements;
the first element is assigned to <span class="c004">uname</span>, the second to
<span class="c004">domain</span>.</p><pre class="verbatim">>>> uname
'monty'
>>> domain
'python.org'
</pre>
<h2 class="section" id="sec143">12.3  Tuples as return values</h2>
<p>
<a id="hevea_default1035"></a>
<a id="hevea_default1036"></a>
<a id="hevea_default1037"></a>
<a id="hevea_default1038"></a></p><p>Strictly speaking, a function can only return one value, but
if the value is a tuple, the effect is the same as returning
multiple values. For example, if you want to divide two integers
and compute the quotient and remainder, it is inefficient to
compute <span class="c004">x/y</span> and then <span class="c004">x%y</span>. It is better to compute
them both at the same time.
<a id="hevea_default1039"></a></p><p>The built-in function <span class="c004">divmod</span> takes two arguments and
returns a tuple of two values, the quotient and remainder.
You can store the result as a tuple:</p><pre class="verbatim">>>> t = divmod(7, 3)
>>> t
(2, 1)
</pre><p>Or use tuple assignment to store the elements separately:
<a id="hevea_default1040"></a>
<a id="hevea_default1041"></a></p><pre class="verbatim">>>> quot, rem = divmod(7, 3)
>>> quot
2
>>> rem
1
</pre><p>Here is an example of a function that returns a tuple:</p><pre class="verbatim">def min_max(t):
return min(t), max(t)
</pre><p><span class="c004">max</span> and <span class="c004">min</span> are built-in functions that find
the largest and smallest elements of a sequence. <code>min_max</code>
computes both and returns a tuple of two values.
<a id="hevea_default1042"></a>
<a id="hevea_default1043"></a>
<a id="hevea_default1044"></a>
<a id="hevea_default1045"></a></p>
<h2 class="section" id="sec144">12.4  Variable-length argument tuples</h2>
<p>
<a id="gather"></a>
<a id="hevea_default1046"></a>
<a id="hevea_default1047"></a>
<a id="hevea_default1048"></a>
<a id="hevea_default1049"></a>
<a id="hevea_default1050"></a></p><p>Functions can take a variable number of arguments. A parameter
name that begins with <span class="c004">*</span> <span class="c010">gathers</span> arguments into
a tuple. For example, <span class="c004">printall</span>
takes any number of arguments and prints them:</p><pre class="verbatim">def printall(*args):
print(args)
</pre><p>The gather parameter can have any name you like, but <span class="c004">args</span> is
conventional. Here’s how the function works:</p><pre class="verbatim">>>> printall(1, 2.0, '3')
(1, 2.0, '3')
</pre><p>The complement of gather is <span class="c010">scatter</span>. If you have a
sequence of values and you want to pass it to a function
as multiple arguments, you can use the <span class="c004">*</span> operator.
For example, <span class="c004">divmod</span> takes exactly two arguments; it
doesn’t work with a tuple:
<a id="hevea_default1051"></a>
<a id="hevea_default1052"></a>
<a id="hevea_default1053"></a>
<a id="hevea_default1054"></a></p><pre class="verbatim">>>> t = (7, 3)
>>> divmod(t)
TypeError: divmod expected 2 arguments, got 1
</pre><p>But if you scatter the tuple, it works:</p><pre class="verbatim">>>> divmod(*t)
(2, 1)
</pre><p>Many of the built-in functions use
variable-length argument tuples. For example, <span class="c004">max</span>
and <span class="c004">min</span> can take any number of arguments:
<a id="hevea_default1055"></a>
<a id="hevea_default1056"></a>
<a id="hevea_default1057"></a>
<a id="hevea_default1058"></a></p><pre class="verbatim">>>> max(1, 2, 3)
3
</pre><p>But <span class="c004">sum</span> does not.
<a id="hevea_default1059"></a>
<a id="hevea_default1060"></a></p><pre class="verbatim">>>> sum(1, 2, 3)
TypeError: sum expected at most 2 arguments, got 3
</pre><p>As an exercise, write a function called <span class="c004">sumall</span> that takes any number
of arguments and returns their sum.</p>
<h2 class="section" id="sec145">12.5  Lists and tuples</h2>
<p>
<a id="hevea_default1061"></a>
<a id="hevea_default1062"></a></p><p><span class="c004">zip</span> is a built-in function that takes two or more sequences and
returns a list of tuples where each tuple contains one
element from each sequence. The name of the function refers to
a zipper, which joins and interleaves two rows of teeth.</p><p>This example zips a string and a list:</p><pre class="verbatim">>>> s = 'abc'
>>> t = [0, 1, 2]
>>> zip(s, t)
<zip object at 0x7f7d0a9e7c48>
</pre><p>The result is a <span class="c010">zip object</span> that knows how to iterate through
the pairs. The most common use of <span class="c004">zip</span> is in a <span class="c004">for</span> loop:</p><pre class="verbatim">>>> for pair in zip(s, t):
... print(pair)
...
('a', 0)
('b', 1)
('c', 2)
</pre><p>A zip object is a kind of <span class="c010">iterator</span>, which is any object
that iterates through a sequence. Iterators are similar to lists in some
ways, but unlike lists, you can’t use an index to select an element from
an iterator.
<a id="hevea_default1063"></a></p><p>If you want to use list operators and methods, you can
use a zip object to make a list:</p><pre class="verbatim">>>> list(zip(s, t))
[('a', 0), ('b', 1), ('c', 2)]
</pre><p>The result is a list of tuples; in this example, each tuple contains
a character from the string and the corresponding element from
the list.
<a id="hevea_default1064"></a></p><p>If the sequences are not the same length, the result has the
length of the shorter one.</p><pre class="verbatim">>>> list(zip('Anne', 'Elk'))
[('A', 'E'), ('n', 'l'), ('n', 'k')]
</pre><p>You can use tuple assignment in a <span class="c004">for</span> loop to traverse a list of
tuples:
<a id="hevea_default1065"></a>
<a id="hevea_default1066"></a>
<a id="hevea_default1067"></a></p><pre class="verbatim">t = [('a', 0), ('b', 1), ('c', 2)]
for letter, number in t:
print(number, letter)
</pre><p>Each time through the loop, Python selects the next tuple in
the list and assigns the elements to <span class="c004">letter</span> and
<span class="c004">number</span>. The output of this loop is:
<a id="hevea_default1068"></a></p><pre class="verbatim">0 a
1 b
2 c
</pre><p>If you combine <span class="c004">zip</span>, <span class="c004">for</span> and tuple assignment, you get a
useful idiom for traversing two (or more) sequences at the same
time. For example, <code>has_match</code> takes two sequences, <span class="c004">t1</span> and
<span class="c004">t2</span>, and returns <span class="c004">True</span> if there is an index <span class="c004">i</span>
such that <span class="c004">t1[i] == t2[i]</span>:
<a id="hevea_default1069"></a></p><pre class="verbatim">def has_match(t1, t2):
for x, y in zip(t1, t2):
if x == y:
return True
return False
</pre><p>If you need to traverse the elements of a sequence and their
indices, you can use the built-in function <span class="c004">enumerate</span>:
<a id="hevea_default1070"></a>
<a id="hevea_default1071"></a>
<a id="hevea_default1072"></a></p><pre class="verbatim">for index, element in enumerate('abc'):
print(index, element)
</pre><p>The result from <span class="c004">enumerate</span> is an enumerate object, which
iterates a sequence of pairs; each pair contains an index (starting
from 0) and an element from the given sequence.
In this example, the output is</p><pre class="verbatim">0 a
1 b
2 c
</pre><p>Again.
<a id="hevea_default1073"></a>
<a id="hevea_default1074"></a>
<a id="hevea_default1075"></a></p>
<h2 class="section" id="sec146">12.6  Dictionaries and tuples</h2>
<p>
<a id="dictuple"></a>
<a id="hevea_default1076"></a>
<a id="hevea_default1077"></a>
<a id="hevea_default1078"></a>
<a id="hevea_default1079"></a></p><p>Dictionaries have a method called <span class="c004">items</span> that returns a sequence of
tuples, where each tuple is a key-value pair.</p><pre class="verbatim">>>> d = {'a':0, 'b':1, 'c':2}
>>> t = d.items()
>>> t
dict_items([('c', 2), ('a', 0), ('b', 1)])
</pre><p>The result is a <code>dict_items</code> object, which is an iterator that
iterates the key-value pairs. You can use it in a <span class="c004">for</span> loop
like this:
<a id="hevea_default1080"></a></p><pre class="verbatim">>>> for key, value in d.items():
... print(key, value)
...
c 2
a 0
b 1
</pre><p>As you should expect from a dictionary, the items are in no
particular order.</p><p>Going in the other direction, you can use a list of tuples to
initialize a new dictionary: <a id="hevea_default1081"></a></p><pre class="verbatim">>>> t = [('a', 0), ('c', 2), ('b', 1)]
>>> d = dict(t)
>>> d
{'a': 0, 'c': 2, 'b': 1}
</pre><p>Combining <span class="c004">dict</span> with <span class="c004">zip</span> yields a concise way
to create a dictionary:
<a id="hevea_default1082"></a></p><pre class="verbatim">>>> d = dict(zip('abc', range(3)))
>>> d
{'a': 0, 'c': 2, 'b': 1}
</pre><p>The dictionary method <span class="c004">update</span> also takes a list of tuples
and adds them, as key-value pairs, to an existing dictionary.
<a id="hevea_default1083"></a>
<a id="hevea_default1084"></a>
<a id="hevea_default1085"></a>
<a id="hevea_default1086"></a></p><p>It is common to use tuples as keys in dictionaries (primarily because
you can’t use lists). For example, a telephone directory might map
from last-name, first-name pairs to telephone numbers. Assuming
that we have defined <span class="c004">last</span>, <span class="c004">first</span> and <span class="c004">number</span>, we
could write:
<a id="hevea_default1087"></a>
<a id="hevea_default1088"></a></p><pre class="verbatim">directory[last, first] = number
</pre><p>The expression in brackets is a tuple. We could use tuple
assignment to traverse this dictionary.
<a id="hevea_default1089"></a></p><pre class="verbatim">for last, first in directory:
print(first, last, directory[last,first])
</pre><p>This loop traverses the keys in <span class="c004">directory</span>, which are tuples. It
assigns the elements of each tuple to <span class="c004">last</span> and <span class="c004">first</span>, then
prints the name and corresponding telephone number.</p><p>There are two ways to represent tuples in a state diagram. The more
detailed version shows the indices and elements just as they appear in
a list. For example, the tuple <code>('Cleese', 'John')</code> would appear
as in Figure <a href="thinkpython2013.html#fig.tuple1">12.1</a>.
<a id="hevea_default1090"></a>
<a id="hevea_default1091"></a></p><blockquote class="figure"><div class="center"><hr class="c019"></div>
<div class="center"><img src="images/thinkpython2018.png"></div>
<div class="caption"><table class="c001 cellpading0"><tr><td class="c018">Figure 12.1: State diagram.</td></tr>
</table></div>
<a id="fig.tuple1"></a>
<div class="center"><hr class="c019"></div></blockquote><p>But in a larger diagram you might want to leave out the
details. For example, a diagram of the telephone directory might
appear as in Figure <a href="thinkpython2013.html#fig.dict2">12.2</a>.</p><blockquote class="figure"><div class="center"><hr class="c019"></div>
<div class="center"><img src="images/thinkpython2019.png"></div>
<div class="caption"><table class="c001 cellpading0"><tr><td class="c018">Figure 12.2: State diagram.</td></tr>
</table></div>
<a id="fig.dict2"></a>
<div class="center"><hr class="c019"></div></blockquote><p>Here the tuples are shown using Python syntax as a graphical
shorthand. The telephone number in the diagram is the complaints line
for the BBC, so please don’t call it.</p>
<h2 class="section" id="sec147">12.7  Sequences of sequences</h2>
<p>
<a id="hevea_default1092"></a></p><p>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.</p><p>In many contexts, the different kinds of sequences (strings, lists and
tuples) can be used interchangeably. So how should you choose one
over the others?
<a id="hevea_default1093"></a>
<a id="hevea_default1094"></a>
<a id="hevea_default1095"></a>
<a id="hevea_default1096"></a>
<a id="hevea_default1097"></a></p><p>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.</p><p>Lists are more common than tuples, mostly because they are mutable.
But there are a few cases where you might prefer tuples:</p><ol class="enumerate" type=1><li class="li-enumerate">In some contexts, like a <span class="c004">return</span> statement, it is
syntactically simpler to create a tuple than a list.</li><li class="li-enumerate">If you want to use a sequence as a dictionary key, you
have to use an immutable type like a tuple or string.</li><li class="li-enumerate">If you are passing a sequence as an argument to a function,
using tuples reduces the potential for unexpected behavior
due to aliasing.</li></ol><p>Because tuples are immutable, they don’t provide methods like <span class="c004">sort</span> and <span class="c004">reverse</span>, which modify existing lists. But Python
provides the built-in function <span class="c004">sorted</span>, which takes any sequence
and returns a new list with the same elements in sorted order, and
<span class="c004">reversed</span>, which takes a sequence and returns an iterator that
traverses the list in reverse order.
<a id="hevea_default1098"></a>
<a id="hevea_default1099"></a> <a id="hevea_default1100"></a>
<a id="hevea_default1101"></a>
<a id="hevea_default1102"></a></p>
<h2 class="section" id="sec148">12.8  Debugging</h2>
<p>
<a id="hevea_default1103"></a>
<a id="hevea_default1104"></a>
<a id="hevea_default1105"></a>
<a id="hevea_default1106"></a></p><p>Lists, dictionaries and tuples are examples of <span class="c010">data
structures</span>; in this chapter we are starting to see compound data
structures, like lists of tuples, or dictionaries that contain tuples
as keys and lists as values. Compound data structures are useful, but
they are prone to what I call <span class="c010">shape errors</span>; that is, errors
caused when a data structure has the wrong type, size, or structure.
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.
<a id="hevea_default1107"></a>
<a id="hevea_default1108"></a></p><p>To help debug these kinds of errors, I have written a module
called <span class="c004">structshape</span> that provides a function, also called
<span class="c004">structshape</span>, that takes any kind of data structure as
an argument and returns a string that summarizes its shape.
You can download it from <a href="http://thinkpython2.com/code/structshape.py"><span class="c004">http://thinkpython2.com/code/structshape.py</span></a></p><p>Here’s the result for a simple list:</p><pre class="verbatim">>>> from structshape import structshape
>>> t = [1, 2, 3]
>>> structshape(t)
'list of 3 int'
</pre><p>A fancier program might write “list of 3 int<em>s</em>”, but it
was easier not to deal with plurals. Here’s a list of lists:</p><pre class="verbatim">>>> t2 = [[1,2], [3,4], [5,6]]
>>> structshape(t2)
'list of 3 list of 2 int'
</pre><p>If the elements of the list are not the same type,
<span class="c004">structshape</span> groups them, in order, by type:</p><pre class="verbatim">>>> t3 = [1, 2, 3, 4.0, '5', '6', [7], [8], 9]
>>> structshape(t3)
'list of (3 int, float, 2 str, 2 list of int, int)'
</pre><p>Here’s a list of tuples:</p><pre class="verbatim">>>> s = 'abc'
>>> lt = list(zip(t, s))
>>> structshape(lt)
'list of 3 tuple of (int, str)'
</pre><p>And here’s a dictionary with 3 items that map integers to strings.</p><pre class="verbatim">>>> d = dict(lt)
>>> structshape(d)
'dict of 3 int->str'
</pre><p>If you are having trouble keeping track of your data structures,
<span class="c004">structshape</span> can help.</p>
<h2 class="section" id="sec149">12.9  Glossary</h2>
<dl class="description"><dt class="dt-description"><span class="c010">tuple:</span></dt><dd class="dd-description"> An immutable sequence of elements.
<a id="hevea_default1109"></a></dd><dt class="dt-description"><span class="c010">tuple assignment:</span></dt><dd class="dd-description"> 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.
<a id="hevea_default1110"></a>
<a id="hevea_default1111"></a></dd><dt class="dt-description"><span class="c010">gather:</span></dt><dd class="dd-description"> The operation of assembling a variable-length
argument tuple.
<a id="hevea_default1112"></a></dd><dt class="dt-description"><span class="c010">scatter:</span></dt><dd class="dd-description"> The operation of treating a sequence as a list of
arguments.
<a id="hevea_default1113"></a></dd><dt class="dt-description"><span class="c010">zip object:</span></dt><dd class="dd-description"> The result of calling a built-in function <span class="c004">zip</span>;
an object that iterates through a sequence of tuples.
<a id="hevea_default1114"></a>
<a id="hevea_default1115"></a></dd><dt class="dt-description"><span class="c010">iterator:</span></dt><dd class="dd-description"> An object that can iterate through a sequence, but
which does not provide list operators and methods.
<a id="hevea_default1116"></a></dd><dt class="dt-description"><span class="c010">data structure:</span></dt><dd class="dd-description"> A collection of related values, often
organized in lists, dictionaries, tuples, etc.
<a id="hevea_default1117"></a></dd><dt class="dt-description"><span class="c010">shape error:</span></dt><dd class="dd-description"> An error caused because a value has the
wrong shape; that is, the wrong type or size.
<a id="hevea_default1118"></a></dd></dl>
<h2 class="section" id="sec150">12.10  Exercises</h2>
<div class="theorem"><span class="c010">Exercise 1</span>  <p><em>Write a function called <code>most_frequent</code> that takes a string and
prints the letters in decreasing order of frequency. Find text
samples from several different languages and see how letter frequency
varies between languages. Compare your results with the tables at
</em><a href="http://en.wikipedia.org/wiki/Letter_frequencies"><span class="c004"><em>http://en.wikipedia.org/wiki/Letter_frequencies</em></span></a><em>. Solution:
</em><a href="http://thinkpython2.com/code/most_frequent.py"><span class="c004"><em>http://thinkpython2.com/code/most_frequent.py</em></span></a><em>. </em><a id="hevea_default1119"></a> <a id="hevea_default1120"></a></p></div><div class="theorem"><span class="c010">Exercise 2</span>  
<a id="anagrams"></a>
<a id="hevea_default1121"></a>
<a id="hevea_default1122"></a><p><em>More anagrams!</em></p><ol class="enumerate" type=1><li class="li-enumerate"><em>Write a program
that reads a word list from a file (see Section </em><a href="thinkpython2010.html#wordlist"><em>9.1</em></a><em>) and
prints all the sets of words that are anagrams.</em><p><em>Here is an example of what the output might look like:</em></p><pre class="verbatim"><em>['deltas', 'desalt', 'lasted', 'salted', 'slated', 'staled']
['retainers', 'ternaries']
['generating', 'greatening']
['resmelts', 'smelters', 'termless']
</em></pre><p><em>Hint: you might want to build a dictionary that maps from a
collection of letters to a list of words that can be spelled with those
letters. The question is, how can you represent the collection of
letters in a way that can be used as a key?</em></p></li><li class="li-enumerate"><em>Modify the previous program so that it prints the longest list
of anagrams first, followed by the second longest, and so on.
</em><a id="hevea_default1123"></a>
<a id="hevea_default1124"></a></li><li class="li-enumerate"><em>In Scrabble a “bingo” is when you play all seven tiles in
your rack, along with a letter on the board, to form an eight-letter
word. What collection of 8 letters forms the most possible bingos?
Hint: there are seven.</em><p><em>Solution: </em><a href="http://thinkpython2.com/code/anagram_sets.py"><span class="c004"><em>http://thinkpython2.com/code/anagram_sets.py</em></span></a><em>.</em></p></li></ol></div><div class="theorem"><span class="c010">Exercise 3</span>  
<a id="hevea_default1125"></a><p><em>Two words form a “metathesis pair” if you can transform one into the
other by swapping two letters; for example, “converse” and
“conserve”. Write a program that finds all of the metathesis pairs
in the dictionary. Hint: don’t test all pairs of words, and don’t
test all possible swaps. Solution:
</em><a href="http://thinkpython2.com/code/metathesis.py"><em><span class="c004">http://thinkpython2.com/code/metathesis.py</span></em></a><em>. Credit: This
exercise is inspired by an example at </em><a href="http://puzzlers.org"><em><span class="c004">http://puzzlers.org</span></em></a><em>.</em></p></div><div class="theorem"><span class="c010">Exercise 4</span>  
<a id="hevea_default1126"></a>
<a id="hevea_default1127"></a><p><em>Here’s another Car Talk Puzzler
(</em><a href="http://www.cartalk.com/content/puzzlers"><em><span class="c004">http://www.cartalk.com/content/puzzlers</span></em></a><em>):</em></p><blockquote class="quote"><em>
What is the longest English word, that remains a valid English word,
as you remove its letters one at a time?</em><p><em>Now, letters can be removed from either end, or the middle, but you
can’t rearrange any of the letters. Every time you drop a letter, you
wind up with another English word. If you do that, you’re eventually
going to wind up with one letter and that too is going to be an
English word—one that’s found in the dictionary. I want to know
what’s the longest word and how many letters does it
have?</em></p><p><em>I’m going to give you a little modest example: Sprite. Ok? You start
off with sprite, you take a letter off, one from the interior of the
word, take the r away, and we’re left with the word spite, then we
take the e off the end, we’re left with spit, we take the s off, we’re
left with pit, it, and I.
</em></p></blockquote><p>
<a id="hevea_default1128"></a>
<a id="hevea_default1129"></a></p><p><em>Write a program to find all words that can be reduced in this way,
and then find the longest one.</em></p><p><em>This exercise is a little more challenging than most, so here are
some suggestions:</em></p><ol class="enumerate" type=1><li class="li-enumerate"><em>You might want to write a function that takes a word and
computes a list of all the words that can be formed by removing one
letter. These are the “children” of the word.
</em><a id="hevea_default1130"></a>
<a id="hevea_default1131"></a></li><li class="li-enumerate"><em>Recursively, a word is reducible if any of its children
are reducible. As a base case, you can consider the empty
string reducible.</em></li><li class="li-enumerate"><em>The wordlist I provided, <span class="c004">words.txt</span>, doesn’t
contain single letter words. So you might want to add
“I”, “a”, and the empty string.</em></li><li class="li-enumerate"><em>To improve the performance of your program, you might want
to memoize the words that are known to be reducible.</em></li></ol><p><em>Solution: </em><a href="http://thinkpython2.com/code/reducible.py"><em><span class="c004">http://thinkpython2.com/code/reducible.py</span></em></a><em>.</em></p></div>
<p>
</td>
<td width=130 valign="top" id="col-right">
<p>
<h4>Are you using one of our books in a class?</h4> We'd like to know
about it. Please consider filling out <a href="http://spreadsheets.google.com/viewform?formkey=dC0tNUZkMjBEdXVoRGljNm9FRmlTMHc6MA" onClick="javascript: pageTracker._trackPageview('/outbound/survey');">this short survey</a>.
<p>
<br>
<p>
<a rel="nofollow" href="http://www.amazon.com/gp/product/1491938455/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1491938455&linkCode=as2&tag=greenteapre01-20&linkId=2JJH4SWCAVVYSQHO">Think DSP</a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1491938455" width="1" height="1" border="0" alt="">
<p>
<a rel="nofollow" href="http://www.amazon.com/gp/product/1491938455/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1491938455&linkCode=as2&tag=greenteapre01-20&linkId=CTV7PDT7E5EGGJUM"><img border="0" src="http://ws-na.amazon-adsystem.com/widgets/q?_encoding=UTF8&ASIN=1491938455&Format=_SL160_&ID=AsinImage&MarketPlace=US&ServiceVersion=20070822&WS=1&tag=greenteapre01-20"></a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1491938455" width="1" height="1" border="0" alt="">
<p>
<a rel="nofollow" href="http://www.amazon.com/gp/product/1491929561/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1491929561&linkCode=as2&tag=greenteapre01-20&linkId=ZY6MAYM33ZTNSCNZ">Think Java</a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1491929561" width="1" height="1" border="0" alt="">
<p>
<a rel="nofollow" href="http://www.amazon.com/gp/product/1491929561/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1491929561&linkCode=as2&tag=greenteapre01-20&linkId=PT77ANWARUNNU3UK"><img border="0" src="http://ws-na.amazon-adsystem.com/widgets/q?_encoding=UTF8&ASIN=1491929561&Format=_SL160_&ID=AsinImage&MarketPlace=US&ServiceVersion=20070822&WS=1&tag=greenteapre01-20"></a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1491929561" width="1" height="1" border="0" alt="">
<p>
<a href="http://www.amazon.com/gp/product/1449370780/ref=as_li_qf_sp_asin_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1449370780&linkCode=as2&tag=greenteapre01-20">Think Bayes</a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1449370780" width="1" height="1" border="0" alt="">
<p>
<a href="http://www.amazon.com/gp/product/1449370780/ref=as_li_qf_sp_asin_il?ie=UTF8&camp=1789&creative=9325&creativeASIN=1449370780&linkCode=as2&tag=greenteapre01-20"><img border="0" src="http://ws-na.amazon-adsystem.com/widgets/q?_encoding=UTF8&ASIN=1449370780&Format=_SL160_&ID=AsinImage&MarketPlace=US&ServiceVersion=20070822&WS=1&tag=greenteapre01-20"></a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1449370780" width="1" height="1" border="0" alt="">
<p>
<a rel="nofollow" href="http://www.amazon.com/gp/product/1491939362/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1491939362&linkCode=as2&tag=greenteapre01-20&linkId=FJKSQ3IHEMY2F2VA">Think Python 2e</a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1491939362" width="1" height="1" border="0" alt="">
<p>
<a rel="nofollow" href="http://www.amazon.com/gp/product/1491939362/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1491939362&linkCode=as2&tag=greenteapre01-20&linkId=ZZ454DLQ3IXDHNHX"><img border="0" src="http://ws-na.amazon-adsystem.com/widgets/q?_encoding=UTF8&ASIN=1491939362&Format=_SL160_&ID=AsinImage&MarketPlace=US&ServiceVersion=20070822&WS=1&tag=greenteapre01-20"></a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1491939362" width="1" height="1" border="0" alt="">
<p>
<a href="http://www.amazon.com/gp/product/1491907339/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1491907339&linkCode=as2&tag=greenteapre01-20&linkId=O7WYM6H6YBYUFNWU">Think Stats 2e</a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1491907339" width="1" height="1" border="0" alt="">
<p>
<a href="http://www.amazon.com/gp/product/1491907339/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1491907339&linkCode=as2&tag=greenteapre01-20&linkId=JVSYKQHYSUIEYRHL"><img border="0" src="http://ws-na.amazon-adsystem.com/widgets/q?_encoding=UTF8&ASIN=1491907339&Format=_SL160_&ID=AsinImage&MarketPlace=US&ServiceVersion=20070822&WS=1&tag=greenteapre01-20"></a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1491907339" width="1" height="1" border="0" alt="">
<p>
<a href="http://www.amazon.com/gp/product/1449314635/ref=as_li_tf_tl?ie=UTF8&tag=greenteapre01-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=1449314635">Think Complexity</a><img class="c003" src="http://www.assoc-amazon.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1449314635" width="1" height="1" border="0" alt="">
<p>
<a href="http://www.amazon.com/gp/product/1449314635/ref=as_li_tf_il?ie=UTF8&camp=1789&creative=9325&creativeASIN=1449314635&linkCode=as2&tag=greenteapre01-20"><img border="0" src="http://ws-na.amazon-adsystem.com/widgets/q?_encoding=UTF8&ASIN=1449314635&Format=_SL160_&ID=AsinImage&MarketPlace=US&ServiceVersion=20070822&WS=1&tag=greenteapre01-20"></a><img class="c003" src="http://www.assoc-amazon.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1449314635" width="1" height="1" border="0" alt="">
</td>
</tr>
</table>
<nav class="navbar navbar-default navbar-fixed-top">
<div class="container-fluid">
<!-- Brand and toggle get grouped for better mobile display -->
<div class="navbar-header">
<button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#bs-example-navbar-collapse-1" aria-expanded="false">
<span class="sr-only">Toggle navigation</span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
<a class="navbar-brand" href="#"><strong>Think Python</strong> - How to Think like a Computer Scientist (2e) <em>by Allen B. Downey</em></a>
</div>
<div>
<ul class="nav navbar-nav navbar-right">
<li><a href="http://greenteapress.com/thinkpython2/html/index.html"><span class="glyphicon glyphicon glyphicon-book" aria-hidden="true"></span></a></li>
<li><a href="thinkpython2012.html"><span class="glyphicon glyphicon glyphicon-menu-left" aria-hidden="true"></span></a></li>
<li><a href="index.html"><span class="glyphicon glyphicon glyphicon-home" aria-hidden="true"></span></a></li>
<li><a href="thinkpython2014.html"><span class="glyphicon glyphicon glyphicon-menu-right" aria-hidden="true"></span></a></li>
<li><a href="http://amzn.to/1VUYQUU"><span class="glyphicon glyphicon glyphicon-shopping-cart" aria-hidden="true"></span></a></li>
</ul>
<div>
</div><!-- /.container-fluid -->
</nav></body>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.3/jquery.min.js"></script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/js/bootstrap.min.js" integrity="sha384-0mSbJDEHialfmuBBQP6A4Qrprq5OVfW37PRR3j5ELqxss1yVqOtnepnHVP9aJ7xS" crossorigin="anonymous"></script>
</html>