File: list_comprehensions.html

package info (click to toggle)
erlang-doc-html 1%3A11.b.2-1
links: PTS
area: main
in suites: etch, etch-m68k
size: 23,284 kB
ctags: 10,724
sloc: erlang: 505; ansic: 323; makefile: 62; perl: 61; sh: 45
file content (245 lines) | stat: -rw-r--r-- 6,848 bytes
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<!-- This document was generated using DocBuilder 3.3.3 -->
<HTML>
<HEAD>
  <TITLE>List Comprehensions</TITLE>
  <SCRIPT type="text/javascript" src="../../doc/erlresolvelinks.js">
</SCRIPT>
</HEAD>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#FF00FF"
      ALINK="#FF0000">
<CENTER>
<A HREF="http://www.erlang.se"><IMG BORDER=0 ALT="[Ericsson AB]" SRC="min_head.gif"></A>
</CENTER>
<A NAME="3"><!-- Empty --></A>
<H2>3 List Comprehensions</H2>
<A NAME="3.1"><!-- Empty --></A>
<H3>3.1 Simple Examples</H3>

<P>We start with a simple example:
<PRE>
&#62; <STRONG>[X || X &#60;- [1,2,a,3,4,b,5,6], X &#62; 3].</STRONG>
[a,4,b,5,6]
    
</PRE>

<P>This should be read as follows:
<BLOCKQUOTE>

<P>The list of X such that X is taken from the list
        <CODE>[1,2,a,...]</CODE> and X is greater than 3.
</BLOCKQUOTE>

<P>The notation <CODE>X &#60;- [1,2,a,...]</CODE> is a generator and
the expression <CODE>X &#62; 3</CODE> is a filter.
<P>An additional filter can be added in order to restrict
the result to integers:
<PRE>
&#62; <STRONG>[X || X &#60;- [1,2,a,3,4,b,5,6], integer(X), X &#62; 3].</STRONG>
[4,5,6]
    
</PRE>

<P>Generators can be combined. For example, the Cartesian product
of two lists can be written as follows:
<PRE>
&#62; <STRONG>[{X, Y} || X &#60;- [1,2,3], Y &#60;- [a,b]].</STRONG>
[{1,a},{1,b},{2,a},{2,b},{3,a},{3,b}]
    
</PRE>
<A NAME="3.2"><!-- Empty --></A>
<H3>3.2 Quick Sort</H3>

<P>The well known quick sort routine can be written as follows:
<PRE>
sort([Pivot|T]) -&#62;
    sort([ X || X &#60;- T, X &#60; Pivot]) ++
    [Pivot] ++
    sort([ X || X &#60;- T, X &#62;= Pivot]);
sort([]) -&#62; [].
    
</PRE>

<P>The expression <CODE>[X || X &#60;- T, X &#60; Pivot]</CODE> is the list of
all elements in <CODE>T</CODE>, which are less than <CODE>Pivot</CODE>.
<P><CODE>[X || X &#60;- T, X &#62;= Pivot]</CODE> is the list of all elements in
<CODE>T</CODE>, which are greater or equal to <CODE>Pivot</CODE>.
<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.<A NAME="3.3"><!-- Empty --></A>
<H3>3.3 Permutations</H3>

<P>The following example generates all permutations of
the elements in a list:
<PRE>
perms([]) -&#62; [[]];
perms(L)  -&#62; [[H|T] || H &#60;- L, T &#60;- perms(L--[H])].
    
</PRE>

<P>We take take <CODE>H</CODE> from <CODE>L</CODE> in all possible ways.
The result is the set of all lists <CODE>[H|T]</CODE>, where <CODE>T</CODE>
is the set of all possible permutations of <CODE>L</CODE> with
<CODE>H</CODE> removed.
<PRE>
&#62; <STRONG>perms([b,u,g]).</STRONG>
[[b,u,g],[b,g,u],[u,b,g],[u,g,b],[g,b,u],[g,u,b]]
    
</PRE>
<A NAME="3.4"><!-- Empty --></A>
<H3>3.4 Pythagorean Triplets</H3>

<P>Pythagorean triplets are sets of integers <CODE>{A,B,C}</CODE> such
that <CODE>A**2 + B**2 = C**2</CODE>.
<P>The function <CODE>pyth(N)</CODE> generates a list of all integers
<CODE>{A,B,C}</CODE> such that <CODE>A**2 + B**2 = C**2</CODE> and where
the sum of the sides is less than <CODE>N</CODE>.
<PRE>
pyth(N) -&#62;
    [ {A,B,C} ||
        A &#60;- lists:seq(1,N),
        B &#60;- lists:seq(1,N),
        C &#60;- lists:seq(1,N),
        A+B+C =&#60; N,
        A*A+B*B == C*C 
    ].
    
</PRE>

<PRE>
&#62; <STRONG>pyth(3).</STRONG>
[].
&#62; <STRONG>pyth(11).</STRONG>
[].
&#62; <STRONG>pyth(12).</STRONG>
[{3,4,5},{4,3,5}]
&#62; <STRONG>pyth(50).</STRONG>
[{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>

<P>The following code reduces the search space and is more
efficient:
<PRE>
pyth1(N) -&#62;
   [{A,B,C} ||
       A &#60;- lists:seq(1,N-2),
       B &#60;- lists:seq(A+1,N-1),
       C &#60;- lists:seq(B+1,N),
       A+B+C =&#60; N,
       A*A+B*B == C*C ].
    
</PRE>
<A NAME="3.5"><!-- Empty --></A>
<H3>3.5 Simplifications with List Comprehensions</H3>

<P>As an example, list comprehensions can be used to simplify some
of the functions in <CODE>lists.erl</CODE>:
<PRE>
append(L)   -&#62;  [X || L1 &#60;- L, X &#60;- L1].
map(Fun, L) -&#62; [Fun(X) || X &#60;- L].
filter(Pred, L) -&#62; [X || X &#60;- L, Pred(X)].
    
</PRE>
<A NAME="3.6"><!-- Empty --></A>
<H3>3.6 Variable Bindings in List Comprehensions</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 &#34;fresh&#34; 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 <CODE>select</CODE>, which selects certain elements from
a list of tuples. We might write
<CODE>select(X, L) -&#62; [Y || {X, Y} &#60;- L].</CODE> with the intention
of extracting all tuples from <CODE>L</CODE> where the first item is
<CODE>X</CODE>.
<P>Compiling this yields the following diagnostic:

<PRE>
./FileName.erl:Line: Warning: variable 'X' shadowed in generate
    
</PRE>

<P>This diagnostic warns us that the variable <CODE>X</CODE> in
the pattern is not the same variable as the variable <CODE>X</CODE>
which occurs in the function head.
<P>Evaluating <CODE>select</CODE> yields the following result:
<PRE>
&#62; <STRONG>select(b,[{a,1},{b,2},{c,3},{b,7}]).</STRONG>
[1,2,3,7]
    
</PRE>

<P>This result is not what we wanted. To achieve the desired
effect we must write <CODE>select</CODE> as follows:
<PRE>
select(X, L) -&#62;  [Y || {X1, Y} &#60;- L, X == X1].
    
</PRE>

<P>The generator now contains unbound variables and the test has
been moved into the filter. This now works as expected:
<PRE>
&#62; <STRONG>select(b,[{a,1},{b,2},{c,3},{b,7}]).</STRONG>
[2,7]
    
</PRE>

<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:

<PRE>
f(...) -&#62;
    Y = ...
    [ Expression || PatternInvolving Y  &#60;- Expr, ...]
    ...
    
</PRE>

<P>Instead, write as follows:
<PRE>
f(...) -&#62;
    Y = ...
    [ Expression || PatternInvolving Y1  &#60;- Expr, Y == Y1, ...]
    ...
    
</PRE>
<CENTER>
<HR>
<SMALL>
Copyright &copy; 1991-2006
<A HREF="http://www.erlang.se">Ericsson AB</A><BR>
</SMALL>
</CENTER>
</BODY>
</HTML>