今回はレコード (record) について説明します。Erlang のレコードはタプルの特別な形式で、タプルの要素に名前を付けたデータ構造です。レコードは名前を使って要素にアクセスすることができるので、要素の順番を覚えておく必要はありません。
レコードを利用する場合、最初にレコードを定義する必要があります。Erlang の場合、ファイル内 (モジュール) で -record(...) 文を使って宣言するのが一般的です。
-record(レコード名, {名前1, ..., 名前N}).
Eshell 上では関数 rd を使ってレコードを定義することができます。引数は -record と同じです。
このほかに、レコードの定義をひとつのファイルにまとめて、それを読み込む方法もあります。この場合、ファイルの拡張子は .hrl とし、関数 rr() で読み込むことができます。
レコードの生成は次のように行います。
#レコード名{名前1 = 式1, ..., 名前N = 式N}.
名前は「フィールド」と呼ばれることがあります。式の評価結果がフィールドの値になります。次の例を見てください。
> rd(foo, {bar, baz}).
foo
> R1 = #foo{bar = 10, baz = 20}.
#foo{bar = 10,baz = 20}
> R1.
#foo{bar = 10,baz = 20}
> R2 = #foo{bar = 100}.
#foo{bar = 100,baz = undefined}
> R2.
#foo{bar = 100,baz = undefined}
> #foo{}.
#foo{bar = undefined,baz = undefined}
値を指定しないとフィールドには undefined というデフォルト値がセットされます。
フィールドの値は次の式で求めることができます。
式#レコード名.フィールド名
式の評価結果はレコードでなければなりません。簡単な例を示しましょう。
> R1#foo.bar. 10 > R1#foo.baz. 20 > R2#foo.bar. 100 > R2#foo.baz. undefined
レコードに "#レコード名.フィールド名" を適用すると、フィールドに格納されている値を参照することができます。
Erlang のレコードは変数と同様に値を書き換えることはできませんが、値を置き換えた新しいレコードを返すことは簡単にできます。
> R3 = R2#foo{baz = 200}.
#foo{bar = 100,baz = 200}
> R2.
#foo{bar = 100,baz = undefined}
> R3.
#foo{bar = 100,baz = 200}
R2#foo{baz = 200} は R2 の baz の値を 200 に置き換えた新しいレコードを生成して変数 R3 にセットします。R2 の値は変わっていませんが、R3 の baz は 200 になります。
もちろん、レコードでもパターンを使うことができます。次の例を見てください。
> R4 = #foo{bar = 0, baz = 1}.
#foo{bar = 0,baz = 1}
> #foo{bar = Bar, baz = Baz} = R4.
#foo{bar = 0,baz = 1}
> Bar.
0
> Baz.
1
>#foo{bar = Bar1} = R4.
#foo{bar = 0,baz = 1}
> Bar1.
0
"フィールド名 = パターン" とすると指定したフィールドの値とパターンがマッチングします。{bar = Bar, baz = Baz} は変数 Bar とフィールド bar の値、変数 Baz とフィールド baz の値がマッチングして、Bar = 0, Baz = 1 になります。また、パターンマッチングのときに、すべてのフィールドを指定する必要はありません。bar = Bar1 だけを指定すると、Bar1 とフィールド bar の値がマッチングします。
レコードは入れ子にすることもできます。次の例を見てください。
> rd(foo1, {a, b}).
foo1
> rd(bar1, {c, d = #foo1{}}).
bar1
> #foo1{}.
#foo1{a = undefined,b = undefined}
> #bar1{}.
#bar1{c = undefined,d = #foo1{a = undefined,b = undefined}}
> RR = #bar1{c = 10, d = #foo1{a = 20, b = 30}}.
#bar1{c = 10,d = #foo1{a = 20,b = 30}}
> RR.
#bar1{c = 10,d = #foo1{a = 20,b = 30}}
> RR#bar1.c.
10
> RR#bar1.d.
#foo1{a = 20,b = 30}
> RR#bar1.d#foo1.a.
20
> RR#bar1.d#foo1.b.
30
> RR1 = RR#bar1{d = RR#bar1.d#foo1{a = 100}}.
#bar1{c = 10,d = #foo1{a = 100,b = 30}}
最初にレコード foo1 を定義します。次にレコード bar1 を定義しますが、その中で d = #foo1{} とすると、レコード foo1 を入れ子することができます。#bar1{} でレコードを生成すると、d の値には foo1 のレコードがセットされます。値を指定する場合は、b = #foo1{a = 10, b = 20} とすることで、foo1 のフィールド a, b の値を 10, 20 にセットすることができます。
入れ子のレコードのアクセスも簡単です。レコード foo1 は RR#bar1.d に格納されているので、RR#bar1.d#foo1.a とすればフィールド a に、RR#bar1.d#foo1.b とすればフィールド b にアクセスすることができます。ただし、入れ子のレコードの場合、フィールドの値を置き換えるのはちょっと面倒です。foo1 だけでではなく bar1 のレコードも新しく生成する必要があります。RR#bar1.d#foo1{a = 100} とすると、a の値を 100 に置き換えた foo1 のレコードが新たに生成されるだけです。ご注意くださいませ。
それでは簡単な例題として「二分探索木」という基本的なデータ構造を作ってみましょう。まず最初に二分探索木から説明します。二分木を理解されている方は読み飛ばしてもらってかまいません。
あるデータの中から特定のデータを探す場合、データ数が少なければ力任せに探索してもなんとかなりますが、データ数が多くなると探索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。この代表的なアルゴリズムが「ハッシュ法」と「二分探索木」です。二分探索木はその名が示すように「木構造」の一種です。まずは木構造から説明しましょう。
「木構造 (tree structer)」は「木 (tree)」とも呼ばれるデータ構造で、「節 (ノード)」と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート)」と呼ばれる節が存在します。
(root)
Ａ ──────── レベル０
／｜＼ ↑
／ ｜ ＼
Ｂ Ｃ Ｄ 木 レベル１
／｜＼ ｜＼ の
／ ｜ ＼ ｜ ＼ 高
Ｅ Ｆ Ｇ Ｈ Ｉ さ レベル２
／ ＼
／ ＼ ↓
Ｊ Ｋ ───── レベル３
図 : 一般的な木構造の一例
木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っています。これを「部分木」といいます。
木は、ある節からほかの節に至る「経路」を考えることができます。たとえば、A から J には、A - B - G - J という経路がありますね。これは、ディレクトリやファイルを指定するときのパスと同じです。
ある節から根の方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接繋がっている節を「親」といます。これは、逆から見ると「子孫」と「子」という関係になります。子を持たない節をとくに「葉」と呼ぶことがあります。上図でいうと、G は J と K の親で、J は G の子になります。J は子を持っていないので葉となります。
子は、「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」といいます。また、順番がない木を「無順序木」と呼びます。節が持っている子の数を「次数」といいます。上図の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。すべての節の次数を n に揃えた順序木を「 n 分木」と呼びます。
とくに、次数が 2 の二分木は、プログラムでよく使われるデータ構造です。
(root)
18
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
14 22
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 20 24
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 19 21 23 25
図 : 二分木の一例
上図に二分木の例を示します。二分木では、節にひとつのデータを格納します。そして、その節の左側の子には小さいデータを、右側の子には大きいデータが配置されるように木を構成します。
この二分木をデータの探索に使うアルゴリズムが「二分探索木」です。二分探索木はデータの探索・挿入を高速に行うことができます。たとえば、上図の木から 19 を探してみましょう。まず root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。
二分探索木の探索は「二分探索 (binary search)」と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。
データ数を N とすると、単純な線形探索では平均で N / 2 回の比較が必要になりますが、二分探索木を使うと log 2 N 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。
そこで、左右のバランスを一定の範囲に収める「平衡木」が考案されています。有名なところでは AVL 木、2-3 木、B 木、B* 木などがあります。また、Ｃ++の標準ライブラリである STL (Standard Template Library) では、「2 色木 (赤黒木)」というアルゴリズムが使われているそうです。今回は Erlang の勉強ということで、単純な二分探索木をプログラムすることにします。なお、本稿では二分探索木のことを単に「二分木」と書くことにします。
それでは、Erlang で二分木を作ってみましょう。最初に -record で二分木の節を定義します。
リスト : 二分木の定義
-module(tree).
-export([search_tree/2, insert_tree/2, delete_tree/2, foreach_tree/2]).
% 二分木の節
% 空の木は null とする
-record(node, {data, left, right}).
レコードで節 (node) を表します。レコード名は node としました。空の木をアトム null で表します。フィールド data が二分木に格納するデータ、left が左部分木、right が右部分木を表します。簡単な例を示します。
12
／ ＼ ==> {node, 12, {node, 11, null, null}, {node, 13, null, null}}
11 13
これを図で表すと次のようになります。
┌─┬─┬─┐
│12│・│・│
└─┴┼┴┼┘
│ │
┌──────┘ └─┐
↓ ↓
┌─┬─┬─┐ ┌─┬─┬─┐
│11│／│／│ │13│／│／│
└─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐
節：│Ｄ│Ｌ│Ｒ│
└─┴─┴─┘
Ｄ：data, Ｌ：left, Ｒ：right, ／：null
図 : 二分木の構造
それでは、データを探索する関数から作ってみましょう。この処理はデータを比較して左右の部分木をたどっていくだけです。
リスト : データの探索
search_tree(_, null) -> false;
search_tree(X, #node{data = X}) -> true;
search_tree(X, #node{data = D, left = L}) when X < D -> search_tree(X, L);
search_tree(X, #node{right = R}) -> search_tree(X, R).
関数 search_tree の第 1 引数 X が探索するデータ、第 2 引数が二分木です。二分木が null であれば、これ以上探索することはできません。データは見つからなかったので false を返します。そうでなければ、引数 X と node のデータを比較します。2 番目の節は X と node 内の data が等しい場合です。データが見つかったので true を返します。
3 番目の節は、X が node のデータ D よりも小さい場合です。search_tree を再帰呼び出しして左部分木をたどります。最後の節は X が D よりも大きい場合です。search_tree を再帰呼び出しして右部分木をたどります。
次は、データを挿入する関数を作りましょう。探索と同様に、データを比較して木をたどっていき、木がなくなった所に新しいデータを挿入します。
リスト : データの挿入
insert_tree(X, null) ->
#node{data = X, left = null, right = null};
insert_tree(X, Node) when X < Node#node.data ->
Node#node{left = insert_tree(X, Node#node.left)};
insert_tree(X, Node) when X > Node#node.data ->
Node#node{right = insert_tree(X, Node#node.right)};
insert_tree(_, Node) -> Node.
関数 insert_tree の第 1 引数 X が挿入するデータ、第 2 引数が二分木です。二分木が null であれば、新しい節を作って返します。この返り値を node の部分木にセットします。
X < Node#node.data であれば、insert_tree を再帰呼び出しして左部分木 left をたどります。そして、left を insert_tree の返り値に置き換えた節を生成して返します。もしも、left が null であれば、ここに新しい節が挿入され、新しい部分木が返されます。X > Node#node.data であれば右部分木をたどり、データを挿入した新しい右部分木を返します。最後の節は X と Node#node.data が等しい場合です。Node をそのまま返します。
次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 null 17
↑
15 を削除する 削除
図 : データの削除（葉の場合）
15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。
次に、子が一つある場合を考えてみましょう。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 15
／ ＼ ／ ／ ＼
11 13 15 11 13
16 を削除する
図 : データの削除（子が一つの場合）
16 を削除する場合、その子である 15 と置き換えれば二分木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。
14 15 <- 最小値と置き換え
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 null 17
↑
14 を削除する 削除
図 : データの削除（子が二つの場合）
この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。たとえば、上図で 14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。
まずは木の中から最小値を探す関数と、最小値の節を削除する関数を作成しましょう。次のリストを見てください。
リスト : 最小値の探索と削除
% 最小値を探す
search_min(#node{data = D, left = null}) -> D;
search_min(#node{left = L}) -> search_min(L).
% 最小値を削除する
delete_min(#node{left = null, right = R}) -> R;
delete_min(Node) -> Node#node{left = delete_min(Node#node.left)}.
二分木の場合、最小値は簡単に求めることができます。左側の子を順番にたどっていき、左側の子がない節に行き着いたとき、その節のデータが最小値になります。関数 search_min の最初の節で、左側の子が null かチェックします。そうであれば左側の子がないので、その節のデータが最小値です。格納されているデータ D を返します。そうでなければ次の節で search_min を再帰呼び出しして左側の子をたどります。
関数 delete_min は最小値を格納している節を削除します。左側の子が null の節を探すのは search_min と同じです。見つけたら、もう一つの子 right を返します。そうでなければ、delete_min を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を格納した新しい節を返します。これで、最小値を持つ節が削除されます。葉の場合であれば right は null なので、単純に削除されることになります。
それでは、データを削除する関数 delete を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。
リスト : データの削除
delete_tree(_, null) -> null;
delete_tree(X, Node) when X < Node#node.data ->
Node#node{left = delete_tree(X, Node#node.left)};
delete_tree(X, Node) when X > Node#node.data ->
Node#node{right = delete_tree(X, Node#node.right)};
delete_tree(_, #node{left = null, right = R}) -> R;
delete_tree(_, #node{left = L, right = null}) -> L;
delete_tree(_, #node{left = L, right = R}) ->
Min = search_min(R),
#node{data = Min, left = L, right = delete_min(R)}.
まず、節が null ならばデータが見つからなかったので null をそのまま返します。エラーを送出してもよいでしょう。X と node のデータが等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は今までと同じで、delete_tree の返り値を格納した新しい節を返します。
削除するデータ X と node のデータが等しい場合はその節を削除します。4, 5 番目の節で、left が null の場合は right を返し、right が null の場合は left を返します。子が 2 つある場合は、右部分木の最小値を関数 search_min で求め、その値を格納した新しい節を作ります。このとき、関数 delete_min で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換えることができます。
最後に、二分木の全データにアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。
二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理は、再帰定義を使えば簡単に実現できます。
リスト : 二分木の巡回
foreach_tree(_, null) -> ok;
foreach_tree(F, #node{data = D, left = L, right = R}) ->
foreach_tree(F, L), F(D), foreach_tree(F, R).
関数 foreach_tree は二分木を通りがけ順に巡回し、格納されているデータに関数 F を適用します。まず、二分木が null ならば何もしないで ok を返します。これが再帰呼び出しの停止条件となります。あとは通りがけ順の定義そのままにプログラムをするだけです。左部分木をたどるため、left に対して foreach_tree を再帰呼び出しします。次に、node のデータ D に関数 F を適用します。最後に右部分木をたどるため、right に対して foreach_tree を再帰呼び出しします。
それでは簡単な実行例を示しましょう。
> RT = lists:foldl(fun(X, A) -> tree:insert_tree(X, A) end, null,
[50, 30, 20, 40, 70, 80, 60]).
{node,50,
{node,30,{node,20,null,null},{node,40,null,null}},
{node,70,{node,60,null,null},{node,80,null,null}}}
> tree:foreach_tree(fun(X) -> io:write(X), io:nl() end, RT).
20
30
40
50
60
70
80
ok
> tree:search_tree(20, RT).
true
> tree:search_tree(80, RT).
true
> tree:search_tree(0, RT).
false
> tree:search_tree(100, RT).
false
> tree:search_tree(55, RT).
false
> RT1 = tree:delete_tree(20, RT).
{node,50,
{node,30,null,{node,40,null,null}},
{node,70,{node,60,null,null},{node,80,null,null}}}
> RT2 = tree:delete_tree(80, RT).
{node,50,
{node,30,{node,20,null,null},{node,40,null,null}},
{node,70,{node,60,null,null},null}}
> RT3 = tree:delete_tree(30, RT).
{node,50,
{node,40,{node,20,null,null},null},
{node,70,{node,60,null,null},{node,80,null,null}}}
> RT4 = tree:delete_tree(70, RT).
{node,50,
{node,30,{node,20,null,null},{node,40,null,null}},
{node,80,{node,60,null,null},null}}
> RT5 = tree:delete_tree(50, RT).
{node,60,
{node,30,{node,20,null,null},{node,40,null,null}},
{node,70,null,{node,80,null,null}}}
> lists:foldl(fun(X, A) -> tree:delete_tree(X, A) end, RT, [50, 30, 20, 40, 70, 80, 60]).
null
正常に動作していますね。
リスト : 二分木
-module(tree).
-export([search_tree/2, insert_tree/2, delete_tree/2, foreach_tree/2]).
% 二分木の節
% 空の木は null とする
-record(node, {data, left, right}).
% データの探索
search_tree(_, null) -> false;
search_tree(X, #node{data = X}) -> true;
search_tree(X, #node{data = D, left = L}) when X < D -> search_tree(X, L);
search_tree(X, #node{right = R}) -> search_tree(X, R).
% データの挿入
insert_tree(X, null) ->
#node{data = X, left = null, right = null};
insert_tree(X, Node) when X < Node#node.data ->
Node#node{left = insert_tree(X, Node#node.left)};
insert_tree(X, Node) when X > Node#node.data ->
Node#node{right = insert_tree(X, Node#node.right)};
insert_tree(_, Node) -> Node.
% 最小値を探す
search_min(#node{data = D, left = null}) -> D;
search_min(#node{left = L}) -> search_min(L).
% 最小値を削除する
delete_min(#node{left = null, right = R}) -> R;
delete_min(Node) -> Node#node{left = delete_min(Node#node.left)}.
% データの削除
delete_tree(_, null) -> null;
delete_tree(X, Node) when X < Node#node.data ->
Node#node{left = delete_tree(X, Node#node.left)};
delete_tree(X, Node) when X > Node#node.data ->
Node#node{right = delete_tree(X, Node#node.right)};
delete_tree(_, #node{left = null, right = R}) -> R;
delete_tree(_, #node{left = L, right = null}) -> L;
delete_tree(_, #node{left = L, right = R}) ->
Min = search_min(R),
#node{data = Min, left = L, right = delete_min(R)}.
% 二分木の巡回
foreach_tree(_, null) -> ok;
foreach_tree(F, #node{data = D, left = L, right = R}) ->
foreach_tree(F, L), F(D), foreach_tree(F, R).