Sophie

Sophie

distrib > Fedora > 17 > i386 > media > updates > by-pkgid > 675c8c8167236dfcf8d66da674f931e8 > files > 105

erlang-doc-R15B-03.3.fc17.noarch.rpm

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html xmlns:fn="http://www.w3.org/2005/02/xpath-functions">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<link rel="stylesheet" href="../otp_doc.css" type="text/css">
<title>Erlang -- List Comprehensions</title>
</head>
<body bgcolor="white" text="#000000" link="#0000ff" vlink="#ff00ff" alink="#ff0000"><div id="container">
<script id="js" type="text/javascript" language="JavaScript" src="../js/flipmenu/flipmenu.js"></script><script id="js2" type="text/javascript" src="../js/erlresolvelinks.js"></script><script language="JavaScript" type="text/javascript">
            <!--
              function getWinHeight() {
                var myHeight = 0;
                if( typeof( window.innerHeight ) == 'number' ) {
                  //Non-IE
                  myHeight = window.innerHeight;
                } else if( document.documentElement && ( document.documentElement.clientWidth ||
                                                         document.documentElement.clientHeight ) ) {
                  //IE 6+ in 'standards compliant mode'
                  myHeight = document.documentElement.clientHeight;
                } else if( document.body && ( document.body.clientWidth || document.body.clientHeight ) ) {
                  //IE 4 compatible
                  myHeight = document.body.clientHeight;
                }
                return myHeight;
              }

              function setscrollpos() {
                var objf=document.getElementById('loadscrollpos');
                 document.getElementById("leftnav").scrollTop = objf.offsetTop - getWinHeight()/2;
              }

              function addEvent(obj, evType, fn){
                if (obj.addEventListener){
                obj.addEventListener(evType, fn, true);
                return true;
              } else if (obj.attachEvent){
                var r = obj.attachEvent("on"+evType, fn);
                return r;
              } else {
                return false;
              }
             }

             addEvent(window, 'load', setscrollpos);

             //--></script><div id="leftnav"><div class="innertube">
<img alt="Erlang logo" src="../erlang-logo.png"><br><small><a href="users_guide.html">User's Guide</a><br><a href="../pdf/otp-system-documentation-5.9.3.1.pdf">PDF</a><br><a href="../index.html">Top</a></small><p><strong>Programming Examples</strong><br><strong>User's Guide</strong><br><small>Version 5.9.3.1</small></p>
<br><a href="javascript:openAllFlips()">Expand All</a><br><a href="javascript:closeAllFlips()">Contract All</a><p><small><strong>Chapters</strong></small></p>
<ul class="flipMenu" imagepath="../js/flipmenu">
<li id="no" title="Records" expanded="false">Records<ul>
<li><a href="records.html">
              Top of chapter
            </a></li>
<li title="Records vs Tuples"><a href="records.html#id60765">Records vs Tuples</a></li>
<li title="Defining a Record"><a href="records.html#id60728">Defining a Record</a></li>
<li title="Creating a Record"><a href="records.html#id59920">Creating a Record</a></li>
<li title="Accessing a Record Field"><a href="records.html#id60048">Accessing a Record Field</a></li>
<li title="Updating a Record"><a href="records.html#id61983">Updating a Record</a></li>
<li title="Type Testing"><a href="records.html#id60031">Type Testing</a></li>
<li title="Pattern Matching"><a href="records.html#id60080">Pattern Matching</a></li>
<li title="Nested Records"><a href="records.html#id61405">Nested Records</a></li>
<li title="Example"><a href="records.html#id57989">Example</a></li>
</ul>
</li>
<li id="no" title="Funs" expanded="false">Funs<ul>
<li><a href="funs.html">
              Top of chapter
            </a></li>
<li title="Example 1 - map"><a href="funs.html#id64362">Example 1 - map</a></li>
<li title="Example 2 - foreach"><a href="funs.html#id57513">Example 2 - foreach</a></li>
<li title="The Syntax of Funs"><a href="funs.html#id61441">The Syntax of Funs</a></li>
<li title="Variable Bindings Within a Fun"><a href="funs.html#id61096">Variable Bindings Within a Fun</a></li>
<li title="Funs and the Module Lists"><a href="funs.html#id61883">Funs and the Module Lists</a></li>
<li title="Funs Which Return Funs"><a href="funs.html#id62549">Funs Which Return Funs</a></li>
</ul>
</li>
<li id="loadscrollpos" title="List Comprehensions" expanded="true">List Comprehensions<ul>
<li><a href="list_comprehensions.html">
              Top of chapter
            </a></li>
<li title="Simple Examples"><a href="list_comprehensions.html#id63964">Simple Examples</a></li>
<li title="Quick Sort"><a href="list_comprehensions.html#id64034">Quick Sort</a></li>
<li title="Permutations"><a href="list_comprehensions.html#id64089">Permutations</a></li>
<li title="Pythagorean Triplets"><a href="list_comprehensions.html#id64141">Pythagorean Triplets</a></li>
<li title="Simplifications with List Comprehensions"><a href="list_comprehensions.html#id64218">Simplifications with List Comprehensions</a></li>
<li title="Variable Bindings in List Comprehensions"><a href="list_comprehensions.html#id64241">Variable Bindings in List Comprehensions</a></li>
</ul>
</li>
<li id="no" title="Bit Syntax" expanded="false">Bit Syntax<ul>
<li><a href="bit_syntax.html">
              Top of chapter
            </a></li>
<li title="Introduction"><a href="bit_syntax.html#id64741">Introduction</a></li>
<li title="A Lexical Note"><a href="bit_syntax.html#id65026">A Lexical Note</a></li>
<li title="Segments"><a href="bit_syntax.html#id65049">Segments</a></li>
<li title="Defaults"><a href="bit_syntax.html#id65237">Defaults</a></li>
<li title="Constructing Binaries and Bitstrings"><a href="bit_syntax.html#id65297">Constructing Binaries and Bitstrings</a></li>
<li title="Matching Binaries"><a href="bit_syntax.html#id65485">Matching Binaries</a></li>
<li title="Appending to a Binary"><a href="bit_syntax.html#id65619">Appending to a Binary</a></li>
</ul>
</li>
</ul>
</div></div>
<div id="content">
<div class="innertube">
<h1>3 List Comprehensions</h1>
  

  <h3><a name="id63964">3.1 
        Simple Examples</a></h3>
    
    <p>We start with a simple example:</p>
    <div class="example"><pre>
&gt; <span class="bold_code">[X || X &lt;- [1,2,a,3,4,b,5,6], X &gt; 3].</span>
[a,4,b,5,6]</pre></div>
    <p>This should be read as follows:</p>
    
      <p>The list of X such that X is taken from the list
        <span class="code">[1,2,a,...]</span> and X is greater than 3.</p>
    
    <p>The notation <span class="code">X &lt;- [1,2,a,...]</span> is a generator and
      the expression <span class="code">X &gt; 3</span> is a filter.</p>
    <p>An additional filter can be added in order to restrict
      the result to integers:</p>
    <div class="example"><pre>
&gt; <span class="bold_code">[X || X &lt;- [1,2,a,3,4,b,5,6], integer(X), X &gt; 3].</span>
[4,5,6]</pre></div>
    <p>Generators can be combined. For example, the Cartesian product
      of two lists can be written as follows:</p>
    <div class="example"><pre>
&gt; <span class="bold_code">[{X, Y} || X &lt;- [1,2,3], Y &lt;- [a,b]].</span>
[{1,a},{1,b},{2,a},{2,b},{3,a},{3,b}]</pre></div>
  

  <h3><a name="id64034">3.2 
        Quick Sort</a></h3>
    
    <p>The well known quick sort routine can be written as follows:</p>
    <div class="example"><pre>
sort([Pivot|T]) -&gt;
    sort([ X || X &lt;- T, X &lt; Pivot]) ++
    [Pivot] ++
    sort([ X || X &lt;- T, X &gt;= Pivot]);
sort([]) -&gt; [].</pre></div>
    <p>The expression <span class="code">[X || X &lt;- T, X &lt; Pivot]</span> is the list of
      all elements in <span class="code">T</span>, which are less than <span class="code">Pivot</span>.</p>
    <p><span class="code">[X || X &lt;- T, X &gt;= Pivot]</span> is the list of all elements in
      <span class="code">T</span>, which are greater or equal to <span class="code">Pivot</span>.</p>
    <p>To sort a list, we isolate the first element in the list and
      split the list into two sub-lists. The first sub-list contains
      all elements which are smaller than the first element in
      the list, the second contains all elements which are greater
      than or equal to the first element in the list. We then sort
      the sub-lists and combine the results.</p>
  

  <h3><a name="id64089">3.3 
        Permutations</a></h3>
    
    <p>The following example generates all permutations of
      the elements in a list:</p>
    <div class="example"><pre>
perms([]) -&gt; [[]];
perms(L)  -&gt; [[H|T] || H &lt;- L, T &lt;- perms(L--[H])].</pre></div>
    <p>We take take <span class="code">H</span> from <span class="code">L</span> in all possible ways.
      The result is the set of all lists <span class="code">[H|T]</span>, where <span class="code">T</span>
      is the set of all possible permutations of <span class="code">L</span> with
      <span class="code">H</span> removed.</p>
    <div class="example"><pre>
&gt; <span class="bold_code">perms([b,u,g]).</span>
[[b,u,g],[b,g,u],[u,b,g],[u,g,b],[g,b,u],[g,u,b]]</pre></div>
  

  <h3><a name="id64141">3.4 
        Pythagorean Triplets</a></h3>
    
    <p>Pythagorean triplets are sets of integers <span class="code">{A,B,C}</span> such
      that <span class="code">A**2 + B**2 = C**2</span>.</p>
    <p>The function <span class="code">pyth(N)</span> generates a list of all integers
      <span class="code">{A,B,C}</span> such that <span class="code">A**2 + B**2 = C**2</span> and where
      the sum of the sides is equal to or less than <span class="code">N</span>.</p>
    <div class="example"><pre>
pyth(N) -&gt;
    [ {A,B,C} ||
        A &lt;- lists:seq(1,N),
        B &lt;- lists:seq(1,N),
        C &lt;- lists:seq(1,N),
        A+B+C =&lt; N,
        A*A+B*B == C*C 
    ].</pre></div>
    <div class="example"><pre>
&gt; <span class="bold_code">pyth(3).</span>
[].
&gt; <span class="bold_code">pyth(11).</span>
[].
&gt; <span class="bold_code">pyth(12).</span>
[{3,4,5},{4,3,5}]
&gt; <span class="bold_code">pyth(50).</span>
[{3,4,5},
 {4,3,5},
 {5,12,13},
 {6,8,10},
 {8,6,10},
 {8,15,17},
 {9,12,15},
 {12,5,13},
 {12,9,15},
 {12,16,20},
 {15,8,17},
 {16,12,20}]</pre></div>
    <p>The following code reduces the search space and is more
      efficient:</p>
    <div class="example"><pre>
pyth1(N) -&gt;
   [{A,B,C} ||
       A &lt;- lists:seq(1,N-2),
       B &lt;- lists:seq(A+1,N-1),
       C &lt;- lists:seq(B+1,N),
       A+B+C =&lt; N,
       A*A+B*B == C*C ].</pre></div>
  

  <h3><a name="id64218">3.5 
        Simplifications with List Comprehensions</a></h3>
    
    <p>As an example, list comprehensions can be used to simplify some
      of the functions in <span class="code">lists.erl</span>:</p>
    <div class="example"><pre>
append(L)   -&gt;  [X || L1 &lt;- L, X &lt;- L1].
map(Fun, L) -&gt; [Fun(X) || X &lt;- L].
filter(Pred, L) -&gt; [X || X &lt;- L, Pred(X)].</pre></div>
  

  <h3><a name="id64241">3.6 
        Variable Bindings in List Comprehensions</a></h3>
    
    <p>The scope rules for variables which occur in list
      comprehensions are as follows:</p>
    <ul>
      <li>all variables which occur in a generator pattern are
       assumed to be "fresh" variables</li>
      <li>any variables which are defined before the list
       comprehension and which are used in filters have the values
       they had before the list comprehension</li>
      <li>no variables may be exported from a list comprehension.</li>
    </ul>
    <p>As an example of these rules, suppose we want to write
      the function <span class="code">select</span>, which selects certain elements from
      a list of tuples. We might write
      <span class="code">select(X, L) -&gt;  [Y || {X, Y} &lt;- L].</span> with the intention
      of extracting all tuples from <span class="code">L</span> where the first item is
      <span class="code">X</span>.</p>
    <p>Compiling this yields the following diagnostic:</p>
    <div class="example"><pre>
./FileName.erl:Line: Warning: variable 'X' shadowed in generate</pre></div>
    <p>This diagnostic warns us that the variable <span class="code">X</span> in
      the pattern is not the same variable as the variable <span class="code">X</span>
      which occurs in the function head.</p>
    <p>Evaluating <span class="code">select</span> yields the following result:</p>
    <div class="example"><pre>
&gt; <span class="bold_code">select(b,[{a,1},{b,2},{c,3},{b,7}]).</span>
[1,2,3,7]</pre></div>
    <p>This result is not what we wanted. To achieve the desired
      effect we must write <span class="code">select</span> as follows:</p>
    <div class="example"><pre>
select(X, L) -&gt;  [Y || {X1, Y} &lt;- L, X == X1].</pre></div>
    <p>The generator now contains unbound variables and the test has
      been moved into the filter. This now works as expected:</p>
    <div class="example"><pre>
&gt; <span class="bold_code">select(b,[{a,1},{b,2},{c,3},{b,7}]).</span>
[2,7]</pre></div>
    <p>One consequence of the rules for importing variables into a
      list comprehensions is that certain pattern matching operations
      have to be moved into the filters and cannot be written directly
      in the generators. To illustrate this, do not write as follows:</p>
    <div class="example"><pre>
f(...) -&gt;
    Y = ...
    [ Expression || PatternInvolving Y  &lt;- Expr, ...]
    ...</pre></div>
    <p>Instead, write as follows:</p>
    <div class="example"><pre>
f(...) -&gt;
    Y = ...
    [ Expression || PatternInvolving Y1  &lt;- Expr, Y == Y1, ...]
    ...</pre></div>
  
</div>
<div class="footer">
<hr>
<p>Copyright © 2003-2012 Ericsson AB. All Rights Reserved.</p>
</div>
</div>
</div></body>
</html>

Perl :: Catalyst :: PostgreSQL :: RPM Valid HTML 4.01 Transitional