<!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 handling</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>Efficiency Guide</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="Introduction" expanded="false">Introduction<ul>
<li><a href="introduction.html">
Top of chapter
</a></li>
<li title="Purpose"><a href="introduction.html#id62954">Purpose</a></li>
<li title="Prerequisites"><a href="introduction.html#id65420">Prerequisites</a></li>
</ul>
</li>
<li id="no" title="The Eight Myths of Erlang Performance" expanded="false">The Eight Myths of Erlang Performance<ul>
<li><a href="myths.html">
Top of chapter
</a></li>
<li title="Myth: Funs are slow"><a href="myths.html#id64448">Myth: Funs are slow</a></li>
<li title="Myth: List comprehensions are slow"><a href="myths.html#id61406">Myth: List comprehensions are slow</a></li>
<li title="Myth: Tail-recursive functions are MUCH faster
than recursive functions"><a href="myths.html#id62291">Myth: Tail-recursive functions are MUCH faster
than recursive functions</a></li>
<li title="Myth: '++' is always bad"><a href="myths.html#id60058">Myth: '++' is always bad</a></li>
<li title="Myth: Strings are slow"><a href="myths.html#id62534">Myth: Strings are slow</a></li>
<li title="Myth: Repairing a Dets file is very slow"><a href="myths.html#id61135">Myth: Repairing a Dets file is very slow</a></li>
<li title="Myth: BEAM is a stack-based byte-code virtual machine (and therefore slow)"><a href="myths.html#id64006">Myth: BEAM is a stack-based byte-code virtual machine (and therefore slow)</a></li>
<li title="Myth: Use '_' to speed up your program when a variable is not used"><a href="myths.html#id64026">Myth: Use '_' to speed up your program when a variable is not used</a></li>
</ul>
</li>
<li id="no" title="Common Caveats" expanded="false">Common Caveats<ul>
<li><a href="commoncaveats.html">
Top of chapter
</a></li>
<li title="The timer module"><a href="commoncaveats.html#id62547">The timer module</a></li>
<li title="list_to_atom/1"><a href="commoncaveats.html#id61885">list_to_atom/1</a></li>
<li title="length/1"><a href="commoncaveats.html#id60806">length/1</a></li>
<li title="setelement/3"><a href="commoncaveats.html#id58300">setelement/3</a></li>
<li title="size/1"><a href="commoncaveats.html#id65402">size/1</a></li>
<li title="split_binary/2"><a href="commoncaveats.html#id60836">split_binary/2</a></li>
<li title="The '--' operator"><a href="commoncaveats.html#id61766">The '--' operator</a></li>
</ul>
</li>
<li id="no" title="Constructing and matching binaries" expanded="false">Constructing and matching binaries<ul>
<li><a href="binaryhandling.html">
Top of chapter
</a></li>
<li title="How binaries are implemented"><a href="binaryhandling.html#id62932">How binaries are implemented</a></li>
<li title="Constructing binaries"><a href="binaryhandling.html#id66066">Constructing binaries</a></li>
<li title="Matching binaries"><a href="binaryhandling.html#id63610">Matching binaries</a></li>
</ul>
</li>
<li id="loadscrollpos" title="List handling" expanded="true">List handling<ul>
<li><a href="listHandling.html">
Top of chapter
</a></li>
<li title="Creating a list"><a href="listHandling.html#id66709">Creating a list</a></li>
<li title="List comprehensions"><a href="listHandling.html#id66805">List comprehensions</a></li>
<li title="Deep and flat lists"><a href="listHandling.html#id66875">Deep and flat lists</a></li>
<li title="Why you should not worry about recursive lists functions"><a href="listHandling.html#id67017">Why you should not worry about recursive lists functions</a></li>
</ul>
</li>
<li id="no" title="Functions" expanded="false">Functions<ul>
<li><a href="functions.html">
Top of chapter
</a></li>
<li title="Pattern matching"><a href="functions.html#id67142">Pattern matching</a></li>
<li title="Function Calls "><a href="functions.html#id67362">Function Calls </a></li>
<li title="Memory usage in recursion"><a href="functions.html#id67506">Memory usage in recursion</a></li>
</ul>
</li>
<li id="no" title="Tables and databases" expanded="false">Tables and databases<ul>
<li><a href="tablesDatabases.html">
Top of chapter
</a></li>
<li title="Ets, Dets and Mnesia"><a href="tablesDatabases.html#id67596">Ets, Dets and Mnesia</a></li>
<li title="Ets specific"><a href="tablesDatabases.html#id67983">Ets specific</a></li>
<li title="Mnesia specific"><a href="tablesDatabases.html#id68087">Mnesia specific</a></li>
</ul>
</li>
<li id="no" title="Processes" expanded="false">Processes<ul>
<li><a href="processes.html">
Top of chapter
</a></li>
<li title="Creation of an Erlang process"><a href="processes.html#id68191">Creation of an Erlang process</a></li>
<li title="Process messages"><a href="processes.html#id68339">Process messages</a></li>
<li title="The SMP emulator"><a href="processes.html#id68531">The SMP emulator</a></li>
</ul>
</li>
<li id="no" title="Drivers" expanded="false">Drivers<ul>
<li><a href="drivers.html">
Top of chapter
</a></li>
<li title="Drivers and concurrency"><a href="drivers.html#id68634">Drivers and concurrency</a></li>
<li title="Avoiding copying of binaries when calling a driver"><a href="drivers.html#id68675">Avoiding copying of binaries when calling a driver</a></li>
<li title="Returning small binaries from a driver"><a href="drivers.html#id68743">Returning small binaries from a driver</a></li>
<li title="Returning big binaries without copying from a driver"><a href="drivers.html#id68777">Returning big binaries without copying from a driver</a></li>
</ul>
</li>
<li id="no" title="Advanced" expanded="false">Advanced<ul>
<li><a href="advanced.html">
Top of chapter
</a></li>
<li title="Memory"><a href="advanced.html#id68919">Memory</a></li>
<li title="System limits"><a href="advanced.html#id69276">System limits</a></li>
</ul>
</li>
<li id="no" title="Profiling" expanded="false">Profiling<ul>
<li><a href="profiling.html">
Top of chapter
</a></li>
<li title="Do not guess about performance - profile"><a href="profiling.html#id69579">Do not guess about performance - profile</a></li>
<li title="Big systems"><a href="profiling.html#id69661">Big systems</a></li>
<li title="What to look for"><a href="profiling.html#id69681">What to look for</a></li>
<li title="Tools"><a href="profiling.html#id69738">Tools</a></li>
<li title="Benchmarking"><a href="profiling.html#id70245">Benchmarking</a></li>
</ul>
</li>
</ul>
</div></div>
<div id="content">
<div class="innertube">
<h1>5 List handling</h1>
<h3><a name="id66709">5.1
Creating a list</a></h3>
<p>Lists can only be built starting from the end and attaching
list elements at the beginning. If you use the <span class="code">++</span> operator
like this</p>
<div class="example"><pre>
List1 ++ List2</pre></div>
<p>you will create a new list which is copy of the elements in <span class="code">List1</span>,
followed by <span class="code">List2</span>. Looking at how <span class="code">lists:append/1</span> or <span class="code">++</span> would be
implemented in plain Erlang, it can be seen clearly that the first list
is copied:</p>
<div class="example"><pre>
append([H|T], Tail) ->
[H|append(T, Tail)];
append([], Tail) ->
Tail.</pre></div>
<p>So the important thing when recursing and building a list is to
make sure that you attach the new elements to the beginning of the list,
so that you build <strong>a</strong> list, and not hundreds or thousands of
copies of the growing result list.</p>
<p>Let us first look at how it should not be done:</p>
<p><strong>DO NOT</strong></p>
<div class="example"><pre>
bad_fib(N) ->
bad_fib(N, 0, 1, []).
bad_fib(0, _Current, _Next, Fibs) ->
Fibs;
bad_fib(N, Current, Next, Fibs) ->
bad_fib(N - 1, Next, Current + Next, Fibs ++ [Current]).</pre></div>
<p>Here we are not a building a list; in each iteration step we
create a new list that is one element longer than the new previous list.</p>
<p>To avoid copying the result in each iteration, we must build the list in
reverse order and reverse the list when we are done:</p>
<p><strong>DO</strong></p>
<div class="example"><pre>
tail_recursive_fib(N) ->
tail_recursive_fib(N, 0, 1, []).
tail_recursive_fib(0, _Current, _Next, Fibs) ->
lists:reverse(Fibs);
tail_recursive_fib(N, Current, Next, Fibs) ->
tail_recursive_fib(N - 1, Next, Current + Next, [Current|Fibs]).</pre></div>
<h3><a name="id66805">5.2
List comprehensions</a></h3>
<p>Lists comprehensions still have a reputation for being slow.
They used to be implemented using funs, which used to be slow.</p>
<p>In recent Erlang/OTP releases (including R12B), a list comprehension</p>
<div class="example"><pre>
[Expr(E) || E <- List]</pre></div>
<p>is basically translated to a local function</p>
<div class="example"><pre>
'lc^0'([E|Tail], Expr) ->
[Expr(E)|'lc^0'(Tail, Expr)];
'lc^0'([], _Expr) -> [].</pre></div>
<p>In R12B, if the result of the list comprehension will <strong>obviously</strong> not be used,
a list will not be constructed. For instance, in this code</p>
<div class="example"><pre>
[io:put_chars(E) || E <- List],
ok.</pre></div>
<p>or in this code</p>
<div class="example"><pre>
.
.
.
case Var of
... ->
[io:put_chars(E) || E <- List];
... ->
end,
some_function(...),
.
.
.</pre></div>
<p>the value is neither assigned to a variable, nor passed to another function,
nor returned, so there is no need to construct a list and the compiler will simplify
the code for the list comprehension to</p>
<div class="example"><pre>
'lc^0'([E|Tail], Expr) ->
Expr(E),
'lc^0'(Tail, Expr);
'lc^0'([], _Expr) -> [].</pre></div>
<h3><a name="id66875">5.3
Deep and flat lists</a></h3>
<p><span class="bold_code"><a href="javascript:erlhref('../../','stdlib','lists.html#flatten-1');">lists:flatten/1</a></span>
builds an entirely new list. Therefore, it is expensive, and even
<strong>more</strong> expensive than the <span class="code">++</span> (which copies its left argument,
but not its right argument).</p>
<p>In the following situations, you can easily avoid calling <span class="code">lists:flatten/1</span>:</p>
<ul>
<li>When sending data to a port. Ports understand deep lists
so there is no reason to flatten the list before sending it to
the port.</li>
<li>When calling BIFs that accept deep lists, such as
<span class="bold_code"><a href="javascript:erlhref('../../','erts','erlang.html#list_to_binary-1');">list_to_binary/1</a></span> or
<span class="bold_code"><a href="javascript:erlhref('../../','erts','erlang.html#iolist_to_binary-1');">iolist_to_binary/1</a></span>.</li>
<li>When you know that your list is only one level deep, you can can use
<span class="bold_code"><a href="javascript:erlhref('../../','stdlib','lists.html#append-1');">lists:append/1</a></span>.</li>
</ul>
<p><strong>Port example</strong></p>
<p><strong>DO</strong></p>
<div class="example"><pre>
...
port_command(Port, DeepList)
...</pre></div>
<p><strong>DO NOT</strong></p>
<div class="example"><pre>
...
port_command(Port, lists:flatten(DeepList))
...</pre></div>
<p>A common way to send a zero-terminated string to a port is the following:</p>
<p><strong>DO NOT</strong></p>
<div class="example"><pre>
...
TerminatedStr = String ++ [0], % String="foo" => [$f, $o, $o, 0]
port_command(Port, TerminatedStr)
...</pre></div>
<p>Instead do like this:</p>
<p><strong>DO</strong></p>
<div class="example"><pre>
...
TerminatedStr = [String, 0], % String="foo" => [[$f, $o, $o], 0]
port_command(Port, TerminatedStr)
...</pre></div>
<p><strong>Append example</strong></p>
<p><strong>DO</strong></p>
<div class="example"><pre>
> lists:append([[1], [2], [3]]).
[1,2,3]
></pre></div>
<p><strong>DO NOT</strong></p>
<div class="example"><pre>
> lists:flatten([[1], [2], [3]]).
[1,2,3]
></pre></div>
<h3><a name="id67017">5.4
Why you should not worry about recursive lists functions</a></h3>
<p>In the performance myth chapter, the following myth was exposed:
<span class="bold_code"><a href="myths.html#tail_recursive">Tail-recursive functions
are MUCH faster than recursive functions</a></span>.</p>
<p>To summarize, in R12B there is usually not much difference between
a body-recursive list function and tail-recursive function that reverses
the list at the end. Therefore, concentrate on writing beautiful code
and forget about the performance of your list functions. In the time-critical
parts of your code (and only there), <strong>measure</strong> before rewriting
your code.</p>
<p><strong>Important note</strong>: This section talks about lists functions that
<strong>construct</strong> lists. A tail-recursive function that does not construct
a list runs in constant space, while the corresponding body-recursive
function uses stack space proportional to the length of the list.
For instance, a function that sums a list of integers, should <strong>not</strong> be
written like this</p>
<p><strong>DO NOT</strong></p>
<div class="example"><pre>
recursive_sum([H|T]) -> H+recursive_sum(T);
recursive_sum([]) -> 0.</pre></div>
<p>but like this</p>
<p><strong>DO</strong></p>
<div class="example"><pre>
sum(L) -> sum(L, 0).
sum([H|T], Sum) -> sum(T, Sum + H);
sum([], Sum) -> Sum.</pre></div>
</div>
<div class="footer">
<hr>
<p>Copyright © 2001-2012 Ericsson AB. All Rights Reserved.</p>
</div>
</div>
</div></body>
</html>
distrib
>
Fedora
>
17
>
i386
>
media
>
updates
>
by-pkgid
>
675c8c8167236dfcf8d66da674f931e8
>
files
>
50
