リストを組み立てるのは、リストの末尾から要素を足していくことでのみ行うことができます。++演算子を使いたい場合には以下のようにします:
List1 ++ List2
この演算の結果、List1の要素のコピーにList2がつながった新しいリストを作ることができます。lists:append/1もしくは++がどのようにプレーンなErlangで実装されるのかを見ると、最初のリストがコピーされる理由というものがはっきりと理解できるでしょう。:
append([H|T], Tail) ->
[H|append(T, Tail)];
append([], Tail) ->
Tail.
重要なことは、再帰をしてリストを作成する場合は、リストの先方に新しい要素を足していきます。そうすると、リストの組み立てを行うのに、結果のリストに要素を足していくたびに何百回も何千回ものコピーをすることがなくなります。
まずはすべきでない実装方法について見てみましょう。
非推奨:
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]).
ここではリストを組み立てているのではなく、繰り返しのステップの中で、一つ前のリストよりも長さが１つだけ長い、新しいリストを新規で作成することになります。
繰り返しの中でコピーをするのを避けるには、逆順でリストを組み立て、組み立て終わったらリストを反転させる必要があります。
推奨:
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]).
リスト内包表記には、使用すると遅くなるという噂が未だに残っています。以前のリスト内包表記の実装ではfunが使用されていました。以前の実装ではfun自体の動作が遅いという問題がありました。
現在のErlang/OTPのリリース(R12B以降)では以下のようなリスト内包表記は、基本的に、ローカルの関数として変換されます。:
[Expr(E) || E <- List]
変換後は以下のようなコードになります。:
'lc^0'([E|Tail], Expr) ->
[Expr(E)|'lc^0'(Tail, Expr)];
'lc^0'([], _Expr) -> [].
R12Bでは、リスト内包表記の結果のリストが明らかに使用されないという状況では、リストは構築されなくなります。例えば以下のような場合には作成されません:
[io:put_chars(E) || E <- List],
ok.
もしくはこのような場合にも作成されません:
.
.
.
case Var of
... ->
[io:put_chars(E) || E <- List];
... ->
end,
some_function(...),
.
.
.
この場足、値は変数に格納されることもありませんし、他の関数に渡されたり、返り値として返されることもありません。ここではコンパイラが、リストを作成する必要がないということを知ることができるため、リスト内包表記のコードもシンプルに生成します。
'Lc^0'([E|Tail], Expr) ->
Expr(E),
'lc^0'(Tail, Expr);
'lc^0'([], _Expr) -> [].
lists:flatten/1 を実行すると、完全に新しいリストを構築します。そのため、この関数の呼び出しは++演算よりも処理時間が多くかかります。ちなみに、++演算子は左側の引数のコピーは行われますが、右側の引数のコピーは行われません。
以下のような状況であれば、lists:flatten/1の呼び出しを避けることができます。
推奨:
...
port_command(Port, DeepList)
...
非推奨:
...
port_command(Port, lists:flatten(DeepList))
...
ゼロ終端された文字列をポートに送信する際は一般的には以下のように行われます。
非推奨:
...
TerminatedStr = String ++ [0], % String="foo" => [$f, $o, $o, 0]
port_command(Port, TerminatedStr)
...
代わりに以下のようにしてください。
推奨:
...
TerminatedStr = [String, 0], % String="foo" => [[$f, $o, $o], 0]
port_command(Port, TerminatedStr)
...
推奨:
> lists:append([[1], [2], [3]]).
[1,2,3]
>
非推奨:
> lists:flatten([[1], [2], [3]]).
[1,2,3]
>
パフォーマンスの都市伝説に関する章では、”末尾再帰関数は、再帰関数と比べて「べらぼう」に高速である”というものが説明されています。
簡単にまとめると、R12B以降の実装では、通常の場合は、リストに対して、本体で再帰する関数と、末尾で再帰させて、最後にリストを反転させる関数ではそれほどパフォーマンスの差はない、というものでした。そのため、どちらの実装の方が美しく書けるか、という点のみを気にしていればよく、リストの関数のパフォーマンスについては忘れてしまうことが可能です。時間の制約の厳しいコードを書く際は、コードを書き直す前に、測定するようにしてください。
重要な情報: このセクションでは、リストを作成する関数について説明してきました。リストを作成しない末尾再帰関数は一定のメモリ消費で呼び出すことができます。本体再帰の関数はリストの長さに応じたスタック領域を消費します。リストに格納されている数値を足す関数は以下のように書きます。
非推奨:
recursive_sum([H|T]) -> H+recursive_sum(T);
recursive_sum([]) -> 0.
but like this
推奨:
sum(L) -> sum(L, 0).
sum([H|T], Sum) -> sum(T, Sum + H);
sum([], Sum) -> Sum.