Tutorial: Programming in Python and Sage -- Thematic Tutorials v4.7.rc0
system:sage


<div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index" accesskey="I">index</a></li>
  
    
      <a href="../index.html"><img src="_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="index.html">Thematic Tutorials v4.7.rc0</a> &raquo;</li>
 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body">
            
  <div class="section" id="tutorial-programming-in-python-and-sage">
<span id="tutorial-programming-python"></span><h1>Tutorial: Programming in Python and Sage<a class="headerlink" href="#tutorial-programming-in-python-and-sage" title="Permalink to this headline">¶</a></h1>
<p><em>Author: Florent Hivert &lt;<a class="reference external" href="mailto:florent.hivert%40univ-rouen.fr">florent<span>&#46;</span>hivert<span>&#64;</span>univ-rouen<span>&#46;</span>fr</a>&gt; et al.</em></p>
<p>This tutorial is an introduction to basic programming in Python/Sage. The
reader is supposed to know the elementary notions of programming but is not
supposed to be familiar with the Python language. The memo given here are far
from being exhaustive. In case you need a more complete tutorial, you can have
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&#8217;s
<a class="reference external" href="http://docs.python.org/release/2.6.4/">documentation</a> and in particular the
<a class="reference external" href="http://docs.python.org/release/2.6.4/library">standard library</a> can be
useful.</p>
<p>A <a class="reference internal" href="tutorial-objects-and-classes.html#tutorial-objects-and-classes"><em>more advanced tutorial</em></a>
presents the notions of objects and classes in Python.</p>
<p>Here is a further list of resources for people wanting to learn Python:</p>
<ul class="simple">
<li><a class="reference external" href="http://www.korokithakis.net/tutorials/python">Learn Python in 10 minutes</a> ou en français
<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>
<li><a class="reference external" href="http://diveintopython.org/">Dive into Python</a>
is a Python book for experienced programmers. Also available in French,
<a class="reference external" href="http://diveintopython.adrahon.org/">Plongez au coeur de Python</a>, and
<a class="reference external" href="http://diveintopython.org/#languages">other languages</a>.</li>
<li><a class="reference external" href="http://www.ibm.com/developerworks/views/opensource/libraryview.jsp?search_by=Discover+Python+Part|">Discover Python</a>
is a series of articles published in IBM&#8217;s <a class="reference external" href="http://www.ibm.com/developerworks/">developerWorks</a> technical resource center.</li>
</ul>
<div class="section" id="data-structures">
<h2>Data structures<a class="headerlink" href="#data-structures" title="Permalink to this headline">¶</a></h2>
<p>In Python, <em>typing is dynamic</em>; there is no such thing as declaring
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
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
<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
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
of a class</em> and there is no difference between classes and types.</p>
<p>The symbol <tt class="docutils literal"><span class="pre">=</span></tt> denotes the affectation to a variable; it should not
be confused with <tt class="docutils literal"><span class="pre">==</span></tt> which denotes mathematical
equality. Inequality is <tt class="docutils literal"><span class="pre">!=</span></tt>.</p>
<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>,
<tt class="docutils literal"><span class="pre">dict</span></tt>, <tt class="docutils literal"><span class="pre">str</span></tt>.</p>
<ul>
<li><p class="first">The type <tt class="docutils literal"><span class="pre">bool</span></tt> (<em>Booleans</em>) takes two values: <tt class="xref docutils literal"><span class="pre">True</span></tt> and <tt class="xref docutils literal"><span class="pre">False</span></tt>. The
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>
</li>
<li><p class="first">Sage uses <em>exact arithmetic</em> on the integers. For performance reason, it
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>
and <tt class="docutils literal"><span class="pre">long</span></tt>).</p>
</li>
<li><p class="first">A <em>list</em> is a data structure which groups values. It is constructed using
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
lists. One can also create lists using <em>list comprehension</em>:</p>
<div class="highlight-python"><pre>[ &lt;expr&gt; for &lt;name&gt; in &lt;iterable&gt; (if &lt;condition&gt;) ]</pre>
</div>
<p>For example:</p>
<div class="highlight-python">

{{{id=0|
[ i^2 for i in range(10) if i % 2 == 0 ]
///
[0, 4, 16, 36, 64]
}}}

</div>
</li>
<li><p class="first">A <em>tuple</em> is very similar to a list; it is constructed using
parentheses. The empty tuple is obtained by <tt class="docutils literal"><span class="pre">()</span></tt> or by the
constructor <tt class="docutils literal"><span class="pre">tuple()</span></tt>. If there is only one element, one has to
write <tt class="docutils literal"><span class="pre">(a,)</span></tt>. A tuple is <em>immutable</em> (one cannot change it) but it
is <em>hashable</em> (see below). One can also create tuples using
comprehensions:</p>
<div class="highlight-python">

{{{id=1|
tuple(i^2 for i in range(10) if i % 2 == 0)
///
(0, 4, 16, 36, 64)
}}}

</div>
</li>
<li><p class="first">A <em>set</em> is a data structure which contains values without
multiplicities or order. One creates it from a list (or any
iterable) with the constructor <tt class="docutils literal"><span class="pre">set()</span></tt>. The elements of a set must
be hashable:</p>
<div class="highlight-python">

{{{id=2|
set([2,2,1,4,5])
///
set([1, 2, 4, 5])
}}}

</div>
</li>
<li><p class="first">A <em>dictionary</em> is an association table, which associate values to
keys. Keys must be hashable. One creates dictionaries using the
constructor <tt class="docutils literal"><span class="pre">dict</span></tt>, or using the syntax:</p>
<div class="highlight-python"><pre>{key1 : value1, key2 : value2 ...}</pre>
</div>
<p>For example:</p>
<div class="highlight-python">

{{{id=3|
age = {&#39;toto&#39; : 8, &#39;mom&#39; : 27}; age
///
{'toto': 8, 'mom': 27}
}}}

</div>
</li>
<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
strings</em>. One can concatenate them using <tt class="docutils literal"><span class="pre">+</span></tt>.</p>
</li>
<li><p class="first">For lists, tuples, strings, and dictionaries, the <em>indexing
operator</em> is written <tt class="docutils literal"><span class="pre">l[i]</span></tt>. For lists, tuples, and strings one
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
<tt class="docutils literal"><span class="pre">l[a:b]</span></tt>. Negative indices start from the end.</p>
</li>
<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
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
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>
</li>
<li><p class="first">Finally there is a special value called <tt class="xref docutils literal"><span class="pre">None</span></tt> to denote the
absence of a value.</p>
</li>
</ul>
</div>
<div class="section" id="control-structures">
<h2>Control structures<a class="headerlink" href="#control-structures" title="Permalink to this headline">¶</a></h2>
<p>In Python, there is no keyword for the beginning and the end of an
instructions block. Blocks are delimited thanks to indentation. Most
of the time a new block is introduced by <tt class="docutils literal"><span class="pre">:</span></tt>. Python has the
following control structures:</p>
<ul>
<li><p class="first">Conditional instruction:</p>
<div class="highlight-python"><pre>if &lt;condition&gt;:
    &lt;instruction sequence&gt;
[elif &lt;condition&gt;:
    &lt;instruction sequence&gt;]*
[else:
    &lt;instruction sequence&gt;]</pre>
</div>
</li>
<li><p class="first">Inside expression exclusively, one can write:</p>
<div class="highlight-python"><pre>&lt;value&gt; if &lt;condition&gt; else &lt;value&gt;</pre>
</div>
</li>
<li><p class="first">Iterative instructions:</p>
<div class="highlight-python"><pre>for &lt;name&gt; in &lt;iterable&gt;:
    &lt;instruction sequence&gt;
[else:
    &lt;instruction sequence&gt;]</pre>
</div>
<div class="highlight-python"><pre>while &lt;condition&gt;:
    &lt;instruction sequence&gt;
[else:
    &lt;instruction sequence&gt;]</pre>
</div>
<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
ended normally, that is neither by a <tt class="docutils literal"><span class="pre">break</span></tt> nor an exception.</p>
</li>
<li><p class="first">In a loop, <tt class="docutils literal"><span class="pre">continue</span></tt> jumps to the next iteration.</p>
</li>
<li><p class="first">An iterable is an object which can be iterated through. Iterable
types include lists, tuples, dictionaries, and strings.</p>
</li>
<li><p class="first">An error (also called exception) is raised by:</p>
<div class="highlight-python"><pre>raise &lt;ErrorType&gt; [, error message]</pre>
</div>
<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>
</li>
</ul>
</div>
<div class="section" id="functions">
<h2>Functions<a class="headerlink" href="#functions" title="Permalink to this headline">¶</a></h2>
<div class="admonition note">
<p class="first admonition-title">Note</p>
<p>Python functions vs. mathematical functions</p>
<p class="last">In what follows, we deal with <em>functions</em> is the sense of
<em>programming languages</em>. Mathematical functions are handled by
sage in a different way. In particular it doesn&#8217;t make sense to do
mathematical manipulation such as additions or derivations on
Python functions.</p>
</div>
<p>One defines a function using the keyword <tt class="docutils literal"><span class="pre">def</span></tt> as</p>
<div class="highlight-python"><pre>def &lt;name&gt;(&lt;argument list&gt;):
     &lt;instruction sequence&gt;</pre>
</div>
<p>The result of the function is given by the instruction
<tt class="docutils literal"><span class="pre">return</span></tt>. Very short functions can be created anonymously using
<tt class="docutils literal"><span class="pre">lambda</span></tt> (remark that there is no return here):</p>
<div class="highlight-python"><pre>lambda &lt;arguments&gt;: &lt;expression&gt;</pre>
</div>
<div class="admonition note">
<p class="first admonition-title">Note</p>
<p>(functional programming)</p>
<p class="last">Functions are objects as any other objects. One can assign them to
variables or return them.</p>
</div>
</div>
</div>
<div class="section" id="exercises">
<h1>Exercises<a class="headerlink" href="#exercises" title="Permalink to this headline">¶</a></h1>
<div class="section" id="lists">
<h2>Lists<a class="headerlink" href="#lists" title="Permalink to this headline">¶</a></h2>
<div class="section" id="creating-lists-i-square-brackets">
<h3>Creating Lists I: [Square brackets]<a class="headerlink" href="#creating-lists-i-square-brackets" title="Permalink to this headline">¶</a></h3>
<p><strong>Example:</strong></p>
<div class="highlight-python">

{{{id=4|
L = [3, Permutation([5,1,4,2,3]), 17, 17, 3, 51]
L
///
[3, [5, 1, 4, 2, 3], 17, 17, 3, 51]
}}}

</div>
<p><strong>Exercise:</strong> Create the list <img class="math" src="_images/math/c9f3c7f81c4ec7d3bb61fca52cb9b8f08f12684b.png" alt="[63, 12, -10, 'a', 12]">, assign it to
the variable <tt class="docutils literal"><span class="pre">L</span></tt>, and print the list.</p>
<div class="highlight-python">

{{{id=5|
# edit here
///
}}}

</div>
<p><strong>Exercise:</strong> Create the empty list (you will often need to do this).</p>
<div class="highlight-python">

{{{id=6|
# edit here
///
}}}

</div>
</div>
<div class="section" id="creating-lists-ii-range">
<h3>Creating Lists II: range<a class="headerlink" href="#creating-lists-ii-range" title="Permalink to this headline">¶</a></h3>
<p>The <em>range</em> function provides an easy way to construct a list of
integers. Here is the documentation of the <em>range</em> function:</p>
<div class="highlight-python"><pre>range([start,] stop[, step]) -&gt; list of integers

Return a list containing an arithmetic progression of integers.
range(i, j) returns [i, i+1, i+2, ..., j-1]; start (!) defaults to 0.
When step is given, it specifies the increment (or decrement). For
example, range(4) returns [0, 1, 2, 3].  The end point is omitted!
These are exactly the valid indices for a list of 4 elements.</pre>
</div>
<p><strong>Exercise:</strong> Use <em>range</em> to construct the list <img class="math" src="_images/math/e03125a1c7bc131925b2596bbe47e96d9860ecdb.png" alt="[1,2,\ldots,50]">.</p>
<div class="highlight-python">

{{{id=7|
# edit here
///
}}}

</div>
<p><strong>Exercise:</strong> Use <em>range</em> to construct the list of <em>even</em> numbers
between 1 and 100 (including 100).</p>
<div class="highlight-python">

{{{id=8|
# edit here
///
}}}

</div>
<p><strong>Exercise:</strong> The <em>step</em> argument for the <em>range</em> command can be negative. Use
<em>range</em> to construct the list <img class="math" src="_images/math/ab89d518382daa42f0affe3b98ad870f7e76be02.png" alt="[10, 7, 4, 1, -2]">.</p>
<div class="highlight-python">

{{{id=9|
# edit here
///
}}}

</div>
</div>
<div class="section" id="creating-lists-iii-list-comprehensions">
<h3>Creating Lists III: list comprehensions<a class="headerlink" href="#creating-lists-iii-list-comprehensions" title="Permalink to this headline">¶</a></h3>
<p><em>List comprehensions</em> provide a concise way to create lists from other lists
(or other data types).</p>
<p><strong>Example</strong> We already know how to create the list <img class="math" src="_images/math/6e447553c856a1add1524b3a8b328722eb2777de.png" alt="[1, 2, \dots, 16]">:</p>
<div class="highlight-python">

{{{id=10|
range(1,17)
///
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
}}}

</div>
<p>Using a <em>list comprehension</em>, we can now create the list
<img class="math" src="_images/math/9ff970b64aedca8b881e7c6a66e04c63f209e599.png" alt="[1^2, 2^2, 3^2, \dots, 16^2]"> as follows:</p>
<div class="highlight-python">

{{{id=11|
[i^2 for i in range(1,17)]
///
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256]
}}}

</div>
<div class="highlight-python">

{{{id=12|
sum([i^2 for i in range(1,17)])
///
1496
}}}

</div>
<p><strong>Exercice:</strong></p>
<p>The sum of the squares of the first ten natural numbers is</p>
<div class="math">
<p><img src="_images/math/9f2a20823e0150d34750d70f7f1ef2ca8211cd4e.png" alt="(1^2 + 2^2 + ... + 10^2) = 385"></p>
</div><p>The square of the sum of the first ten natural numbers is</p>
<div class="math">
<p><img src="_images/math/a2a4cd28d3138c8311337da9ba958049216bd951.png" alt="(1 + 2 + ... + 10)^2 = 55^2 = 3025"></p>
</div><p>Hence the difference between the sum of the squares of the first ten natural
numbers and the square of the sum is</p>
<div class="math">
<p><img src="_images/math/6e1e10127866de18a671e0fabc10297a4de1df7c.png" alt="3025 - 385 = 2640"></p>
</div><p>Find the difference between the sum of the squares of the first one hundred
natural numbers and the square of the sum.</p>
<div class="highlight-python">

{{{id=13|
# edit here
///
}}}

</div>
<div class="highlight-python">

{{{id=14|
# edit here
///
}}}

</div>
<div class="highlight-python">

{{{id=15|
# edit here
///
}}}

</div>
<div class="section" id="filtering-lists-with-a-list-comprehension">
<h4>Filtering lists with a list comprehension<a class="headerlink" href="#filtering-lists-with-a-list-comprehension" title="Permalink to this headline">¶</a></h4>
<p>A list can be <em>filtered</em> using a list comprehension.</p>
<p><strong>Example:</strong> To create a list of the squares of the prime numbers between 1
and 100, we use a list comprehension as follows.</p>
<div class="highlight-python">

{{{id=16|
[p^2 for p in [1,2,..,100] if is_prime(p)]
///
[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]
}}}

</div>
<p><strong>Exercise:</strong> Use a <em>list comprehension</em> to list all the natural numbers below
20 that are multiples of 3 or 5. Hint:</p>
<ul class="simple">
<li>To get the remainder of 7 divided by 3 use <em>7%3</em>.</li>
<li>To test for equality use two equal signs (<em>==</em>); for example, <em>3 == 7</em>.</li>
</ul>
<div class="highlight-python">

{{{id=17|
# edit here
///
}}}

</div>
</div>
<div class="section" id="nested-list-comprehensions">
<h4>Nested list comprehensions<a class="headerlink" href="#nested-list-comprehensions" title="Permalink to this headline">¶</a></h4>
<p>List comprehensions can be nested!</p>
<p><strong>Examples:</strong></p>
<div class="highlight-python">

{{{id=18|
[(x,y) for x in range(5) for y in range(3)]
///
[(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)]
}}}

</div>
<div class="highlight-python">

{{{id=19|
[[i^j for j in range(1,4)] for i in range(6)]
///
[[0, 0, 0], [1, 1, 1], [2, 4, 8], [3, 9, 27], [4, 16, 64], [5, 25, 125]]
}}}

</div>
<div class="highlight-python">

{{{id=20|
matrix([[i^j for j in range(1,4)] for i in range(6)])
///
[  0   0   0]
[  1   1   1]
[  2   4   8]
[  3   9  27]
[  4  16  64]
[  5  25 125]
}}}

</div>
<p><strong>Exercise:</strong></p>
<p>A <em>Pythagorean triple</em> is a triple <img class="math" src="_images/math/c73ed093cc73a8d9a14185fa525e7067e5c3725d.png" alt="(x,y,z)"> of <em>positive</em> integers satisfying
<img class="math" src="_images/math/67aa4144e50ffd4aa0b56d858fb0504f2e14ac59.png" alt="x^2+y^2=z^2">. The Pythagorean triples whose components are at most <img class="math" src="_images/math/fc606f7f1e530731ab4f1cc364c01dc64a4455ee.png" alt="10"> are:</p>
<div class="math">
<p><img src="_images/math/85101d2cf002d6235fc372643d4556a165d88bbf.png" alt="[(3, 4, 5), (4, 3, 5), (6, 8, 10), (8, 6, 10)]\,."></p>
</div><p>Using a filtered list comprehension, construct the list of Pythagorean triples
whose components are at most <img class="math" src="_images/math/906734e2f1010e9a171ffee8050cbc0649cea37c.png" alt="50">.</p>
<div class="highlight-python">

{{{id=21|
# edit here
///
}}}

</div>
<div class="highlight-python">

{{{id=22|
# edit here
///
}}}

</div>
</div>
</div>
<div class="section" id="accessing-individual-elements-of-lists">
<h3>Accessing individual elements of lists<a class="headerlink" href="#accessing-individual-elements-of-lists" title="Permalink to this headline">¶</a></h3>
<p>To access an element of the list, use the syntax <tt class="docutils literal"><span class="pre">L[i]</span></tt>, where <img class="math" src="_images/math/34857b3ba74ce5cd8607f3ebd23e9015908ada71.png" alt="i"> is the
index of the item.</p>
<p><strong>Exercise:</strong></p>
<blockquote>
<ol class="arabic">
<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>
<div class="highlight-python">

{{{id=23|
# edit here
///
}}}

</div>
</li>
<li><p class="first">What is <tt class="docutils literal"><span class="pre">L[1]</span></tt>?</p>
<div class="highlight-python">

{{{id=24|
# edit here
///
}}}

</div>
</li>
<li><p class="first">What is the index of the first element of <tt class="docutils literal"><span class="pre">L</span></tt>?</p>
<div class="highlight-python">

{{{id=25|
# edit here
///
}}}

</div>
</li>
<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>
<div class="highlight-python">

{{{id=26|
# edit here
///
}}}

</div>
</li>
<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>
<div class="highlight-python">

{{{id=27|
# edit here
///
}}}

</div>
</li>
</ol>
</blockquote>
</div>
<div class="section" id="modifying-lists-changing-an-element-in-a-list">
<h3>Modifying lists: changing an element in a list<a class="headerlink" href="#modifying-lists-changing-an-element-in-a-list" title="Permalink to this headline">¶</a></h3>
<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>
<div class="highlight-python">

{{{id=28|
L = [&quot;a&quot;, 4, 1, 8]
L
///
['a', 4, 1, 8]
}}}

</div>
<div class="highlight-python">

{{{id=29|
L[2] = 0
L
///
['a', 4, 0, 8]
}}}

</div>
</div>
<div class="section" id="modifying-lists-append-and-extend">
<h3>Modifying lists: append and extend<a class="headerlink" href="#modifying-lists-append-and-extend" title="Permalink to this headline">¶</a></h3>
<p>To <em>append</em> an object to a list:</p>
<div class="highlight-python">

{{{id=30|
L = [&quot;a&quot;, 4, 1, 8]
L
///
['a', 4, 1, 8]
}}}

</div>
<div class="highlight-python">

{{{id=31|
L.append(17)
L
///
['a', 4, 1, 8, 17]
}}}

</div>
<p>To <em>extend</em> a list by another list:</p>
<div class="highlight-python">

{{{id=32|
L1 = [1,2,3]
L2 = [7,8,9,0]
print L1
///
[1, 2, 3]
}}}

{{{id=33|
print L2
///
[7, 8, 9, 0]
}}}

</div>
<div class="highlight-python">

{{{id=34|
L1.extend(L2)
L1
///
[1, 2, 3, 7, 8, 9, 0]
}}}

</div>
</div>
<div class="section" id="modifying-lists-reverse-sort">
<h3>Modifying lists: reverse, sort, ...<a class="headerlink" href="#modifying-lists-reverse-sort" title="Permalink to this headline">¶</a></h3>
<div class="highlight-python">

{{{id=35|
L = [4,2,5,1,3]
L
///
[4, 2, 5, 1, 3]
}}}

</div>
<div class="highlight-python">

{{{id=36|
L.reverse()
L
///
[3, 1, 5, 2, 4]
}}}

</div>
<div class="highlight-python">

{{{id=37|
L.sort()
L
///
[1, 2, 3, 4, 5]
}}}

</div>
<div class="highlight-python">

{{{id=38|
L = [3,1,6,4]
sorted(L)
///
[1, 3, 4, 6]
}}}

</div>
<div class="highlight-python">

{{{id=39|
L
///
[3, 1, 6, 4]
}}}

</div>
</div>
<div class="section" id="concatenating-lists">
<h3>Concatenating Lists<a class="headerlink" href="#concatenating-lists" title="Permalink to this headline">¶</a></h3>
<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>
<div class="highlight-python">

{{{id=40|
L1 = [1,2,3]
L2 = [7,8,9,0]
L1 + L2
///
[1, 2, 3, 7, 8, 9, 0]
}}}

</div>
</div>
<div class="section" id="slicing-lists">
<h3>Slicing Lists<a class="headerlink" href="#slicing-lists" title="Permalink to this headline">¶</a></h3>
<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
return a sublist of <tt class="docutils literal"><span class="pre">L</span></tt>.</p>
<p><strong>Exercise:</strong> Below are some examples of slicing lists. Try to guess what the output will be before evaluating the cell.</p>
<div class="highlight-python">

{{{id=41|
L = range(20)
L
///
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
}}}

</div>
<div class="highlight-python">

{{{id=42|
L[3:15]
///
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
}}}

</div>
<div class="highlight-python">

{{{id=43|
L[3:15:2]
///
[3, 5, 7, 9, 11, 13]
}}}

</div>
<div class="highlight-python">

{{{id=44|
L[15:3:-1]
///
[15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4]
}}}

</div>
<div class="highlight-python">

{{{id=45|
L[:4]
///
[0, 1, 2, 3]
}}}

</div>
<div class="highlight-python">

{{{id=46|
L[:]
///
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
}}}

</div>
<div class="highlight-python">

{{{id=47|
L[::-1]
///
[19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
}}}

</div>
<p><strong>Advanced exercise:</strong> The following function combines a loop with the some of
the list operations above. What does the function do?</p>
<div class="highlight-python">

{{{id=48|
def f(number_of_iterations):
       L = [1]
       for n in range(2, number_of_iterations):
           L = [sum(L[:i]) for i in range(n-1, -1, -1)]
       return numerical_approx(2*L[0]*len(L)/sum(L), digits=50)
///
}}}

</div>
<div class="highlight-python">

{{{id=49|
f(10)
///
3.1413810483870967741935483870967741935483870967742
}}}

</div>
</div>
</div>
<div class="section" id="tuples">
<h2>Tuples<a class="headerlink" href="#tuples" title="Permalink to this headline">¶</a></h2>
<p>A <em>tuple</em> is an <em>immutable</em> list. That is, it cannot be changed once it is
created. To create a tuple, use parentheses instead of brackets:</p>
<div class="highlight-python">

{{{id=50|
t = (3, 5, [3,1], (17,[2,3],17), 4)
t
///
(3, 5, [3, 1], (17, [2, 3], 17), 4)
}}}

</div>
<p>We can create a tuple from a list, or vice-versa.</p>
<div class="highlight-python">

{{{id=51|
tuple(range(5))
///
(0, 1, 2, 3, 4)
}}}

</div>
<div class="highlight-python">

{{{id=52|
list(t)
///
[3, 5, [3, 1], (17, [2, 3], 17), 4]
}}}

</div>
<p>Tuples behave like lists in many respects:</p>
<table border="1" class="docutils">
<colgroup>
<col width="30%">
<col width="35%">
<col width="35%">
</colgroup>
<thead valign="bottom">
<tr><th class="head">Operation</th>
<th class="head">Syntax for lists</th>
<th class="head">Syntax for tuples</th>
</tr>
</thead>
<tbody valign="top">
<tr><td>Accessing a letter</td>
<td><tt class="docutils literal"><span class="pre">list[3]</span></tt></td>
<td><tt class="docutils literal"><span class="pre">tuple[3]</span></tt></td>
</tr>
<tr><td>Concatenation</td>
<td><tt class="docutils literal"><span class="pre">list1</span> <span class="pre">+</span> <span class="pre">list2</span></tt></td>
<td><tt class="docutils literal"><span class="pre">tuple1</span> <span class="pre">+</span> <span class="pre">tuple2</span></tt></td>
</tr>
<tr><td>Slicing</td>
<td><tt class="docutils literal"><span class="pre">list[3:17:2]</span></tt></td>
<td><tt class="docutils literal"><span class="pre">tuple[3:17:2]</span></tt></td>
</tr>
<tr><td>A reversed copy</td>
<td><tt class="docutils literal"><span class="pre">list[::-1]</span></tt></td>
<td><tt class="docutils literal"><span class="pre">tuple[::-1]</span></tt></td>
</tr>
<tr><td>Length</td>
<td><tt class="docutils literal"><span class="pre">len(list)</span></tt></td>
<td><tt class="docutils literal"><span class="pre">len(tuple)</span></tt></td>
</tr>
</tbody>
</table>
<p>Trying to modify a tuple will fail.</p>
<div class="highlight-python">

{{{id=53|
t = (5, &#39;a&#39;, 6/5)
t
///
(5, 'a', 6/5)
}}}

</div>
<div class="highlight-python">

{{{id=54|
t[1] = &#39;b&#39;
///
Traceback (most recent call last):

TypeError: 'tuple' object does not support item assignment
}}}

</div>
</div>
<div class="section" id="generators">
<h2>Generators<a class="headerlink" href="#generators" title="Permalink to this headline">¶</a></h2>
<p>&#8220;Tuple-comprehension&#8221; does not exist. The syntax produces something called a
generator.  A generator allows you to process a sequence of items one at a
time. Each item is created when it is needed, and then forgotten. This can
be very efficient if we only need to use each item once.</p>
<div class="highlight-python">

{{{id=55|
(i^2 for i in range(5))
///
<generator object <genexpr> at 0x...>
}}}

</div>
<div class="highlight-python">

{{{id=56|
g = (i^2 for i in range(5))
g[0]
///
Traceback (most recent call last):

TypeError: 'generator' object is unsubscriptable
}}}

</div>
<div class="highlight-python">

{{{id=57|
[x for x in g]
///
[0, 1, 4, 9, 16]
}}}

</div>
<p><tt class="docutils literal"><span class="pre">g</span></tt> is now empty.</p>
<div class="highlight-python">

{{{id=58|
[x for x in g]
///
[]
}}}

</div>
<p>A nice &#8216;pythonic&#8217; trick is to use generators as argument of functions. We
do <em>not</em> need double parentheses for this.</p>
<div class="highlight-python">

{{{id=59|
sum( i^2 for i in srange(100001) )
///
333338333350000
}}}

</div>
</div>
<div class="section" id="dictionaries">
<h2>Dictionaries<a class="headerlink" href="#dictionaries" title="Permalink to this headline">¶</a></h2>
<p>A <em>dictionary</em> is another built-in data type. Unlike lists, which are indexed
by a range of numbers, dictionaries are indexed 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 &#8220;associative arrays&#8221; in other
programming languages.</p>
<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>
<div class="highlight-python">

{{{id=60|
d = {3:17, &quot;key&quot;:[4,1,5,2,3], (3,1,2):&quot;goo&quot;, 3/2 : 17}
d
///
{3/2: 17, 3: 17, (3, 1, 2): 'goo', 'key': [4, 1, 5, 2, 3]}
}}}

</div>
<p>A second solution for creating a dictionary is to use the function dict which
admits a list of 2-tuples <em>(key, value)</em> (actually any iterable):</p>
<div class="highlight-python">

{{{id=61|
dd = dict((i,i^2) for i in xrange(10))
dd
///
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}
}}}

</div>
<p>Dictionaries behave as lists and tuples for several important operations.</p>
<table border="1" class="docutils">
<colgroup>
<col width="28%">
<col width="32%">
<col width="40%">
</colgroup>
<thead valign="bottom">
<tr><th class="head">Operation</th>
<th class="head">Syntax for lists</th>
<th class="head">Syntax for dictionaries</th>
</tr>
</thead>
<tbody valign="top">
<tr><td>Accessing elements</td>
<td><tt class="docutils literal"><span class="pre">list[3]</span></tt></td>
<td><tt class="docutils literal"><span class="pre">D[&quot;key&quot;]</span></tt></td>
</tr>
<tr><td>Length</td>
<td><tt class="docutils literal"><span class="pre">len(list)</span></tt></td>
<td><tt class="docutils literal"><span class="pre">len(D)</span></tt></td>
</tr>
<tr><td>Modifying</td>
<td><tt class="docutils literal"><span class="pre">L[3]</span> <span class="pre">=</span> <span class="pre">17</span></tt></td>
<td><tt class="docutils literal"><span class="pre">D[&quot;key&quot;]</span> <span class="pre">=</span> <span class="pre">17</span></tt></td>
</tr>
<tr><td>Deleting items</td>
<td><tt class="docutils literal"><span class="pre">del</span> <span class="pre">L[3]</span></tt></td>
<td><tt class="docutils literal"><span class="pre">del</span> <span class="pre">D[&quot;key&quot;]</span></tt></td>
</tr>
</tbody>
</table>
<div class="highlight-python">

{{{id=62|
d[10]=&#39;a&#39;
d
///
{3/2: 17, 10: 'a', 3: 17, (3, 1, 2): 'goo', 'key': [4, 1, 5, 2, 3]}
}}}

</div>
<p>A dictionary can have the same value multiple times, but each key must only
appear once and must be immutable.</p>
<div class="highlight-python">

{{{id=63|
d = {3: 14, 4: 14}
d
///
{3: 14, 4: 14}
}}}

</div>
<div class="highlight-python">

{{{id=64|
d = {3: 13, 3: 14}
d
///
{3: 14}
}}}

</div>
<div class="highlight-python">

{{{id=65|
d = {[1,2,3] : 12}
///
Traceback (most recent call last):

TypeError: unhashable type: 'list'
}}}

</div>
<p>Another way to add items to a dictionary is with the <tt class="docutils literal"><span class="pre">update()</span></tt> method which
updates the dictionnary from another dictionnary:</p>
<div class="highlight-python">

{{{id=66|
d = {}
d
///
{}
}}}

</div>
<div class="highlight-python">

{{{id=67|
d.update( {10 : &#39;newvalue&#39;, 20: &#39;newervalue&#39;, 3: 14, &#39;a&#39;:[1,2,3]} )
d
///
{'a': [1, 2, 3], 10: 'newvalue', 3: 14, 20: 'newervalue'}
}}}

</div>
<p>We can iterate through the <em>keys</em>, or <em>values</em>, or both, of a dictionary.</p>
<div class="highlight-python">

{{{id=68|
d = {10 : &#39;newvalue&#39;, 20: &#39;newervalue&#39;, 3: 14, &#39;a&#39;:[1,2,3]}
///
}}}

</div>
<div class="highlight-python">

{{{id=69|
[key for key in d]
///
['a', 10, 3, 20]
}}}

</div>
<div class="highlight-python">

{{{id=70|
[key for key in d.iterkeys()]
///
['a', 10, 3, 20]
}}}

</div>
<div class="highlight-python">

{{{id=71|
[value for value in d.itervalues()]
///
[[1, 2, 3], 'newvalue', 14, 'newervalue']
}}}

</div>
<div class="highlight-python">

{{{id=72|
[(key, value) for key, value in d.iteritems()]
///
[('a', [1, 2, 3]), (10, 'newvalue'), (3, 14), (20, 'newervalue')]
}}}

</div>
<p><strong>Exercise:</strong> Consider the following directed graph.</p>
<img alt="_images/graph0.png" src="_images/graph0.png">
<p>Create a dictionary whose keys are the vertices of the above directed graph,
and whose values are the lists of the vertices that it points to. For
instance, the vertex 1 points to the vertices 2 and 3, so the dictionary will
look like:</p>
<div class="highlight-python"><pre>d = { ..., 1:[2,3], ... }</pre>
</div>
<div class="highlight-python">

{{{id=73|
# edit here
///
}}}

</div>
<p>Then try</p>
<div class="highlight-python">

{{{id=74|
g = DiGraph(d)
g.plot()
///
}}}

</div>
</div>
<div class="section" id="using-sage-types-the-srange-command">
<h2>Using Sage types: The srange command<a class="headerlink" href="#using-sage-types-the-srange-command" title="Permalink to this headline">¶</a></h2>
<p><strong>Example:</strong> Construct a <img class="math" src="_images/math/d278803d72fcc493afb1559174a483aa7f41d143.png" alt="3 \times 3"> matrix whose <img class="math" src="_images/math/887919dfbc86eebc29e0373f98f97dbf23a0ae23.png" alt="(i,j)"> entry is the
rational number <img class="math" src="_images/math/e19c3c39ceaedd97bfd3e94af905749535535bcb.png" alt="\frac{i}{j}">. The integer generated by <tt class="docutils literal"><span class="pre">range</span></tt> are
python <tt class="docutils literal"><span class="pre">int</span></tt>. As a consequence, dividing them does euclidian division.</p>
<div class="highlight-python">

{{{id=75|
matrix([[ i/j for j in range(1,4)] for i in range(1,4)])
///
[1 0 0]
[2 1 0]
[3 1 1]
}}}

</div>
<p>Whereas Dividing sage <tt class="docutils literal"><span class="pre">Integer</span></tt> gives a fraction</p>
<div class="highlight-python">

{{{id=76|
matrix([[ i/j for j in srange(1,4)] for i in srange(1,4)])
///
[  1 1/2 1/3]
[  2   1 2/3]
[  3 3/2   1]
}}}

</div>
</div>
<div class="section" id="modifying-lists-has-consequences">
<h2>Modifying lists has consequences!<a class="headerlink" href="#modifying-lists-has-consequences" title="Permalink to this headline">¶</a></h2>
<p>Try to predict the results of the following commands.</p>
<div class="highlight-python">

{{{id=77|
a = [1, 2, 3]
L = [a, a, a]
L
///
[[1, 2, 3], [1, 2, 3], [1, 2, 3]]
}}}

</div>
<div class="highlight-python">

{{{id=78|
a.append(4)
L
///
[[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]
}}}

</div>
<p>Now try these:</p>
<div class="highlight-python">

{{{id=79|
a = [1, 2, 3]
L = [a, a, a]
L
///
[[1, 2, 3], [1, 2, 3], [1, 2, 3]]
}}}

</div>
<div class="highlight-python">

{{{id=80|
a = [1, 2, 3, 4]
L
///
[[1, 2, 3], [1, 2, 3], [1, 2, 3]]
}}}

</div>
<div class="highlight-python">

{{{id=81|
L[0].append(4)
L
///
[[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]
}}}

</div>
<p>You can use the command <em>deepcopy</em> to avoid these issues.</p>
<div class="highlight-python">

{{{id=82|
a = [1,2,3]
L = [deepcopy(a), deepcopy(a)]
L
///
[[1, 2, 3], [1, 2, 3]]
}}}

</div>
<div class="highlight-python">

{{{id=83|
a.append(4)
L
///
[[1, 2, 3], [1, 2, 3]]
}}}

</div>
<p>The same issues occur with dictionaries.</p>
<div class="highlight-python">

{{{id=84|
d = {1:&#39;a&#39;, 2:&#39;b&#39;, 3:&#39;c&#39;}
dd = d
d.update( { 4:&#39;d&#39; } )
dd
///
{1: 'a', 2: 'b', 3: 'c', 4: 'd'}
}}}

</div>
</div>
</div>
<div class="section" id="loops-and-functions">
<h1>Loops and Functions<a class="headerlink" href="#loops-and-functions" title="Permalink to this headline">¶</a></h1>
<p>For more verbose explanation of what&#8217;s going on here, a good place to look is
at the following section of the Python tutorial:
<a class="reference external" href="http://docs.python.org/tutorial/controlflow.html">http://docs.python.org/tutorial/controlflow.html</a></p>
<div class="section" id="while-loops">
<h2>While Loops<a class="headerlink" href="#while-loops" title="Permalink to this headline">¶</a></h2>
<p>While loops tend not to be used nearly as much as for loops in Python code.</p>
<div class="highlight-python">

{{{id=85|
i = 0
while i &lt; 10:
       print i
       i += 1
///
0
1
2
3
4
5
6
7
8
9
}}}

</div>
<div class="highlight-python">

{{{id=86|
i = 0
while i &lt; 10:
       if i % 2 == 1:
           i += 1
           continue
       print i
       i += 1
///
0
2
4
6
8
}}}

</div>
<p>Note that the truth value expression in the <em>while</em> loop is evaluated using
bool().</p>
<div class="highlight-python">

{{{id=87|
bool(True)
///
True
}}}

</div>
<div class="highlight-python">

{{{id=88|
bool(&#39;a&#39;)
///
True
}}}

</div>
<div class="highlight-python">

{{{id=89|
bool(1)
///
True
}}}

</div>
<div class="highlight-python">

{{{id=90|
bool(0)
///
False
}}}

</div>
<div class="highlight-python">

{{{id=91|
i = 4
while i:
       print i
       i -= 1
///
4
3
2
1
}}}

</div>
</div>
<div class="section" id="for-loops">
<h2>For Loops<a class="headerlink" href="#for-loops" title="Permalink to this headline">¶</a></h2>
<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>
<div class="highlight-python">

{{{id=92|
l = [&#39;a&#39;, &#39;b&#39;, &#39;c&#39;]
for letter in l:
       print letter
///
a
b
c
}}}

</div>
<p>The <em>range</em> function is very useful when you want to generate arithmetic
progressions to loop over. Note that the end point is never included:</p>
<div class="highlight-python"><pre>sage: range?</pre>
</div>
<div class="highlight-python">

{{{id=93|
range(4)
///
[0, 1, 2, 3]
}}}

</div>
<div class="highlight-python">

{{{id=94|
range(1, 5)
///
[1, 2, 3, 4]
}}}

</div>
<div class="highlight-python">

{{{id=95|
range(1, 11, 2)
///
[1, 3, 5, 7, 9]
}}}

</div>
<div class="highlight-python">

{{{id=96|
range(10, 0, -1)
///
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
}}}

</div>
<div class="highlight-python">

{{{id=97|
for i in range(4):
       print i, i*i
///
0 0
1 1
2 4
3 9
}}}

</div>
<p>You can use the <em>continue</em> keyword to immediately go to the next item in the
loop:</p>
<div class="highlight-python">

{{{id=98|
for i in range(10):
       if i % 2 == 0:
           continue
       print i
///
1
3
5
7
9
}}}

</div>
<p>If you want to break out of the loop, use the <em>break</em> keyword:</p>
<div class="highlight-python">

{{{id=99|
for i in range(10):
       if i % 2 == 0:
           continue
       if i == 7:
           break
       print i
///
1
3
5
}}}

</div>
<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>
<div class="highlight-python">

{{{id=100|
l = [&#39;a&#39;, &#39;b&#39;, &#39;c&#39;]
   for i in range(len(l)):
       print i, l[i]
///
}}}

</div>
<p>It&#8217;s cleaner to use <em>enumerate</em> which provides the index as well as the value:</p>
<div class="highlight-python">

{{{id=101|
l = [&#39;a&#39;, &#39;b&#39;, &#39;c&#39;]
   for i, letter in enumerate(l):
       print i, letter
///
}}}

</div>
<p>You could make something similary to the <em>enumerate</em> function by using <em>zip</em>
to zip two lists together:</p>
<div class="highlight-python">

{{{id=102|
l = [&#39;a&#39;, &#39;b&#39;, &#39;c&#39;]
   for i, letter in zip(range(len(l)), l):
       print i, letter
///
}}}

</div>
<p>For loops work using Python&#8217;s iterator protocol.&nbsp; This allows all sorts of different objects to be looped over.&nbsp; For example,</p>
<div class="highlight-python">

{{{id=103|
for i in GF(5):
       print i, i*i
///
0 0
1 1
2 4
3 4
4 1
}}}

</div>
<p>How does it work?</p>
<div class="highlight-python">

{{{id=104|
it = iter(GF(5)); it
///
<generator object __iter__ at 0x...>
}}}

{{{id=105|
it.next()
///
0
}}}

{{{id=106|
it.next()
///
1
}}}

{{{id=107|
it.next()
///
2
}}}

{{{id=108|
it.next()
///
3
}}}

{{{id=109|
it.next()
///
4
}}}

{{{id=110|
it.next()
///
Traceback (most recent call last):

StopIteration
}}}

</div>
<p>..skip</p>
<div class="highlight-python"><pre>sage: R = GF(5)
...   R.__iter__??</pre>
</div>
<p><em>yield</em> provides a very convient way to produce iterators.&nbsp; We&#8217;ll see more
about it in a bit.</p>
<div class="section" id="id1">
<h3>Exercises<a class="headerlink" href="#id1" title="Permalink to this headline">¶</a></h3>
<p>TODO: Finish the translation!</p>
<p>For each of the following sets, compute the list of its elements and their
sum. Use two different ways, if possible: with a loop and using lists
comprehension:</p>
<blockquote>
<ol class="arabic simple">
<li><tt class="docutils literal"><span class="pre">n</span></tt> premiers termes de la série harmonique</li>
</ol>
<blockquote>
<div class="math">
<p><img src="_images/math/dfcb054b5e28eb474bf7569d9a07c7c60172142c.png" alt="\sum_{i=1}^n \frac{1}{i}"></p>
</div></blockquote>
<ol class="arabic simple">
<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>
<li>les <tt class="docutils literal"><span class="pre">n</span></tt> premiers entiers impairs;</li>
<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>
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>
<li>les <tt class="docutils literal"><span class="pre">n</span></tt> premiers entiers qui ne sont
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>
</ol>
</blockquote>
</div>
</div>
<div class="section" id="id2">
<h2>Functions<a class="headerlink" href="#id2" title="Permalink to this headline">¶</a></h2>
<p>Functions are defined using the <em>def</em> statement, and values are returned using
the <em>return</em> keyword:</p>
<div class="highlight-python">

{{{id=111|
def f(x):
       return x*x
///
}}}

</div>
<div class="highlight-python">

{{{id=112|
f(2)
///
4
}}}

</div>
<div class="highlight-python">

{{{id=113|
def fib(n):
       if n &lt;= 1:
           return 1
       else:
           return fib(n-1) + fib(n-2)
///
}}}

</div>
<div class="highlight-python">

{{{id=114|
[fib(i) for i in range(10)]
///
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
}}}

</div>
<p>Functions are first class objects like any other.&nbsp; For example, they can be
passed in as arguments to other functions:</p>
<div class="highlight-python"><pre>.. link</pre>
</div>
<div class="highlight-python">

{{{id=115|
f
///
<function f at 0x...>
}}}

</div>
<div class="highlight-python">

{{{id=116|
def compose(f, x, n):
       for i in range(n):
           x = f(x)
       return x
///
}}}

</div>
<div class="highlight-python">

{{{id=117|
compose(f, 2, 3)
///
256
}}}

</div>
<div class="highlight-python">

{{{id=118|
def add_one(x):
       return x + 1
///
}}}

</div>
<div class="highlight-python">

{{{id=119|
compose(add_one, 2, 3)
///
5
}}}

</div>
<p>You can give default values for arguments in functions:</p>
<div class="highlight-python">

{{{id=120|
def add_n(x, n=1):
       return x + n
///
}}}

</div>
<div class="highlight-python">

{{{id=121|
add_n(4)
///
5
}}}

</div>
<div class="highlight-python">

{{{id=122|
add_n(4, n=100)
///
104
}}}

</div>
<div class="highlight-python">

{{{id=123|
add_n(4, 1000)
///
1004
}}}

</div>
<p>You can return multiple things from a function:</p>
<div class="highlight-python">

{{{id=124|
def g(x):
       return x, x*x
///
}}}

</div>
<div class="highlight-python">

{{{id=125|
g(2)
///
(2, 4)
}}}

</div>
<div class="highlight-python">

{{{id=126|
type(g)
///
<type 'function'>
}}}

</div>
<div class="highlight-python">

{{{id=127|
a,b = g(100)
///
}}}

</div>
<div class="highlight-python">

{{{id=128|
a
///
100
}}}

</div>
<div class="highlight-python">

{{{id=129|
b
///
10000
}}}

</div>
<p>You can also take variable number of arguments and keyword arguments in a
function:</p>
<div class="highlight-python">

{{{id=130|
def h(*args, **kwds):
       print type(args), args
       print type(kwds), kwds
///
}}}

</div>
<div class="highlight-python">

{{{id=131|
h(1,2,3,n=4)
///
<type 'tuple'> (1, 2, 3)
<type 'dict'> {'n': 4}
}}}

</div>
<p>Let&#8217;s use the <em>yield</em> instruction to make an generator for the Fibonacci
numbers up to n:</p>
<div class="highlight-python">

{{{id=132|
def fib_gen(n):
       if n &lt; 1:
           return
       a = b = 1
       yield b
       while b &lt; n:
           yield b
           a, b = b, b+a
///
}}}

</div>
<div class="highlight-python">

{{{id=133|
for i in fib_gen(50):
       print i
///
1
1
2
3
5
8
13
21
34
}}}

</div>
<div class="section" id="exercices">
<h3>Exercices<a class="headerlink" href="#exercices" title="Permalink to this headline">¶</a></h3>
<blockquote>
<ol class="arabic simple">
<li>Write a function <tt class="docutils literal"><span class="pre">is_even</span></tt> returning <tt class="xref docutils literal"><span class="pre">True</span></tt> if <tt class="docutils literal"><span class="pre">n</span></tt> is even
and <tt class="xref docutils literal"><span class="pre">False</span></tt> otherwise.</li>
<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
list containing every other element of <tt class="docutils literal"><span class="pre">l</span></tt></li>
<li>Write a function computing the n-th Fibonacci number. Try to improve
performance.</li>
</ol>
</blockquote>
</div>
</div>
</div>


          </div>
        </div>
      </div>
      <div class="sphinxsidebar">
        <div class="sphinxsidebarwrapper">
            <h3><a href="index.html">Table Of Contents</a></h3>
            <ul>
<li><a class="reference internal" href="#">Tutorial: Programming in Python and Sage</a><ul>
<li><a class="reference internal" href="#data-structures">Data structures</a></li>
<li><a class="reference internal" href="#control-structures">Control structures</a></li>
<li><a class="reference internal" href="#functions">Functions</a></li>
</ul>
</li>
<li><a class="reference internal" href="#exercises">Exercises</a><ul>
<li><a class="reference internal" href="#lists">Lists</a><ul>
<li><a class="reference internal" href="#creating-lists-i-square-brackets">Creating Lists I: [Square brackets]</a></li>
<li><a class="reference internal" href="#creating-lists-ii-range">Creating Lists II: range</a></li>
<li><a class="reference internal" href="#creating-lists-iii-list-comprehensions">Creating Lists III: list comprehensions</a><ul>
<li><a class="reference internal" href="#filtering-lists-with-a-list-comprehension">Filtering lists with a list comprehension</a></li>
<li><a class="reference internal" href="#nested-list-comprehensions">Nested list comprehensions</a></li>
</ul>
</li>
<li><a class="reference internal" href="#accessing-individual-elements-of-lists">Accessing individual elements of lists</a></li>
<li><a class="reference internal" href="#modifying-lists-changing-an-element-in-a-list">Modifying lists: changing an element in a list</a></li>
<li><a class="reference internal" href="#modifying-lists-append-and-extend">Modifying lists: append and extend</a></li>
<li><a class="reference internal" href="#modifying-lists-reverse-sort">Modifying lists: reverse, sort, ...</a></li>
<li><a class="reference internal" href="#concatenating-lists">Concatenating Lists</a></li>
<li><a class="reference internal" href="#slicing-lists">Slicing Lists</a></li>
</ul>
</li>
<li><a class="reference internal" href="#tuples">Tuples</a></li>
<li><a class="reference internal" href="#generators">Generators</a></li>
<li><a class="reference internal" href="#dictionaries">Dictionaries</a></li>
<li><a class="reference internal" href="#using-sage-types-the-srange-command">Using Sage types: The srange command</a></li>
<li><a class="reference internal" href="#modifying-lists-has-consequences">Modifying lists has consequences!</a></li>
</ul>
</li>
<li><a class="reference internal" href="#loops-and-functions">Loops and Functions</a><ul>
<li><a class="reference internal" href="#while-loops">While Loops</a></li>
<li><a class="reference internal" href="#for-loops">For Loops</a><ul>
<li><a class="reference internal" href="#id1">Exercises</a></li>
</ul>
</li>
<li><a class="reference internal" href="#id2">Functions</a><ul>
<li><a class="reference internal" href="#exercices">Exercices</a></li>
</ul>
</li>
</ul>
</li>
</ul>

            <h3>This Page</h3>
            <ul class="this-page-menu">
              <li><a href="_sources/tutorial-programming-python.txt" rel="nofollow">Show Source</a></li>
            </ul>
          <div id="searchbox" style="display: none">
            <h3>Quick search</h3>
              <p class="searchtip" style="font-size: 90%">
              Enter search terms or a module, class or function name.
              </p>
          </div>
          <script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index">index</a></li>
  
    
      <a href="../index.html"><img src="_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="index.html">Thematic Tutorials v4.7.rc0</a> &raquo;</li>
 
      </ul>
    </div>
    
    <div class="footer">
        &copy; Copyright 2005--2011, The Sage Development Team.
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.0.4.
    </div>
    <script type="text/javascript">
/*global jQuery, window */
/* Sphinx sidebar toggle.  Putting this code at the end of the body
 * enables the toggle for the live, static, and offline docs.  Note:
 * sage.misc.html.math_parse() eats jQuery's dollar-sign shortcut. */
var jq = jQuery;  
jq(document).ready(function () {
    var bar, bod, bg, fg, key, tog, wid_old, wid_new, resize, get_state, set_state;
    bod = jq('div.bodywrapper');
    bar = jq('div.sphinxsidebar');
    tog = jq('<div class="sphinxsidebartoggle"></div>');
    
    /* Delayed resize helper.  Not perfect but good enough. */
    resize = function () {
        setTimeout(function () {
            tog.height(bod.height());
        }, 100);
    };
    jq(window).resize(function () {
        resize();
    });
    
    /* Setup and add the toggle. See Sphinx v0.5.1 default.css. */
    fg = jq('div.sphinxsidebar p a').css('color') || 'rgb(152, 219, 204)';
    bg = jq('div.document').css('background-color') || 'rgb(28, 78, 99)';
    wid_old = '230px';
    wid_new = '5px';
    tog.css('background-color', bg)
        .css('border-width', '0px')
        .css('border-right', wid_new + ' ridge ' + bg)
        .css('cursor', 'pointer')
        .css('position', 'absolute')
        .css('left', '-' + wid_new)
        .css('top', '0px')
        .css('width', wid_new);
    bod.css('position', 'relative');
    bod.prepend(tog);
    resize();
    
    /* Cookie helpers. */
    key = 'sphinxsidebar=';
    set_state = function (s) {
        var date = new Date();
        /* Expiry in 7 days. */
        date.setTime(date.getTime() + (7 * 24 * 3600 * 1000));
        document.cookie = key + encodeURIComponent(s) + '; expires=' +
            date.toUTCString() + '; path=/';
    };
    get_state = function () {
        var i, c, crumbs = document.cookie.split(';');
        for (i = 0; i < crumbs.length; i += 1) {
            c = crumbs[i].replace(/^\s+/, '');
            if (c.indexOf(key) === 0) {
                return decodeURIComponent(c.substring(key.length, c.length));
            }
        }
        return null;
    };
    
    /* Event handlers. */
    tog.mouseover(function (ev) {
        tog.css('border-right-color', fg);
    }).mouseout(function (ev) {
        tog.css('border-right-color', bg);
    }).click(function (ev) {
        if (bod.hasClass('wide')) {
            bod.removeClass('wide');
            bod.css('margin-left', wid_old);
            bar.css('width', wid_old);
            bar.show();
            set_state('visible');
        } else {
            set_state('hidden');
            bar.hide();
            bar.css('width', '0px');
            bod.css('margin-left', wid_new);
            bod.addClass('wide');
        }
        resize();
    });
    
    /* Hide the normally visible sidebar? */
    if (get_state() === 'hidden') {
        tog.trigger('click');
    } else {
        set_state('visible');
    }
});
    </script>