モジュール (module) はデータ構造とそれを操作する関数を一つにまとめるための仕組みです。最近はモジュールに相当する機能を持つプログラミング言語が多くなりました。Erlang にもモジュールはありますが、その機能はもっと単純なもので、基本的には複数の関数をまとめるための容器になります。機能単位で関数をモジュールにまとめておけば、ユーザーにとって使いやすいライブラリを構築することができます。実際、Erlang には実用的なモジュールが標準で多数用意されています。
「Erlang の基礎知識」で簡単に説明しましたが、Erlang の関数はモジュールの中で定義します。-module はモジュールを宣言する文です。
-module(test).
上の例では、モジュール名を test と宣言しています。このとき、ファイル名はモジュールと同じ名前 (test.erl) でなければなりません。-export は公開する関数名をリストで宣言します。関数名のあとに「引数の個数 (arity)」を指定します。Erlang の場合、引数の個数が異なれば同名の関数をいくつでも定義することができます。
-import はモジュールから関数を取り込みます。
-import(モジュール名, [関数名/ariyt, ...]).
-import で宣言された関数は、モジュール名を省略して呼び出すことができます。
簡単な例を示しましょう。
リスト : export と import
-module(test).
-export([distance/2]).
-import(math, [sqrt/1]).
distance({X1, Y1}, {X2, Y2}) ->
Dx = X1 - X2,
Dy = Y1 - Y2,
sqrt(Dx * Dx + Dy * Dy).
sqrt はモジュール math に定義されていますが、-import で関数名を取り込むことにより、math: を付けなくても呼び出すことができます。
> c(test).
{ok,test}
> test:distance({0, 0}, {10, 10}).
14.142135623730951
-compile はコンパイルオプションを指定します。export_all を指定すると、モジュール内で定義された関数をすべて公開することができます。その他のオプションは Erlang のリファレンスマニュアル Compile をお読みください。
このほかに -record でレコードの定義を、-vsn でモジュールのバージョンを宣言することができます。レコードについては次章で詳しく説明します。
簡単な例として「スタック (stack)」というデータ構造を考えてみましょう。次の図を見てください。
|-----| |[ A ]| |[ B ]| |[ A ]| |-----|
| | | |-----| |[ A ]| |-----| | | |
| | | | | | |-----| | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
+-----+ +-----+ +-----+ +-----+ +-----+
(1) 空の状態 (2) PUSH A (3) PUSH B (4) POP B (5) POP A
図 : スタックの動作例
上図は、バネがついた容器を表していて、上から品物を出し入れすることができます。初めは空の状態です。ここに品物を乗せると、重さによってバネを圧縮し、品物が容器に格納されます。さらにもう一つ品物を上に乗せると、さらにバネを圧縮し、その品物も容器に格納することができます。バネが限界まで圧縮されると、もう品物は追加できなくなります。取り出す場合は、上にある品物から行います。一つ取り出すと、その分バネが伸びて下にある品物が上に押し出されます。
この容器の動作が、スタックの動作なのです。スタックにデータを追加する操作をプッシュ (PUSH) といい、スタックからデータを取り出す操作をポップ (POP) といいます。品物をデータに見立てれば、データ A をスタックにプッシュし (2)、次にデータ B をプッシュします (3)。データを取り出す場合、あとから入れたデータ B が先にポップされ (4)、その次にデータ A がポップされてスタックが空になります (5)。このように、スタックはあとから入れたデータが先に取り出されるので、後入れ先出し (LIFO : Last-In, First-Out) と呼ばれます。
Erlang の場合、スタックはリストを使って簡単に実現することができます。データを追加するときはリストの先頭に追加し、データを取り出すときはリストの先頭から行うように操作を限定すると、それはスタックの動作と同じになります。次のリストを見てください。
リスト : スタック
-module(stack).
-export([new/0, push/2, top/1, pop/1, is_empty/1]).
% スタックの生成
new() -> {stack, []}.
% データの追加
push({stack, Xs}, X) -> {stack, [X | Xs]}.
% データの取得
top({stack, [X | _]}) -> X.
% データの削除
pop({stack, [_ | Xs]}) -> {stack, Xs}.
% スタックは空か
is_empty({stack, []}) -> true;
is_empty({stack, _}) -> false.
スタックはタプル {stack, Xs} で表します。第 1 要素の stack はスタックを表すデータ型として使います。第 2 要素のリスト Xs がスタック本体になるリストです。スタックの操作関数は簡単です。push/2 はデータをリストの先頭に追加します。pop/1 はリストの先頭要素を取り除きます。データの取得は関数 top/1 で行います。関数 is_empty/1 はスタックが空かチェックする述語です。
簡単な使用例を示します。
> S0 = stack:new().
{stack,[]}
> S1 = stack:push(S0, 10).
{stack,"\n"}
> stack:top(S1).
10
> S2 = stack:push(S1, 20).
{stack,[20,10]}
> S3 = stack:push(S2, 30).
{stack,[30,20,10]}
> stack:top(S3).
30
> S4 = stack:pop(S3).
{stack,[20,10]}
> stack:top(S4).
20
> stack:is_empty(S0).
true
> stack:is_empty(S4).
false
正常に動作していますね。関数型言語の場合、変数の値を書き換えることができないので、push や pop の返り値 (スタック) を別の変数に格納する必要があります。ご注意くださいませ。
もうひとつ簡単な例を示しましょう。キューは「待ち行列」といわれるデータ構造です。たとえばチケットを買う場合、窓口に長い列ができますが、それと同じだと考えてください。チケットを買うときは、列の途中に割り込むことはできませんね。いちばん後ろに並んで順番を待たなければいけません。列の先頭まで進むと、チケットを購入することができます。
このように、要素を取り出す場合は列の先頭から行い、要素を追加する場合は列の後ろに行うデータ構造がキューなのです。キューは「先入れ先出し (FIFO : first-in, first-out)」とも呼ばれます。
先頭 最後尾
---------------------------
<= 1 2 3 4 5 . . . n <=
---------------------------
先頭 最後尾
変数 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
queue ─→│・│・┼─→│・│・┼─→│・│・┼・・・→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓ ↓
１ ２ ３ ｎ
図 : キューの構造
キューにデータを入れることを enqueue といい、キューからデータを取り出すことを dequeue といいます。リストを使ってキューを実装する場合、上図のようにキューの先頭とリストの先頭を対応させます。すると、キューからデータを取り出すには、リストの先頭からデータを取り出すだけですみます。これはとても簡単ですね。
ただし、キューにデータを入れるには、リストの最後尾にデータを追加することになるため、ちょっとした工夫が必要になります。たとえば、データの追加に演算子 ++ を使うと、データを追加するたびにリスト（キュー）がコピーされてしまいます。このため、キューに格納されているデータが多くなると時間がかかるようになります。
先頭
変数 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
front ─→│０│・┼─→│１│・┼─→│２│／│
└─┴─┘ └─┴─┘ └─┴─┘
最後尾
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
rear ─→│５│・┼─→│４│・┼─→│３│／│
└─┴─┘ └─┴─┘ └─┴─┘
図 : キューの構造（改良版）
これを回避する方法はいろいろ考えられるのですが、今回は関数型言語で用いられる簡単な方法を紹介します。上図は 2 つのリストでキューを表しています。データを取り出すときは front のリストを、データを追加するときは rear のリストを使います。front と rear で一つのキューを構成し、rear のリストはデータを逆順で格納することになります。ようするに、front が先頭で rear が最後尾になるわけです。上図のキューを一つのリストで表すと [0, 1, 2, 3, 4, 5] になります。
したがって、front が空リストでも rear にデータがあれば、キューは空ではありません。rear のリストを逆順にして front にセットし、rear を空リストにします。これで front からデータを取り出すことができます。キューが空の状態は front と rear が両方とも空リストの場合です。
それではプログラムを作りましょう。次のリストを見てください。Erlang にはモジュール queue が標準で用意されているので、モジュール名は myque としました。
リスト : キューの実装
-module(myque).
-export([new/0, enqueue/2, dequeue/1, front/1, is_empty/1]).
% キューの生成
new()-> {queue, [], []}.
% データの追加
enqueue({queue, Front, Rear}, X) -> {queue, Front, [X | Rear]}.
% データの削除
dequeue({queue, [_ | Xs], Rear}) -> {queue, Xs, Rear};
dequeue({queue, [], []}) -> false;
dequeue({queue, [], Rear}) -> dequeue({queue, lists:reverse(Rear), []}).
% 先頭データの取得
front({queue, [X | _], _}) -> X;
front({queue, [], []}) -> false;
front({queue, [], Rear}) -> front({queue, lists:reverse(Rear), []}).
% キューは空か
is_empty({queue, [], []}) -> true;
is_empty({queue, [_ | _], _}) -> false;
is_empty({queue, _, [_ | _]}) -> false.
キューはタプル {queue, Front, Rear} で表します。関数 new/0 は空のキュー {queue, [], []} を返します。関数 enqueue/2 はキューにデータ X を追加します。これは X を Rear の先頭に追加するだけです。関数 dequeue/1 はキューからデータを取り除きます。キューが空の場合は false を返します。まだ説明していませんが、ここはエラーを送出したほうがよいでしょう。
front が空リストの場合は、キュー {queue, reverse(Rear), []} を作って dequeue を再帰呼び出しします。front にデータがある場合は先頭要素を取り除くだけです。関数 front/1 はキューの先頭要素を返します。処理は dequeue とほとんど同じで、違いは front の先頭データ X を返すだけです。関数 is_empty/1 は、キューが空であれば true を、そうでなければ false を返します。
それでは簡単な実行例を示します。
> Q0 = myque:new().
{queue,[],[]}
> Q1 = myque:enqueue(Q0, 10).
{queue,[],"\n"}
> Q2 = myque:enqueue(Q1, 20).
{queue,[],[20,10]}
> Q3 = myque:enqueue(Q2, 30).
{queue,[],[30,20,10]}
> myque:front(Q3).
10
> Q4 = myque:dequeue(Q3).
{queue,[20,30],[]}
> myque:front(Q4).
20
> Q5 = myque:dequeue(Q4).
{queue,[30],[]}
> myque:front(Q5).
30
> myque:is_empty(Q0).
true
> myque:is_empty(Q5).
false
正常に動作していますね。