attachment:tutorial-programming-python.txt of days28

   1 <span id="tutorial-programming-python"></span><h1>Tutorial: Programming in Python and Sage</h1>
   2 
   3 
   4 </pre><p>This tutorial is an introduction to basic programming in Python/Sage. The
   5 reader is supposed to know the elementary notions of programming but is not
   6 supposed to be familiar with the Python language. The memo given here are far
   7 from being exhaustive. In case you need a more complete tutorial, you can have
   8 a look at the <a class="reference external" href="http://docs.python.org/release/2.6.4/tutorial/index.html">Python Tutorial</a>. Also Python's
   9 <a class="reference external" href="http://docs.python.org/release/2.6.4/">documentation</a> and in particular the
  10 <a class="reference external" href="http://docs.python.org/release/2.6.4/library">standard library</a> can be
  11 useful.</p>
  12 <p>A <a href="#id1"><span class="problematic" id="id2">:ref:`more advanced tutorial &lt;tutorial-objects-and-classes&gt;`</span></a>
  13 presents the notions of objects and classes in Python.</p>
  14 
  15 <p class="system-message-title">System Message: ERROR/3 (<tt class="docutils">tutorial-programming-python.rst</tt>, line 20); <em><a href="#id2">backlink</a></em></p>
  16 Unknown interpreted text role &quot;ref&quot;.
  17 <p>Here is a further list of resources for people wanting to learn Python:</p>
  18 <ul class="simple">
  19 <li><a class="reference external" href="http://www.korokithakis.net/tutorials/python">Learn Python in 10 minutes</a> ou en français
  20 <a class="reference external" href="http://mat.oxyg3n.org/index.php?post/2009/07/26/Python-en-10-minutes">Python en 10 minutes</a></li>
  21 <li><a class="reference external" href="http://diveintopython.org/">Dive into Python</a>
  22 is a Python book for experienced programmers. Also available in French,
  23 <a class="reference external" href="http://diveintopython.adrahon.org/">Plongez au coeur de Python</a>, and
  24 <a class="reference external" href="http://diveintopython.org/#languages">other languages</a>.</li>
  25 <li><a class="reference external" href="http://www.ibm.com/developerworks/views/opensource/libraryview.jsp?search_by=Discover+Python+Part|">Discover Python</a>
  26 is a series of articles published in IBM's <a class="reference external" href="http://www.ibm.com/developerworks/">developerWorks</a> technical resource center.</li>
  27 </ul>
  28 
  29 <h2>Data structures</h2>
  30 <p>In Python, <em>typing is dynamic</em>; there is no such thing as declaring
  31 variables. The function <tt class="docutils literal"><span class="pre">type</span></tt> returns the type of an object <tt class="docutils literal"><span class="pre">obj</span></tt>. To
  32 convert an object to a type <tt class="docutils literal"><span class="pre">typ</span></tt> just write <tt class="docutils literal"><span class="pre">typ(obj)</span></tt> as in
  33 <tt class="docutils literal"><span class="pre">int(&quot;123&quot;)</span></tt>. The command <tt class="docutils literal"><span class="pre">isinstance(ex,</span> <span class="pre">typ)</span></tt> returns whether the
  34 expression <tt class="docutils literal"><span class="pre">ex</span></tt> is of type <tt class="docutils literal"><span class="pre">typ</span></tt>. Specifically, any value is <em>an instance
  35 of a class</em> and there is no difference between classes and types.</p>
  36 <p>The symbol <tt class="docutils literal"><span class="pre">=</span></tt> denotes the affectation to a variable; it should not
  37 be confused with <tt class="docutils literal"><span class="pre">==</span></tt> which denotes mathematical
  38 equality. Inequality is <tt class="docutils literal"><span class="pre">!=</span></tt>.</p>
  39 <p>The <em>standard types</em> are <tt class="docutils literal"><span class="pre">bool</span></tt>, <tt class="docutils literal"><span class="pre">int</span></tt>, <tt class="docutils literal"><span class="pre">list</span></tt>, <tt class="docutils literal"><span class="pre">tuple</span></tt>, <tt class="docutils literal"><span class="pre">set</span></tt>,
  40 <tt class="docutils literal"><span class="pre">dict</span></tt>, <tt class="docutils literal"><span class="pre">str</span></tt>.</p>
  41 <ul>
  42 <li><p class="first">The type <tt class="docutils literal"><span class="pre">bool</span></tt> (<em>Booleans</em>) takes two values: <tt class="docutils literal"><span class="pre">True</span></tt> and <tt class="docutils literal"><span class="pre">False</span></tt>. The
  43 boolean operator are denoted by their names <tt class="docutils literal"><span class="pre">or</span></tt>, <tt class="docutils literal"><span class="pre">and</span></tt>, <tt class="docutils literal"><span class="pre">not</span></tt>.</p>
  44 </li>
  45 <li><p class="first">Sage uses <em>exact arithmetic</em> on the integers. For performance reason, it
  46 uses its own type named <tt class="docutils literal"><span class="pre">Integer</span></tt> (whereas python uses the types <tt class="docutils literal"><span class="pre">int</span></tt>
  47 and <tt class="docutils literal"><span class="pre">long</span></tt>).</p>
  48 </li>
  49 <li><p class="first">A <em>list</em> is a data structure which groups values. It is constructed using
  50 brackets as in <tt class="docutils literal"><span class="pre">[1,</span> <span class="pre">3,</span> <span class="pre">4]</span></tt>. The <tt class="docutils literal"><span class="pre">range</span></tt> function creates integer
  51 lists. One can also create lists using <em>list comprehension</em>:</p>
  52 <pre class="literal-block">
  53 [ &lt;expr&gt; for &lt;name&gt; in &lt;iterable&gt; (if &lt;condition&gt;) ]
  54 
  55 </pre><p>For example:</p>
  56 
  57 {{{id=0|
  58 [ i^2 for i in range(10) if i % 2 == 0 ]
  59 ///
  60 [0, 4, 16, 36, 64]
  61 }}}
  62 
  63 </li>
  64 <li><p class="first">A <em>tuple</em> is very similar to a list; it is constructed using
  65 parentheses. The empty tuple is obtained by <tt class="docutils literal"><span class="pre">()</span></tt> or by the
  66 constructor <tt class="docutils literal"><span class="pre">tuple()</span></tt>. If there is only one element, one has to
  67 write <tt class="docutils literal"><span class="pre">(a,)</span></tt>. A tuple is <em>immutable</em> (one cannot change it) but it
  68 is <em>hashable</em> (see below). One can also create tuples using
  69 comprehensions:</p>
  70 
  71 {{{id=1|
  72 tuple(i^2 for i in range(10) if i % 2 == 0)
  73 ///
  74 (0, 4, 16, 36, 64)
  75 }}}
  76 
  77 </li>
  78 <li><p class="first">A <em>set</em> is a data structure which contains values without
  79 multiplicities or order. One creates it from a list (or any
  80 iterable) with the constructor <tt class="docutils literal"><span class="pre">set()</span></tt>. The elements of a set must
  81 be hashable:</p>
  82 
  83 {{{id=2|
  84 set([2,2,1,4,5])
  85 ///
  86 set([1, 2, 4, 5])
  87 }}}
  88 
  89 </li>
  90 <li><p class="first">A <em>dictionary</em> is an association table, which associate values to
  91 keys. Keys must be hashable. One creates dictionaries using the
  92 constructor <tt class="docutils literal"><span class="pre">dict</span></tt>, or using the syntax:</p>
  93 <pre class="literal-block">
  94 {&nbsp;key1 : value1, key2 : value2 ...}&nbsp;
  95 
  96 </pre><p>For example:</p>
  97 
  98 {{{id=3|
  99 age = {'toto' : 8, 'mom' : 27}; age
 100 ///
 101 {'toto': 8, 'mom': 27}
 102 }}}
 103 
 104 </li>
 105 <li><p class="first">Quotes (simple <tt class="docutils literal"><span class="pre">'</span> <span class="pre">'</span></tt> or double <tt class="docutils literal"><span class="pre">&quot;</span> <span class="pre">&quot;</span></tt>) encloses <em>character
 106 strings</em>. One can concatenate them using <tt class="docutils literal"><span class="pre">+</span></tt>.</p>
 107 </li>
 108 <li><p class="first">For lists, tuples, strings, and dictionaries, the <em>indexing
 109 operator</em> is written <tt class="docutils literal"><span class="pre">l[i]</span></tt>. For lists, tuples, and strings one
 110 can also uses <em>slices</em> as <tt class="docutils literal"><span class="pre">l[:]</span></tt>, <tt class="docutils literal"><span class="pre">l[:b]</span></tt>, <tt class="docutils literal"><span class="pre">l[a:]</span></tt>, or
 111 <tt class="docutils literal"><span class="pre">l[a:b]</span></tt>. Negative indices start from the end.</p>
 112 </li>
 113 <li><p class="first">The <tt class="docutils literal"><span class="pre">len</span></tt> function returns the number of elements of a list, a
 114 tuple, a set, a string, or a dictionary. One writes <tt class="docutils literal"><span class="pre">x</span> <span class="pre">in</span> <span class="pre">C</span></tt> to
 115 tests whether <tt class="docutils literal"><span class="pre">x</span></tt> is in <tt class="docutils literal"><span class="pre">C</span></tt>.</p>
 116 </li>
 117 <li><p class="first">Finally there is a special value called <tt class="docutils literal"><span class="pre">None</span></tt> to denote the
 118 absence of a value.</p>
 119 </li>
 120 </ul>
 121 
 122 
 123 <h2>Control structures</h2>
 124 <p>In Python, there is no keyword for the beginning and the end of an
 125 instructions block. Blocks are delimited thanks to indentation. Most
 126 of the time a new block is introduced by <tt class="docutils literal"><span class="pre">:</span></tt>. Python has the
 127 following control structures:</p>
 128 <ul>
 129 <li><p class="first">Conditional instruction:</p>
 130 <pre class="literal-block">
 131 if &lt;condition&gt;:
 132     &lt;instruction sequence&gt;
 133 [elif &lt;condition&gt;:
 134     &lt;instruction sequence&gt;]*
 135 [else:
 136     &lt;instruction sequence&gt;]
 137 
 138 </pre></li>
 139 <li><p class="first">Inside expression exclusively, one can write:</p>
 140 <pre class="literal-block">
 141 &lt;value&gt; if &lt;condition&gt; else &lt;value&gt;
 142 
 143 </pre></li>
 144 <li><p class="first">Iterative instructions:</p>
 145 <pre class="literal-block">
 146 for &lt;name&gt; in &lt;iterable&gt;:
 147     &lt;instruction sequence&gt;
 148 [else:
 149     &lt;instruction sequence&gt;]
 150 
 151 </pre><pre class="literal-block">
 152 while &lt;condition&gt;:
 153     &lt;instruction sequence&gt;
 154 [else:
 155     &lt;instruction sequence&gt;]
 156 
 157 </pre><p>The <tt class="docutils literal"><span class="pre">else</span></tt> bloc is executed at the end of the loop if the loop is
 158 ended normally, that is neither by a <tt class="docutils literal"><span class="pre">break</span></tt> nor an exception.</p>
 159 </li>
 160 <li><p class="first">In a loop, <tt class="docutils literal"><span class="pre">continue</span></tt> jumps to the next iteration.</p>
 161 </li>
 162 <li><p class="first">An iterable is an object which can be iterated through. Iterable
 163 types include lists, tuples, dictionaries, and strings.</p>
 164 </li>
 165 <li><p class="first">An error (also called exception) is raised by:</p>
 166 <pre class="literal-block">
 167 raise &lt;ErrorType&gt; [, error message]
 168 
 169 </pre><p>Usual errors includes <tt class="docutils literal"><span class="pre">ValueError</span></tt> and <tt class="docutils literal"><span class="pre">TypeError</span></tt>.</p>
 170 </li>
 171 </ul>
 172 
 173 
 174 <h2>Functions</h2>
 175 
 176 <p class="first admonition-title">Note</p>
 177 <p>Python functions vs. mathematical functions</p>
 178 <p class="last">In what follows, we deal with <em>functions</em> is the sense of
 179 <em>programming languages</em>. Mathematical functions are handled by
 180 sage in a different way. In particular it doesn't make sense to do
 181 mathematical manipulation such as additions or derivations on
 182 Python functions.</p>
 183 
 184 <p>One defines a function using the keyword <tt class="docutils literal"><span class="pre">def</span></tt> as</p>
 185 <pre class="literal-block">
 186 def &lt;name&gt;(&lt;argument list&gt;):
 187      &lt;instruction sequence&gt;
 188 
 189 </pre><p>The result of the function is given by the instruction
 190 <tt class="docutils literal"><span class="pre">return</span></tt>. Very short functions can be created anonymously using
 191 <tt class="docutils literal"><span class="pre">lambda</span></tt> (remark that there is no return here):</p>
 192 <pre class="literal-block">
 193 lambda &lt;arguments&gt;: &lt;expression&gt;
 194 
 195 </pre><p class="first admonition-title">Note</p>
 196 <p>(functional programming)</p>
 197 <p class="last">Functions are objects as any other objects. One can assign them to
 198 variables or return them.</p>
 199 
 200 
 201 
 202 
 203 <h1>Exercises</h1>
 204 
 205 <h2>Lists</h2>
 206 
 207 <h3>Creating Lists I: [Square brackets]</h3>
 208 <p><strong>Example:</strong></p>
 209 
 210 {{{id=4|
 211 L = [3, Permutation([5,1,4,2,3]), 17, 17, 3, 51]
 212 L
 213 ///
 214 [3, [5, 1, 4, 2, 3], 17, 17, 3, 51]
 215 }}}
 216 
 217 <p><strong>Exercise:</strong> Create the list $[63, 12, -10, 'a', 12]$, assign it to
 218 the variable <tt class="docutils literal"><span class="pre">L</span></tt>, and print the list.</p>
 219 
 220 {{{id=5|
 221 
 222 ///
 223 }}}
 224 
 225 <p><strong>Exercise:</strong> Create the empty list (you will often need to do this).</p>
 226 
 227 {{{id=6|
 228 
 229 ///
 230 }}}
 231 
 232 <h3>Creating Lists II: range</h3>
 233 <p>The <em>range</em> function provides an easy way to construct a list of
 234 integers. Here is the documentation of the <em>range</em> function:</p>
 235 <pre class="literal-block">
 236 range([start,] stop[, step]) -&gt; list of integers
 237 
 238 Return a list containing an arithmetic progression of integers.
 239 range(i, j) returns [i, i+1, i+2, ..., j-1]; start (!) defaults to 0.
 240 When step is given, it specifies the increment (or decrement). For
 241 example, range(4) returns [0, 1, 2, 3].  The end point is omitted!
 242 These are exactly the valid indices for a list of 4 elements.
 243 
 244 </pre><p><strong>Exercise:</strong> Use <em>range</em> to construct the list $[1,2,ldots,50]$.</p>
 245 
 246 {{{id=7|
 247 
 248 ///
 249 }}}
 250 
 251 <p><strong>Exercise:</strong> Use <em>range</em> to construct the list of <em>even</em> numbers
 252 between 1 and 100 (including 100).</p>
 253 
 254 {{{id=8|
 255 
 256 ///
 257 }}}
 258 
 259 <p><strong>Exercise:</strong> The <em>step</em> argument for the <em>range</em> command can be negative. Use
 260 <em>range</em> to construct the list $[10, 7, 4, 1, -2]$.</p>
 261 
 262 {{{id=9|
 263 
 264 ///
 265 }}}
 266 
 267 <h3>Creating Lists III: list comprehensions</h3>
 268 <p><em>List comprehensions</em> provide a concise way to create lists from other lists
 269 (or other data types).</p>
 270 <p><strong>Example</strong> We already know how to create the list $[1, 2, dots, 16]$:</p>
 271 
 272 {{{id=10|
 273 range(1,17)
 274 ///
 275 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
 276 }}}
 277 
 278 <p>Using a <em>list comprehension</em>, we can now create the list
 279 $[1^2, 2^2, 3^2, dots, 16^2]$ as follows:</p>
 280 
 281 {{{id=11|
 282 [i^2 for i in range(1,17)]
 283 ///
 284 [1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256]
 285 }}}
 286 
 287 
 288 {{{id=12|
 289 sum([i^2 for i in range(1,17)])
 290 ///
 291 1496
 292 }}}
 293 
 294 <p><strong>Exercice:</strong></p>
 295 <p>The sum of the squares of the first ten natural numbers is</p>
 296 
 297 <p class="system-message-title">System Message: ERROR/3 (<tt class="docutils">tutorial-programming-python.rst</tt>, line 301)</p>
 298 <p>Unknown directive type &quot;math&quot;.</p>
 299 <pre class="literal-block">
 300 .. math:: (1^2 + 2^2 + ... + 10^2) = 385
 301 
 302 
 303 </pre><p>The square of the sum of the first ten natural numbers is</p>
 304 
 305 <p class="system-message-title">System Message: ERROR/3 (<tt class="docutils">tutorial-programming-python.rst</tt>, line 305)</p>
 306 <p>Unknown directive type &quot;math&quot;.</p>
 307 <pre class="literal-block">
 308 .. math:: (1 + 2 + ... + 10)^2 = 55^2 = 3025
 309 
 310 
 311 </pre><p>Hence the difference between the sum of the squares of the first ten natural
 312 numbers and the square of the sum is</p>
 313 
 314 <p class="system-message-title">System Message: ERROR/3 (<tt class="docutils">tutorial-programming-python.rst</tt>, line 310)</p>
 315 <p>Unknown directive type &quot;math&quot;.</p>
 316 <pre class="literal-block">
 317 .. math:: 3025 - 385 = 2640
 318 
 319 
 320 </pre><p>Find the difference between the sum of the squares of the first one hundred
 321 natural numbers and the square of the sum.</p>
 322 
 323 {{{id=13|
 324 
 325 ///
 326 }}}
 327 
 328 
 329 {{{id=14|
 330 
 331 ///
 332 }}}
 333 
 334 
 335 {{{id=15|
 336 
 337 ///
 338 }}}
 339 
 340 <h4>Filtering lists with a list comprehension</h4>
 341 <p>A list can be <em>filtered</em> using a list comprehension.</p>
 342 <p><strong>Example:</strong> To create a list of the squares of the prime numbers between 1
 343 and 100, we use a list comprehension as follows.</p>
 344 
 345 {{{id=16|
 346 [p^2 for p in [1,2,..,100] if is_prime(p)]
 347 ///
 348 [4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409]
 349 }}}
 350 
 351 <p><strong>Exercise:</strong> Use a <em>list comprehension</em> to list all the natural numbers below
 352 20 that are multiples of 3 or 5. Hint:</p>
 353 <ul class="simple">
 354 <li>To get the remainder of 7 divided by 3 use <em>7%3</em>.</li>
 355 <li>To test for equality use two equal signs (<em>==</em>); for example, <em>3 == 7</em>.</li>
 356 </ul>
 357 
 358 {{{id=17|
 359 
 360 ///
 361 }}}
 362 
 363 <h4>Nested list comprehensions</h4>
 364 <p>List comprehensions can be nested!</p>
 365 <p><strong>Examples:</strong></p>
 366 
 367 {{{id=18|
 368 [(x,y) for x in range(5) for y in range(3)]
 369 ///
 370 [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2)]
 371 }}}
 372 
 373 
 374 {{{id=19|
 375 [[i^j for j in range(1,4)] for i in range(6)]
 376 ///
 377 [[0, 0, 0], [1, 1, 1], [2, 4, 8], [3, 9, 27], [4, 16, 64], [5, 25, 125]]
 378 }}}
 379 
 380 
 381 {{{id=20|
 382 matrix([[i^j for j in range(1,4)] for i in range(6)])
 383 ///
 384 [  0   0   0][  1   1   1][  2   4   8][  3   9  27][  4  16  64][  5  25 125]
 385 }}}
 386 
 387 <p><strong>Exercise:</strong></p>
 388 <p>A <em>Pythagorean triple</em> is a triple $(x,y,z)$ of <em>positive</em> integers satisfying
 389 $x^2+y^2=z^2$. The Pythagorean triples whose components are at most $10$ are:</p>
 390 
 391 <p class="system-message-title">System Message: ERROR/3 (<tt class="docutils">tutorial-programming-python.rst</tt>, line 398)</p>
 392 <p>Unknown directive type &quot;math&quot;.</p>
 393 <pre class="literal-block">
 394 .. math:: [(3, 4, 5), (4, 3, 5), (6, 8, 10), (8, 6, 10)]\,.
 395 
 396 
 397 </pre><p>Using a filtered list comprehension, construct the list of Pythagorean triples
 398 whose components are at most $50$.</p>
 399 
 400 {{{id=21|
 401 
 402 ///
 403 }}}
 404 
 405 
 406 {{{id=22|
 407 
 408 ///
 409 }}}
 410 
 411 <h3>Accessing individual elements of lists</h3>
 412 <p>To access an element of the list, use the syntax <tt class="docutils literal"><span class="pre">L[i]</span></tt>, where $i$ is the
 413 index of the item.</p>
 414 <p><strong>Exercise:</strong></p>
 415 <blockquote>
 416 <ol class="arabic">
 417 <li><p class="first">Construct the list <tt class="docutils literal"><span class="pre">L</span> <span class="pre">=</span> <span class="pre">[1,2,3,4,3,5,6]</span></tt>. What is <tt class="docutils literal"><span class="pre">L[3]</span></tt>?</p>
 418 
 419 {{{id=23|
 420 
 421 ///
 422 }}}
 423 
 424 </li>
 425 <li><p class="first">What is <tt class="docutils literal"><span class="pre">L[1]</span></tt>?</p>
 426 
 427 {{{id=24|
 428 
 429 ///
 430 }}}
 431 
 432 </li>
 433 <li><p class="first">What is the index of the first element of <tt class="docutils literal"><span class="pre">L</span></tt>?</p>
 434 
 435 {{{id=25|
 436 
 437 ///
 438 }}}
 439 
 440 </li>
 441 <li><p class="first">What is <tt class="docutils literal"><span class="pre">L[-1]</span></tt>? What is <tt class="docutils literal"><span class="pre">L[-2]</span></tt>?</p>
 442 
 443 {{{id=26|
 444 
 445 ///
 446 }}}
 447 
 448 </li>
 449 <li><p class="first">What is <tt class="docutils literal"><span class="pre">L.index(2)</span></tt>? What is <tt class="docutils literal"><span class="pre">L.index(3)</span></tt>?</p>
 450 
 451 {{{id=27|
 452 
 453 ///
 454 }}}
 455 
 456 </li>
 457 </ol>
 458 </blockquote>
 459 
 460 
 461 <h3>Modifying lists: changing an element in a list</h3>
 462 <p>To change the item in position <tt class="docutils literal"><span class="pre">i</span></tt> of a list <tt class="docutils literal"><span class="pre">L</span></tt>:</p>
 463 
 464 {{{id=28|
 465 L = [&quot;a&quot;, 4, 1, 8]
 466 L
 467 ///
 468 ['a', 4, 1, 8]
 469 }}}
 470 
 471 <!-- link -->
 472 
 473 {{{id=29|
 474 L[2] = 0
 475 L
 476 ///
 477 ['a', 4, 0, 8]
 478 }}}
 479 
 480 <h3>Modifying lists: append and extend</h3>
 481 <p>To <em>append</em> an object to a list:</p>
 482 
 483 {{{id=30|
 484 L = [&quot;a&quot;, 4, 1, 8]
 485 L
 486 ///
 487 ['a', 4, 1, 8]
 488 }}}
 489 
 490 <!-- link -->
 491 
 492 {{{id=31|
 493 L.append(17)
 494 L
 495 ///
 496 ['a', 4, 1, 8, 17]
 497 }}}
 498 
 499 <p>To <em>extend</em> a list by another list:</p>
 500 
 501 {{{id=32|
 502 L1 = [1,2,3]
 503 L2 = [7,8,9,0]
 504 print L1
 505 ///
 506 [1, 2, 3]
 507 }}}
 508 
 509 {{{id=33|
 510 print L2
 511 ///
 512 [7, 8, 9, 0]
 513 }}}
 514 
 515 <!-- link -->
 516 
 517 {{{id=34|
 518 L1.extend(L2)
 519 L1
 520 ///
 521 [1, 2, 3, 7, 8, 9, 0]
 522 }}}
 523 
 524 <h3>Modifying lists: reverse, sort, ...</h3>
 525 
 526 {{{id=35|
 527 L = [4,2,5,1,3]
 528 L
 529 ///
 530 [4, 2, 5, 1, 3]
 531 }}}
 532 
 533 <!-- link -->
 534 
 535 {{{id=36|
 536 L.reverse()
 537 L
 538 ///
 539 [3, 1, 5, 2, 4]
 540 }}}
 541 
 542 <!-- link -->
 543 
 544 {{{id=37|
 545 L.sort()
 546 L
 547 ///
 548 [1, 2, 3, 4, 5]
 549 }}}
 550 
 551 
 552 {{{id=38|
 553 L = [3,1,6,4]
 554 sorted(L)
 555 ///
 556 [1, 3, 4, 6]
 557 }}}
 558 
 559 <!-- link -->
 560 
 561 {{{id=39|
 562 L
 563 ///
 564 [3, 1, 6, 4]
 565 }}}
 566 
 567 <h3>Concatenating Lists</h3>
 568 <p>To concatenate two lists, add them with the operator <tt class="docutils literal"><span class="pre">+</span></tt>. This is not a commutative operation....</p>
 569 
 570 {{{id=40|
 571 L1 = [1,2,3]
 572 L2 = [7,8,9,0]
 573 L1 + L2
 574 ///
 575 [1, 2, 3, 7, 8, 9, 0]
 576 }}}
 577 
 578 <h3>Slicing Lists</h3>
 579 <p>You can slice a list using the syntax <tt class="docutils literal"><span class="pre">L[start</span> <span class="pre">:</span> <span class="pre">stop</span> <span class="pre">:</span> <span class="pre">step]</span></tt>. This will
 580 return a sublist of <tt class="docutils literal"><span class="pre">L</span></tt>.</p>
 581 <p><strong>Exercise:</strong> Below are some examples of slicing lists. Try to guess what the output will be before evaluating the cell.</p>
 582 
 583 {{{id=41|
 584 L = range(20)
 585 L
 586 ///
 587 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
 588 }}}
 589 
 590 <!-- link -->
 591 
 592 {{{id=42|
 593 L[3:15]
 594 ///
 595 [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
 596 }}}
 597 
 598 <!-- link -->
 599 
 600 {{{id=43|
 601 L[3:15:2]
 602 ///
 603 [3, 5, 7, 9, 11, 13]
 604 }}}
 605 
 606 <!-- link -->
 607 
 608 {{{id=44|
 609 L[15:3:-1]
 610 ///
 611 [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4]
 612 }}}
 613 
 614 <!-- link -->
 615 
 616 {{{id=45|
 617 L[:4]
 618 ///
 619 [0, 1, 2, 3]
 620 }}}
 621 
 622 <!-- link -->
 623 
 624 {{{id=46|
 625 L[:]
 626 ///
 627 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
 628 }}}
 629 
 630 <!-- link -->
 631 
 632 {{{id=47|
 633 L[::-1]
 634 ///
 635 [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
 636 }}}
 637 
 638 <p><strong>Advanced exercise:</strong> The following function combines a loop with the some of
 639 the list operations above. What does the function do?</p>
 640 
 641 {{{id=48|
 642 def f(number_of_iterations):
 643        L = [1]
 644        for n in range(2, number_of_iterations):
 645            L = [sum(L[:i]) for i in range(n-1, -1, -1)]
 646        return numerical_approx(2*L[0]*len(L)/sum(L), digits=50)
 647 ///
 648 }}}
 649 
 650 <!-- link -->
 651 
 652 {{{id=49|
 653 f(10)
 654 ///
 655 3.1413810483870967741935483870967741935483870967742
 656 }}}
 657 
 658 <h2>Tuples</h2>
 659 <p>A <em>tuple</em> is an <em>immutable</em> list. That is, it cannot be changed once it is
 660 created. The syntax for creating a tuple is to the use parentheses.</p>
 661 
 662 {{{id=50|
 663 t = (3, 5, [3,1], (17,[2,3],17), 4)
 664 t
 665 ///
 666 (3, 5, [3, 1], (17, [2, 3], 17), 4)
 667 }}}
 668 
 669 <p>We can create a tuple from a list, or vice-versa.</p>
 670 <!-- link -->
 671 
 672 {{{id=51|
 673 tuple(range(5))
 674 ///
 675 (0, 1, 2, 3, 4)
 676 }}}
 677 
 678 <!-- link -->
 679 
 680 {{{id=52|
 681 list(t)
 682 ///
 683 [3, 5, [3, 1], (17, [2, 3], 17), 4]
 684 }}}
 685 
 686 <p>Tuples behave like lists in many respects:</p>
 687 <table border="1" class="docutils">
 688 <colgroup>
 689 <col width="30%">
 690 <col width="35%">
 691 <col width="35%">
 692 </colgroup>
 693 <thead valign="bottom">
 694 <tr><th class="head">Operation</th>
 695 <th class="head">Syntax for lists</th>
 696 <th class="head">Syntax for tuples</th>
 697 </tr>
 698 </thead>
 699 <tbody valign="top">
 700 <tr><td>Accessing a letter</td>
 701 <td><tt class="docutils literal"><span class="pre">list[3]</span></tt></td>
 702 <td><tt class="docutils literal"><span class="pre">tuple[3]</span></tt></td>
 703 </tr>
 704 <tr><td>Concatenation</td>
 705 <td><tt class="docutils literal"><span class="pre">list1</span> <span class="pre">+</span> <span class="pre">list2</span></tt></td>
 706 <td><tt class="docutils literal"><span class="pre">tuple1</span> <span class="pre">+</span> <span class="pre">tuple2</span></tt></td>
 707 </tr>
 708 <tr><td>Slicing</td>
 709 <td><tt class="docutils literal"><span class="pre">list[3:17:2]</span></tt></td>
 710 <td><tt class="docutils literal"><span class="pre">tuple[3:17:2]</span></tt></td>
 711 </tr>
 712 <tr><td>A reversed copy</td>
 713 <td><tt class="docutils literal"><span class="pre">list[::-1]</span></tt></td>
 714 <td><tt class="docutils literal"><span class="pre">tuple[::-1]</span></tt></td>
 715 </tr>
 716 <tr><td>Length</td>
 717 <td><tt class="docutils literal"><span class="pre">len(list)</span></tt></td>
 718 <td><tt class="docutils literal"><span class="pre">len(tuple)</span></tt></td>
 719 </tr>
 720 </tbody>
 721 </table>
 722 <p>Trying to modify a tuple will fail.</p>
 723 
 724 {{{id=53|
 725 t = (5, 'a', 6/5)
 726 t
 727 ///
 728 (5, 'a', 6/5)
 729 }}}
 730 
 731 <!-- link -->
 732 
 733 {{{id=54|
 734 t[1] = 'b'
 735 ///
 736 Traceback (most recent call last):
 737 TypeError: 'tuple' object does not support item assignment
 738 }}}
 739 
 740 <h2>Generators</h2>
 741 <p>&quot;Tuple-comprehension&quot; does not exist.  The syntax produces something called a
 742 generator.  A generator allows you to process a sequence of items one at a
 743 time.  Each item is created when it is needed, and then forgotten.  This can
 744 be very efficient if we only need to use each item once.</p>
 745 
 746 {{{id=55|
 747 (i^2 for i in range(5))
 748 ///
 749 <generator object <genexpr> at 0x...>
 750 }}}
 751 
 752 
 753 {{{id=56|
 754 g = (i^2 for i in range(5))
 755 g[0]
 756 ///
 757 Traceback (most recent call last):
 758 TypeError: 'generator' object is unsubscriptable
 759 }}}
 760 
 761 <!-- link -->
 762 
 763 {{{id=57|
 764 [x for x in g]
 765 ///
 766 [0, 1, 4, 9, 16]
 767 }}}
 768 
 769 <p><tt class="docutils literal"><span class="pre">g</span></tt> is now empty.</p>
 770 <!-- link -->
 771 
 772 {{{id=58|
 773 [x for x in g]
 774 ///
 775 []
 776 }}}
 777 
 778 <p>A nice 'pythonic' trick is to use generators as the argument to functions.  We
 779 do <em>not</em> need double parentheses for this.</p>
 780 
 781 {{{id=59|
 782 sum( i^2 for i in srange(100001) )
 783 ///
 784 333338333350000
 785 }}}
 786 
 787 <h2>Dictionaries</h2>
 788 <p>A <em>dictionary</em> is another built-in data type. Unlike lists, which are indexed by a range of numbers, dictionaries are &quot;indexed&quot; by <em>keys</em>, which can be any immutable object. Strings and numbers can always be keys (because they are immutable). Dictionaries are sometimes called &quot;associative arrays&quot; in other programming languages.</p>
 789 <p>There are several ways to define dictionaries. One method is to use braces, {}, with comma-separated entries given in the form <em>key:value</em>.</p>
 790 
 791 {{{id=60|
 792 d = {3:17, &quot;key&quot;:[4,1,5,2,3], (3,1,2):&quot;goo&quot;, 3/2 : 17}
 793 d
 794 ///
 795 {3/2: 17, 3: 17, (3, 1, 2): 'goo', 'key': [4, 1, 5, 2, 3]}
 796 }}}
 797 
 798 <p>Dictionaries behave as lists and tuples for several important operations.</p>
 799 <table border="1" class="docutils">
 800 <colgroup>
 801 <col width="28%">
 802 <col width="32%">
 803 <col width="40%">
 804 </colgroup>
 805 <thead valign="bottom">
 806 <tr><th class="head">Operation</th>
 807 <th class="head">Syntax for lists</th>
 808 <th class="head">Syntax for dictionaries</th>
 809 </tr>
 810 </thead>
 811 <tbody valign="top">
 812 <tr><td>Accessing elements</td>
 813 <td><tt class="docutils literal"><span class="pre">list[3]</span></tt></td>
 814 <td><tt class="docutils literal"><span class="pre">D[&quot;key&quot;]</span></tt></td>
 815 </tr>
 816 <tr><td>Length</td>
 817 <td><tt class="docutils literal"><span class="pre">len(list)</span></tt></td>
 818 <td><tt class="docutils literal"><span class="pre">len(D)</span></tt></td>
 819 </tr>
 820 <tr><td>Modifying</td>
 821 <td><tt class="docutils literal"><span class="pre">L[3]</span> <span class="pre">=</span> <span class="pre">17</span></tt></td>
 822 <td><tt class="docutils literal"><span class="pre">D[&quot;key&quot;]</span> <span class="pre">=</span> <span class="pre">17</span></tt></td>
 823 </tr>
 824 <tr><td>Deleting items</td>
 825 <td><tt class="docutils literal"><span class="pre">del</span> <span class="pre">L[3]</span></tt></td>
 826 <td><tt class="docutils literal"><span class="pre">del</span> <span class="pre">D[&quot;key&quot;]</span></tt></td>
 827 </tr>
 828 </tbody>
 829 </table>
 830 <!-- link -->
 831 
 832 {{{id=61|
 833 d[10]='a'
 834 d
 835 ///
 836 {3/2: 17, 10: 'a', 3: 17, (3, 1, 2): 'goo', 'key': [4, 1, 5, 2, 3]}
 837 }}}
 838 
 839 <p>A dictionary can have the same value multiple times, but each key can only
 840 appear once and must be immutable.</p>
 841 
 842 {{{id=62|
 843 d = {3: 14, 4: 14}
 844 d
 845 ///
 846 {3: 14, 4: 14}
 847 }}}
 848 
 849 
 850 {{{id=63|
 851 d = {3: 13, 3: 14}
 852 d
 853 ///
 854 {3: 14}
 855 }}}
 856 
 857 
 858 {{{id=64|
 859 d = {[1,2,3] : 12}
 860 ///
 861 Traceback (most recent call last):
 862 TypeError: unhashable type: 'list'
 863 }}}
 864 
 865 <p>Another way to add items to a dictionary is with the <tt class="docutils literal"><span class="pre">update()</span></tt> method:</p>
 866 
 867 {{{id=65|
 868 d = {}
 869 d
 870 ///
 871 {}
 872 }}}
 873 
 874 <!-- link -->
 875 
 876 {{{id=66|
 877 d.update( {10 : 'newvalue', 20: 'newervalue', 3: 14, 'a':[1,2,3]} )
 878 d
 879 ///
 880 {'a': [1, 2, 3], 10: 'newvalue', 3: 14, 20: 'newervalue'}
 881 }}}
 882 
 883 <p>We can iterate through the <em>keys</em>, or <em>values</em>, or both, of a dictionary.</p>
 884 
 885 {{{id=67|
 886 d = {10 : 'newvalue', 20: 'newervalue', 3: 14, 'a':[1,2,3]}
 887 ///
 888 }}}
 889 
 890 <!-- link -->
 891 
 892 {{{id=68|
 893 [key for key in d]
 894 ///
 895 ['a', 10, 3, 20]
 896 }}}
 897 
 898 <!-- link -->
 899 
 900 {{{id=69|
 901 [key for key in d.iterkeys()]
 902 ///
 903 ['a', 10, 3, 20]
 904 }}}
 905 
 906 <!-- link -->
 907 
 908 {{{id=70|
 909 [value for value in d.itervalues()]
 910 ///
 911 [[1, 2, 3], 'newvalue', 14, 'newervalue']
 912 }}}
 913 
 914 <!-- link -->
 915 
 916 {{{id=71|
 917 [(key, value) for key, value in d.iteritems()]
 918 ///
 919 [('a', [1, 2, 3]), (10, 'newvalue'), (3, 14), (20, 'newervalue')]
 920 }}}
 921 
 922 <p><strong>Exercise:</strong> Consider the following directed graph.</p>
 923 <img alt="media/graph0.png" src="media/graph0.png">
 924 <p>Create a dictionary whose keys are the vertices of the above directed graph,
 925 and whose values are the lists of the vertices that it points to. For
 926 instance, the vertex 1 points to the vertices 2 and 3, so the dictionary will
 927 look like:</p>
 928 <pre class="literal-block">
 929 d = {&nbsp; ..., 1:[2,3], ... }&nbsp;
 930 
 931 </pre>
 932 {{{id=72|
 933 
 934 ///
 935 }}}
 936 
 937 <p>Then try</p>
 938 <!-- skip -->
 939 
 940 {{{id=73|
 941 g = DiGraph(d)
 942 g.plot()
 943 ///
 944 }}}
 945 
 946 <h2>Using Sage types: The srange command</h2>
 947 <p><strong>Example:</strong> Construct a $3 times 3$ matrix whose $(i,j)$ entry is the
 948 rational number $frac{i}{j}$. The integer generated by <tt class="docutils literal"><span class="pre">range</span></tt> are
 949 python <tt class="docutils literal"><span class="pre">int</span></tt>. As a consequence, dividing them does euclidian division.</p>
 950 
 951 {{{id=74|
 952 matrix([[ i/j for j in range(1,4)] for i in range(1,4)])
 953 ///
 954 [1 0 0][2 1 0][3 1 1]
 955 }}}
 956 
 957 <p>Whereas Dividing sage <tt class="docutils literal"><span class="pre">Integer</span></tt> gives a fraction</p>
 958 
 959 {{{id=75|
 960 matrix([[ i/j for j in srange(1,4)] for i in srange(1,4)])
 961 ///
 962 [  1 1/2 1/3][  2   1 2/3][  3 3/2   1]
 963 }}}
 964 
 965 <h2>Modifying lists has consequences!</h2>
 966 <p>Try to predict the results of the following commands.</p>
 967 
 968 {{{id=76|
 969 a = [1, 2, 3]
 970 L = [a, a, a]
 971 L
 972 ///
 973 [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
 974 }}}
 975 
 976 <!-- link -->
 977 
 978 {{{id=77|
 979 a.append(4)
 980 L
 981 ///
 982 [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]
 983 }}}
 984 
 985 <p>Now try these:</p>
 986 
 987 {{{id=78|
 988 a = [1, 2, 3]
 989 L = [a, a, a]
 990 L
 991 ///
 992 [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
 993 }}}
 994 
 995 <!-- link -->
 996 
 997 {{{id=79|
 998 a = [1, 2, 3, 4]
 999 L
1000 ///
1001 [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
1002 }}}
1003 
1004 <!-- link -->
1005 
1006 {{{id=80|
1007 L[0].append(4)
1008 L
1009 ///
1010 [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]
1011 }}}
1012 
1013 <p>You can use the command <em>deepcopy</em> to avoid these issues.</p>
1014 
1015 {{{id=81|
1016 a = [1,2,3]
1017 L = [deepcopy(a), deepcopy(a)]
1018 L
1019 ///
1020 [[1, 2, 3], [1, 2, 3]]
1021 }}}
1022 
1023 <!-- link -->
1024 
1025 {{{id=82|
1026 a.append(4)
1027 L
1028 ///
1029 [[1, 2, 3], [1, 2, 3]]
1030 }}}
1031 
1032 <p>The same issues occur with dictionaries.</p>
1033 
1034 {{{id=83|
1035 d = {1:'a', 2:'b', 3:'c'}
1036 dd = d
1037 d.update( { 4:'d' } )
1038 dd
1039 ///
1040 {1: 'a', 2: 'b', 3: 'c', 4: 'd'}
1041 }}}
1042 
1043 <h1>Loops and Functions</h1>
1044 <p>For more verbose explanation of what's going on here, a good place to look is
1045 at the following section of the Python tutorial:
1046 <a class="reference external" href="http://docs.python.org/tutorial/controlflow.html">http://docs.python.org/tutorial/controlflow.html</a></p>
1047 
1048 <h2>While Loops</h2>
1049 <p>While loops tend not to be used nearly as much as for loops in Python code.</p>
1050 
1051 {{{id=84|
1052 i = 0
1053 while i &lt; 10:
1054        print i
1055        i += 1
1056 ///
1057 0123456789
1058 }}}
1059 
1060 
1061 {{{id=85|
1062 i = 0
1063 while i &lt; 10:
1064        if i % 2 == 1:
1065            i += 1
1066            continue
1067        print i
1068        i += 1
1069 ///
1070 02468
1071 }}}
1072 
1073 <p>Note that the truth value expression in the <em>while</em> loop is evaluated using
1074 bool().</p>
1075 
1076 {{{id=86|
1077 bool(True)
1078 ///
1079 True
1080 }}}
1081 
1082 
1083 {{{id=87|
1084 bool('a')
1085 ///
1086 True
1087 }}}
1088 
1089 
1090 {{{id=88|
1091 bool(1)
1092 ///
1093 True
1094 }}}
1095 
1096 
1097 {{{id=89|
1098 bool(0)
1099 ///
1100 False
1101 }}}
1102 
1103 <!-- skip -->
1104 
1105 {{{id=90|
1106 i = 4
1107 while i:
1108        print i
1109        i -= 1
1110 ///
1111 4321
1112 }}}
1113 
1114 <h2>For Loops</h2>
1115 <p>Here is a basic for loop iterating over all of the elements in the list <tt class="docutils literal"><span class="pre">l</span></tt>:</p>
1116 
1117 {{{id=91|
1118 l = ['a', 'b', 'c']
1119 for letter in l:
1120        print letter
1121 ///
1122 abc
1123 }}}
1124 
1125 <p>The <em>range</em> function is very useful when you want to generate arithmetic
1126 progressions to loop over. Note that the end point is never included:</p>
1127 <!-- skip -->
1128 
1129 {{{id=92|
1130 range?
1131 ///
1132 }}}
1133 
1134 
1135 {{{id=93|
1136 range(4)
1137 ///
1138 [0, 1, 2, 3]
1139 }}}
1140 
1141 
1142 {{{id=94|
1143 range(1, 5)
1144 ///
1145 [1, 2, 3, 4]
1146 }}}
1147 
1148 
1149 {{{id=95|
1150 range(1, 11, 2)
1151 ///
1152 [1, 3, 5, 7, 9]
1153 }}}
1154 
1155 
1156 {{{id=96|
1157 range(10, 0, -1)
1158 ///
1159 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
1160 }}}
1161 
1162 
1163 {{{id=97|
1164 for i in range(4):
1165        print i, i*i
1166 ///
1167 0 01 12 43 9
1168 }}}
1169 
1170 <p>You can use the <em>continue</em> keyword to immediately go to the next item in the
1171 loop:</p>
1172 
1173 {{{id=98|
1174 for i in range(10):
1175        if i % 2 == 0:
1176            continue
1177        print i
1178 ///
1179 13579
1180 }}}
1181 
1182 <p>If you want to break out of the loop, use the <em>break</em> keyword:</p>
1183 
1184 {{{id=99|
1185 for i in range(10):
1186        if i % 2 == 0:
1187            continue
1188        if i == 7:
1189            break
1190        print i
1191 ///
1192 135
1193 }}}
1194 
1195 <p>If you need to keep track of both the position in the list and its value, one (not so elegant) way would be to do the following:</p>
1196 
1197 {{{id=100|
1198 l = ['a', 'b', 'c']
1199    for i in range(len(l)):
1200        print i, l[i]
1201 ///
1202 }}}
1203 
1204 <p>It's cleaner to use <em>enumerate</em> which provides the index as well as the value:</p>
1205 
1206 {{{id=101|
1207 l = ['a', 'b', 'c']
1208    for i, letter in enumerate(l):
1209        print i, letter
1210 ///
1211 }}}
1212 
1213 <p>You could make something similary to the <em>enumerate</em> function by using <em>zip</em>
1214 to zip two lists together:</p>
1215 
1216 {{{id=102|
1217 l = ['a', 'b', 'c']
1218    for i, letter in zip(range(len(l)), l):
1219        print i, letter
1220 ///
1221 }}}
1222 
1223 <p>For loops work using Python's iterator protocol.&nbsp; This allows all sorts of different objects to be looped over.&nbsp; For example,</p>
1224 
1225 {{{id=103|
1226 for i in GF(5):
1227        print i, i*i
1228 ///
1229 0 01 12 43 44 1
1230 }}}
1231 
1232 <p>How does it work?</p>
1233 
1234 {{{id=104|
1235 it = iter(GF(5)); it
1236 ///
1237 <generator object __iter__ at 0x...>
1238 }}}
1239 
1240 {{{id=105|
1241 it.next()
1242 ///
1243 0
1244 }}}
1245 
1246 {{{id=106|
1247 it.next()
1248 ///
1249 1
1250 }}}
1251 
1252 {{{id=107|
1253 it.next()
1254 ///
1255 2
1256 }}}
1257 
1258 {{{id=108|
1259 it.next()
1260 ///
1261 3
1262 }}}
1263 
1264 {{{id=109|
1265 it.next()
1266 ///
1267 4
1268 }}}
1269 
1270 {{{id=110|
1271 it.next()
1272 ///
1273 Traceback (most recent call last):
1274 StopIteration
1275 }}}
1276 
1277 <p>..skip</p>
1278 
1279 {{{id=111|
1280 R = GF(5)
1281    R.__iter__??
1282 ///
1283 }}}
1284 
1285 <p><em>yield</em> provides a very convient way to produce iterators.&nbsp; We'll see more
1286 about it in a bit.</p>
1287 
1288 <h3>Exercices</h3>
1289 <p>For each of the following sets, compute the list of its elements and their
1290 sum. Use two different ways, if possible: with a loop and using lists
1291 comprehension:</p>
1292 <blockquote>
1293 <ol class="arabic simple">
1294 <li><tt class="docutils literal"><span class="pre">n</span></tt> premiers termes de la série harmonique</li>
1295 </ol>
1296 
1297 <p class="system-message-title">System Message: WARNING/2 (<tt class="docutils">tutorial-programming-python.rst</tt>, line 1268)</p>
1298 Enumerated list ends without a blank line; unexpected unindent.
1299 <blockquote>
1300 
1301 <p class="system-message-title">System Message: ERROR/3 (<tt class="docutils">tutorial-programming-python.rst</tt>, line 1268)</p>
1302 <p>Unknown directive type &quot;math&quot;.</p>
1303 <pre class="literal-block">
1304 .. math:: \sum_{&nbsp;i=1}&nbsp;^n \frac{&nbsp;1}&nbsp;{&nbsp;i}&nbsp;
1305 
1306 
1307 </pre></blockquote>
1308 <ol class="arabic simple">
1309 <li>les entiers impair entre <tt class="docutils literal"><span class="pre">1</span></tt> et <tt class="docutils literal"><span class="pre">n</span></tt>;</li>
1310 <li>les <tt class="docutils literal"><span class="pre">n</span></tt> premiers entiers impairs;</li>
1311 <li>les entiers entre <tt class="docutils literal"><span class="pre">1</span></tt> et <tt class="docutils literal"><span class="pre">n</span></tt> et qui ne sont divisibles ni par <tt class="docutils literal"><span class="pre">2</span></tt>
1312 ni par <tt class="docutils literal"><span class="pre">3</span></tt> ni par <tt class="docutils literal"><span class="pre">5</span></tt>;</li>
1313 <li>les <tt class="docutils literal"><span class="pre">n</span></tt> premiers entiers qui ne sont
1314 divisibles ni par <tt class="docutils literal"><span class="pre">2</span></tt> ni par <tt class="docutils literal"><span class="pre">3</span></tt> ni par <tt class="docutils literal"><span class="pre">5</span></tt>.</li>
1315 </ol>
1316 </blockquote>
1317 
1318 
1319 
1320 <h2>Functions</h2>
1321 <p>Functions are defined using the <em>def</em> statement, and values are returned using
1322 the <em>return</em> keyword:</p>
1323 
1324 {{{id=112|
1325 def f(x):
1326        return x*x
1327 ///
1328 }}}
1329 
1330 <!-- link -->
1331 
1332 {{{id=113|
1333 f(2)
1334 ///
1335 4
1336 }}}
1337 
1338 <!-- link -->
1339 
1340 {{{id=114|
1341 def fib(n):
1342        if n &lt;= 1:
1343            return 1
1344        else:
1345            return fib(n-1) + fib(n-2)
1346 ///
1347 }}}
1348 
1349 <!-- link -->
1350 
1351 {{{id=115|
1352 [fib(i) for i in range(10)]
1353 ///
1354 [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
1355 }}}
1356 
1357 <p>Functions are first class objects like any other.&nbsp; For example, they can be
1358 passed in as arguments to other functions:</p>
1359 <pre class="literal-block">
1360 .. link
1361 
1362 </pre>
1363 {{{id=116|
1364 f
1365 ///
1366 <function f at 0x...>
1367 }}}
1368 
1369 <!-- link -->
1370 
1371 {{{id=117|
1372 def compose(f, x, n):
1373        for i in range(n):
1374            x = f(x)
1375        return x
1376 ///
1377 }}}
1378 
1379 <!-- link -->
1380 
1381 {{{id=118|
1382 compose(f, 2, 3)
1383 ///
1384 256
1385 }}}
1386 
1387 <!-- link -->
1388 
1389 {{{id=119|
1390 def add_one(x):
1391        return x + 1
1392 ///
1393 }}}
1394 
1395 <!-- link -->
1396 
1397 {{{id=120|
1398 compose(add_one, 2, 3)
1399 ///
1400 5
1401 }}}
1402 
1403 <p>You can give default values for arguments in functions:</p>
1404 
1405 {{{id=121|
1406 def add_n(x, n=1):
1407        return x + n
1408 ///
1409 }}}
1410 
1411 <!-- link -->
1412 
1413 {{{id=122|
1414 add_n(4)
1415 ///
1416 5
1417 }}}
1418 
1419 <!-- link -->
1420 
1421 {{{id=123|
1422 add_n(4, n=100)
1423 ///
1424 104
1425 }}}
1426 
1427 <!-- link -->
1428 
1429 {{{id=124|
1430 add_n(4, 1000)
1431 ///
1432 1004
1433 }}}
1434 
1435 <p>You can return multiple things from a function:</p>
1436 
1437 {{{id=125|
1438 def g(x):
1439        return x, x*x
1440 ///
1441 }}}
1442 
1443 <!-- link -->
1444 
1445 {{{id=126|
1446 g(2)
1447 ///
1448 (2, 4)
1449 }}}
1450 
1451 <!-- link -->
1452 
1453 {{{id=127|
1454 type(g)
1455 ///
1456 <type 'function'>
1457 }}}
1458 
1459 <!-- link -->
1460 
1461 {{{id=128|
1462 a,b = g(100)
1463 ///
1464 }}}
1465 
1466 <!-- link -->
1467 
1468 {{{id=129|
1469 a
1470 ///
1471 100
1472 }}}
1473 
1474 <!-- link -->
1475 
1476 {{{id=130|
1477 b
1478 ///
1479 10000
1480 }}}
1481 
1482 <p>You can also take variable number of arguments and keyword arguments in a
1483 function:</p>
1484 
1485 {{{id=131|
1486 def h(*args, **kwds):
1487        print type(args), args
1488        print type(kwds), kwds
1489 ///
1490 }}}
1491 
1492 <!-- link -->
1493 
1494 {{{id=132|
1495 h(1,2,3,n=4)
1496 ///
1497 <type 'tuple'> (1, 2, 3)<type 'dict'> {'n': 4}
1498 }}}
1499 
1500 <p>Let's use the <em>yield</em> instruction to make an generator for the Fibonacci
1501 numbers up to n:</p>
1502 
1503 {{{id=133|
1504 def fib_gen(n):
1505        if n &lt; 1:
1506            return
1507        a = b = 1
1508        yield b
1509        while b &lt; n:
1510            yield b
1511            a, b = b, b+a
1512 ///
1513 }}}
1514 
1515 <!-- link -->
1516 
1517 {{{id=134|
1518 for i in fib_gen(50):
1519        print i
1520 ///
1521 112358132134
1522 }}}
1523 
1524 <h3>Exercices</h3>
1525 <blockquote>
1526 <ol class="arabic simple">
1527 <li>Write a function <tt class="docutils literal"><span class="pre">is_even</span></tt> returning <tt class="docutils literal"><span class="pre">True</span></tt> if <tt class="docutils literal"><span class="pre">n</span></tt> is even
1528 and <tt class="docutils literal"><span class="pre">False</span></tt> otherwise.</li>
1529 <li>Write a function <tt class="docutils literal"><span class="pre">every_other</span></tt> which takes a list <tt class="docutils literal"><span class="pre">l</span></tt> and returns a
1530 list containing every other element of <tt class="docutils literal"><span class="pre">l</span></tt></li>
1531 <li>Write a function computing the n-th Fibonacci number. Try to improve
1532 performance.</li>
1533 </ol>
1534 </blockquote>