素晴らしいErlangを

学ぼう！

• ホーム
• FAQ
• RSS
• コード

一般的なデータ構造の簡単な紹介

長くなりすぎないことを約束します！

おそらくあなたは今、Erlangの関数型サブセットをかなりよく理解しており、多くのプログラムを問題なく読むことができるでしょう。しかし、最後の章が関数型の方法で問題を解決することだったとしても、実際に役立つプログラムをどのように構築するかを考えるのは、まだ少し難しいだろうと私は確信しています。これは、私が学習のその時点でどのように感じていたかによるものですが、もしあなたがよりうまくやっているなら、おめでとうございます！

とにかく、私が言いたいのは、私たちはたくさんのものを見てきたということです。最も基本的なデータ型、シェル、モジュールと関数（再帰付き）の書き方、さまざまなコンパイル方法、プログラムのフローの制御、例外の処理、いくつかの一般的な操作の抽象化などです。タプル、リスト、およびバイナリ検索ツリーの不完全な実装によるデータの格納方法も見てきました。まだ見ていないのは、Erlang標準ライブラリでプログラマに提供される他のデータ構造です。

レコード

まず、レコードはハックです。それらは言語への後付けのようなものであり、不便な点も少なからずあります。それについては後で説明します。名前で属性に直接アクセスしたい小さなデータ構造がある場合は、依然として非常に便利です。そのため、ErlangレコードはCの構造体によく似ています（Cを知っている場合）。

それらは次のようにモジュール属性として宣言されます。

-module(records).
-compile(export_all).

-record(robot, {name,
                type=industrial,
                hobbies,
                details=[]}).

ここでは、name、type、hobbies、detailsの4つのフィールドを持つロボットを表すレコードがあります。また、typeとdetailsにはそれぞれデフォルト値industrialと[]があります。モジュールrecordsでレコードを宣言する方法を次に示します。

first_robot() ->
    #robot{name="Mechatron",
           type=handmade, 
           details=["Moved by a small man inside"]}.

そしてコードを実行します。

1> c(records).
{ok,records}
2> records:first_robot().
{robot,"Mechatron",handmade,undefined,
       ["Moved by a small man inside"]}

おっと！ここでハックが登場！Erlangレコードは、タプルの上に乗ったシンタックスシュガーにすぎません。幸い、これを改善する方法があります。Erlangシェルには、Moduleからレコード定義をロードできるコマンドrr(Module)があります。

3> rr(records).
[robot]
4> records:first_robot().         
#robot{name = "Mechatron",type = handmade,
       hobbies = undefined,
       details = ["Moved by a small man inside"]}

ああ、できました！これでレコードを操作するのがずっと簡単になります。first_robot/0では、hobbiesフィールドを定義しておらず、宣言にデフォルト値がなかったことに気づくでしょう。Erlangはデフォルトで、値をundefinedに設定します。

robot定義で設定したデフォルトの動作を確認するために、次の関数をコンパイルしましょう。

car_factory(CorpName) ->
    #robot{name=CorpName, hobbies="building cars"}.

そしてそれを実行します。

5> c(records).
{ok,records}
6> records:car_factory("Jokeswagen").
#robot{name = "Jokeswagen",type = industrial,
       hobbies = "building cars",details = []}

そして、私たちは車を組み立てるのが好きな工業用ロボットを持っています。

レコードを記述するだけではあまり役に立ちません。レコードから値を抽出する方法が必要です。これを行うには基本的に2つの方法があります。1つ目は、特別な「ドット構文」を使用することです。ロボットのレコード定義がロードされていると仮定します。

5> Crusher = #robot{name="Crusher", hobbies=["Crushing people","petting cats"]}. 
#robot{name = "Crusher",type = industrial,
       hobbies = ["Crushing people","petting cats"],
       details = []}
6> Crusher#robot.hobbies.
["Crushing people","petting cats"]

うーん、きれいな構文ではありません。これは、レコードがタプルであるという性質によるものです。それらは一種のコンパイラトリックにすぎないため、どのレコードがどの変数に対応するかを定義するキーワードを保持する必要があり、そのためCrusher#robot.hobbiesの#robot部分が必要になります。残念ですが、それを回避する方法はありません。さらに悪いことに、ネストされたレコードは非常に醜くなります。

7> NestedBot = #robot{details=#robot{name="erNest"}}.
#robot{name = undefined,type = industrial,
       hobbies = undefined,
       details = #robot{name = "erNest",type = industrial,
                        hobbies = undefined,details = []}}
8> (NestedBot#robot.details)#robot.name. 
"erNest"

そして、はい、括弧は必須です。

レコードのタプルへの依存性をさらに示すために、以下を参照してください。

9> #robot.type.
3

これは、基礎となるタプルのどの要素であるかを出力します。

レコードの1つの優れた機能は、関数ヘッドでのパターンマッチングやガードでの使用が可能であることです。ファイルの先頭に次のように新しいレコードを宣言し、その下に次の関数を追加します。

-record(user, {id, name, group, age}).

%% use pattern matching to filter
admin_panel(#user{name=Name, group=admin}) ->
    Name ++ " is allowed!";
admin_panel(#user{name=Name}) ->
    Name ++ " is not allowed".

%% can extend user without problem
adult_section(U = #user{}) when U#user.age >= 18 ->
    %% Show stuff that can't be written in such a text
    allowed;
adult_section(_) ->
    %% redirect to sesame street site
    forbidden.

レコードの任意のフィールドに変数をバインドするための構文は、admin_panel/1関数で示されています（複数のフィールドに変数をバインドできます）。adult_section/1関数について注意すべき重要な点は、レコード全体を変数にバインドするためにSomeVar = #some_record{}を実行する必要があることです。次に、通常どおりコンパイルを行います。

10> c(records).
{ok,records}
11> rr(records).
[robot,user]
12> records:admin_panel(#user{id=1, name="ferd", group=admin, age=96}).
"ferd is allowed!"
13> records:admin_panel(#user{id=2, name="you", group=users, age=66}). 
"you is not allowed"
14> records:adult_section(#user{id=21, name="Bill", group=users, age=72}).
allowed
15> records:adult_section(#user{id=22, name="Noah", group=users, age=13}).
forbidden

これにより、関数を作成するときに、タプルのすべての部分を照合したり、タプルがいくつあるかを知る必要がないことがわかります。必要な場合は年齢またはグループのみを照合し、構造の残りの部分はすべて無視できます。通常のタプルを使用する場合、関数定義はfunction({record, _, _, ICareAboutThis, _, _}) -> ...のようになっている可能性があります。次に、誰かがタプルに要素を追加すると、他の誰か（おそらくそれらすべてに腹を立てている）が、そのタプルが使用されているすべての関数を更新する必要があります。

次の関数は、レコードを更新する方法を示しています（そうでないと、あまり役に立たないでしょう）。

repairman(Rob) ->
    Details = Rob#robot.details,
    NewRob = Rob#robot{details=["Repaired by repairman"|Details]},
    {repaired, NewRob}.

そして次に、

16> c(records).
{ok,records}
17> records:repairman(#robot{name="Ulbert", hobbies=["trying to have feelings"]}).
{repaired,#robot{name = "Ulbert",type = industrial,
                 hobbies = ["trying to have feelings"],
                 details = ["Repaired by repairman"]}}

そして、私のロボットが修理されたことがわかります。レコードを更新するための構文は、ここでは少し特殊です。レコードをインプレースで更新しているように見えます（Rob#robot{Field=NewValue}）が、これはすべて、基礎となるerlang:setelement/3関数を呼び出すためのコンパイラトリックです。

レコードに関する最後のこと。レコードは非常に便利で、コードの重複は煩わしいので、Erlangプログラマは、ヘッダーファイルの助けを借りてモジュール間でレコードを頻繁に共有します。Erlangヘッダーファイルは、Cの対応するものと非常によく似ています。それらは、最初に記述されたかのようにモジュールに追加されるコードスニペットにすぎません。records.hrlという名前のファイルを作成し、次の内容を記述します。

%% this is a .hrl (header) file.
-record(included, {some_field,
                   some_default = "yeah!",
                   unimaginative_name}).

それをrecords.erlに含めるには、次の行をモジュールに追加するだけです。

-include("records.hrl").

そして、それを試すための次の関数。

included() -> #included{some_field="Some value"}.

次に、通常どおりに試してください。

18> c(records).
{ok,records}
19> rr(records).
[included,robot,user]
20> records:included().
#included{some_field = "Some value",some_default = "yeah!",
          unimaginative_name = undefined}

やった！レコードについては以上です。醜いですが便利です。構文はきれいではなく、ハックにすぎませんが、コードの保守性にとっては比較的重要です。

キーと値のストア

数章前にツリーを作成させましたが、その用途はアドレス帳のキーと値のストアとして使用することでした。そのアドレス帳はひどいものでした。削除したり、役立つものに変換したりすることができませんでした。それは再帰の良い実証でしたが、それ以上のことはありませんでした。今こそ、特定のキーの下にデータを格納するための便利なデータ構造とモジュールをいくつか紹介するときです。すべての関数が何をするかを定義したり、すべてのモジュールを調べたりすることはありません。ドキュメントページへのリンクを貼り付けるだけです。Erlangのキーと値のストアに関する「意識を高める」責任のある人として私を考えてください。良いタイトルになりそうです。これらのリボンが1つ必要です。

少量のデータの場合、基本的に2つのデータ構造を使用できます。1つ目はプロパティリストと呼ばれます。プロパティリストは、[{Key,Value}]の形式のタプルの任意のリストです。他にルールがないため、それらは奇妙な種類の構造です。実際、ルールは非常に緩いため、リストにはブール値、整数、および必要なものを含めることもできます。ここでは、リスト内のキーと値を持つタプルのアイデアにむしろ関心があります。プロパティリストを操作するには、proplistsモジュールを使用できます。これには、proplists:delete/2、proplists:get_value/2、proplists:get_all_values/2、proplists:lookup/2、proplists:lookup_all/2などの関数が含まれています。

リストの要素を追加または更新する関数がないことに気づくでしょう。これは、プロパティリストがデータ構造としていかに緩く定義されているかを示しています。これらの機能を取得するには、要素を手動で連結し（[NewElement|OldList]）、lists:keyreplace/4などの関数を使用する必要があります。1つの小さなデータ構造に2つのモジュールを使用することは最もクリーンなことではありませんが、プロパティリストは非常に緩く定義されているため、構成リストや、特定のアイテムの一般的な説明を処理するためによく使用されます。プロパティリストは、正確には完全なデータ構造ではありません。それらは、いくつかのオブジェクトまたはアイテムを表すためにリストとタプルを使用するときに現れる一般的なパターンに近く、プロパティリストモジュールはそのようなパターンに関するツールボックスのようなものです。

少量のデータに対して、より完全なキーと値のストアが必要な場合は、orddictモジュールが必要です。順序付き辞書（orddict）は、形式を好むプロパティリストです。各キーは1回存在でき、リスト全体が平均ルックアップを高速化するためにソートされます。一般的な関数は次のとおりです。CRUD使用には、orddict:store/3、orddict:find/2（キーが辞書にあるかどうか不明な場合）、orddict:fetch/2（そこにあること、または必ずある必要があることがわかっている場合）、orddict:erase/2などがあります。

順序付き辞書は、約75要素までの複雑さと効率の間の一般的に優れた妥協点です（私のベンチマークを参照）。それ以降の量については、別のキーと値のストアに切り替える必要があります。

大量のデータを扱うための主要なキーバリューストレージ/モジュールには、基本的に dicts と gb_trees の2つがあります。辞書(dicts)は、orddict と同じインターフェースを持ちます。dict:store/3, dict:find/2, dict:fetch/2, dict:erase/2 や、dict:map/2, dict:fold/2 (データ構造全体を扱うのに非常に便利！) のような他の全ての関数も同様です。このように、dicts は、必要に応じて orddicts をスケールアップするための非常に良い選択肢となります。

一方、一般平衡木(General Balanced Trees)は、構造体の使用方法をより直接的に制御できる、より多くの関数を持っています。gb_treesには基本的に2つのモードがあります。それは、構造を熟知しているモード（私はこれを「スマートモード」と呼びます）と、構造についてあまり想定できないモード（私はこれを「ナイーブモード」と呼びます）です。ナイーブモードでは、関数は gb_trees:enter/3, gb_trees:lookup/2, gb_trees:delete_any/2 です。関連するスマート関数は、gb_trees:insert/3, gb_trees:get/2, gb_trees:update/3, gb_trees:delete/2 です。また、必要なときにいつでも便利な gb_trees:map/2 もあります。

「スマート」関数に対する「ナイーブ」関数の欠点は、gb_trees が平衡木であるため、新しい要素を挿入したり（または多くの要素を削除したり）するたびに、木がバランスを調整する必要がある可能性があることです。これには時間とメモリがかかる可能性があります（単に確認するためだけの無駄なチェックであっても）。「スマート」関数はすべて、キーがツリー内に存在することを前提としています。これにより、すべての安全チェックをスキップでき、より高速な処理が可能になります。

dicts の代わりに gb_trees を使用するのはどのような場合でしょうか？これは明確な決定ではありません。私が作成した ベンチマークモジュール で示すように、gb_trees と dicts は多くの点でやや似たパフォーマンスを示します。しかし、ベンチマークは、dicts が最高の読み取り速度を持ち、gb_trees は他の操作で少し速くなる傾向があることを示しています。どちらが最適かは、自分のニーズに基づいて判断できます。

また、dicts には fold 関数がありますが、gb_trees にはありません。代わりにイテレータ関数があり、そこから木の断片を返して、gb_trees:next(Iterator) を呼び出すと、順序に従って次の値を取得できます。つまり、汎用的な fold を使用するのではなく、gb_trees の上で独自の再帰関数を作成する必要があるということです。一方、gb_trees を使用すると、gb_trees:smallest/1 と gb_trees:largest/1 を使用して、構造体の最小要素と最大要素にすばやくアクセスできます。

したがって、キーバリューストアのどちらを選択するかは、アプリケーションのニーズによって決定されるべきだと私は考えています。保存するデータの量、それで何をしたいかなどのさまざまな要因すべてが重要になります。測定、プロファイル、ベンチマークを実行して、確認してください。

配列

では、数値キーのみを持つデータ構造を必要とするコードについてはどうでしょうか？その場合、配列があります。これにより、数値インデックスを使用して要素にアクセスし、未定義のスロットを無視しながら構造全体を反復処理できます。

集合の集合

数学の授業で集合論を学んだことがあるなら、集合が何ができるかについての考えがあるでしょう。そうでない場合は、これをスキップしたいかもしれません。ただし、集合は比較や操作ができる一意な要素のグループにすぎないと言っておきます。2つのグループにある要素、どちらにもない要素、一方だけにある要素などを調べることができます。より高度な操作では、関係を定義してこれらの関係を操作したり、さらに多くのことができます。理論に深く立ち入るつもりはないので（これもこの本の範囲外です）、それらを現状のまま説明するだけです。

Erlang で集合を扱うための主要なモジュールは4つあります。最初は少し奇妙に見えるかもしれませんが、セットを構築するための「最良」の方法がないことに実装者が同意したことに気づくと、より意味を成します。4つのモジュールは、ordsets、sets、gb_sets、sofs（集合の集合）です。

ordsets

Ordsets はソートされたリストとして実装されています。それらは主に小さな集合に役立ち、最も遅い種類の集合ですが、すべての集合の中で最も単純で読みやすい表現を持っています。それらには、ordsets:new/0, ordsets:is_element/2, ordsets:add_element/2, ordsets:del_element/2, ordsets:union/1, ordsets:intersection/1 のような標準関数があります。他にもたくさんあります。

sets

Sets（モジュール）は、dict で使用されている構造と非常によく似た構造の上に実装されています。それらは ordsets と同じインターフェースを実装していますが、より優れたスケールを実現します。辞書と同様に、特定の要素がセットの一部であるかどうかを確認するなど、読み取り負荷の高い操作に特に適しています。

gb_sets

Gb_sets 自体は、gb_trees モジュールで使用されているものと同様の一般平衡木構造の上に構築されています。gb_sets は、dict に対する gb_tree のようなもので、読み取り以外の操作を考慮した場合に高速になり、より多くの制御が可能になる実装です。gb_sets は sets および ordsets と同じインターフェースを実装していますが、より多くの関数も追加しています。gb_trees と同様に、スマート関数とナイーブ関数、イテレータ、最小値と最大値へのクイックアクセスなどがあります。

sofs

集合の集合（sofs）は、いくつかのメタデータを持つタプル内に格納されたソートされたリストを使用して実装されています。セット間の関係、ファミリを完全に制御したり、セットタイプを強制したりする場合に使用するモジュールです。これらは、「単なる」一意な要素のグループではなく、数学的な概念が必要な場合に本当に必要なものです。

多くのオプションが用意されているのは少し混乱を招くかもしれません。Erlang/OTPチームのBjörn Gustavsson氏（ErlangによるWings3Dのプログラマー）は、ほとんどの場合gb_setsを使用し、独自コードで処理したい明確な表現が必要な場合はordsetを使用し、=:=演算子が必要な場合は'sets'を使用することを主に推奨しています（ソース）。

いずれにせよ、キーバリューストアと同様に、最適な解決策は通常、ベンチマークを実行して、アプリケーションに最も適したものを見つけることです。

有向グラフ

ここで言及しておきたいデータ構造がもう1つあります（この章で言及されているもの以外にも多くあるわけではありませんが、反対にあります）。それは有向グラフです。繰り返しになりますが、このデータ構造は、それに関連する数学的理論をすでに知っている読者向けです。

Erlangにおける有向グラフは、digraphとdigraph_utilsという2つのモジュールとして実装されています。digraphモジュールは基本的に、有向グラフの構築と変更を可能にします。つまり、エッジと頂点の操作、パスとサイクルの検索などです。一方、digraph_utilsを使用すると、グラフを（後順、先行順で）ナビゲートしたり、サイクル、樹状構造、または木をテストしたり、隣接ノードを見つけたりすることができます。

有向グラフは集合論と密接な関係があるため、'sofs'モジュールには、ファミリーを有向グラフに変換したり、有向グラフをファミリーに変換したりできるいくつかの関数が含まれています。

キュー

queueモジュールは、両端FIFO（First In, First Out）キューを実装します。

これらは、上記で説明したように少し実装されています。つまり、要素を高速に追加および先頭に追加できる2つのリスト（このコンテキストでは、スタック）です。

queueモジュールには、基本的に、複雑さが異なる3つのインターフェース（またはAPI）に精神的に分離されたさまざまな関数があります。これらは「オリジナルAPI」、「拡張API」、「岡崎API」と呼ばれます。

オリジナルAPI

オリジナルAPIには、キューの概念の基本となる関数が含まれています。たとえば、空のキューを作成するnew/0、新しい要素を挿入するin/2、要素を削除するout/1、およびリストへの変換、キューの反転、特定の値がキューの一部であるかどうかの確認などの関数が含まれます。

拡張API

拡張APIは、主にいくつかのイントロスペクション機能と柔軟性を追加します。最初の要素を削除せずにキューの先頭を調べたり（get/1またはpeek/1を参照）、要素を気にせずに削除したり（drop/1）できます。これらの関数はキューの概念にとって不可欠ではありませんが、一般的に役立ちます。

岡崎API

岡崎APIは少し奇妙です。これは、Chris OkasakiのPurely Functional Data Structuresに由来します。このAPIは、以前の2つのAPIで利用可能だったものと同様の操作を提供しますが、関数名の一部が逆方向に書かれており、全体的に奇妙です。このAPIが必要だと確信がない限り、気にしないでください。

一般に、最初に順序付けられた項目が最初に処理されることを確認する必要がある場合は、キューを使用します。これまで、私が示した例では、主にリストを後で反転されるアキュムレータとして使用していました。一度にすべての反転を行うことができず、要素が頻繁に追加される場合は、queueモジュールが必要になります（まずテストと測定を行う必要があります。常にテストと測定を行ってください！）。

短い訪問の終わり

Erlangのデータ構造の旅は以上です。最後まで車両の中に腕を置いておいていただきありがとうございます。もちろん、さまざまな問題を解決するために利用できるデータ構造は他にもあります。ここでは、Erlangの一般的なユースケースの強みを考えると、遭遇したり、最も必要になる可能性の高いものだけを取り上げました。詳細については、標準ライブラリと拡張ライブラリも探索することをお勧めします。

これが、シーケンシャル（関数型）Erlangへの旅を完了したことを知って喜んでいただけるかもしれません。多くの人が、Erlangが輝いている並行性とプロセスなどを見ようとしてErlangを使い始めていることを知っています。それは理解できます。スーパービジョントリ―、高度なエラー管理、分散など。これらのテーマについて書くのを非常に待ちきれなかったし、読者の中にも、それらについて読むのを非常に待ちきれなかった人がいると思います。

ただし、並行Erlangに進む前に、関数型Erlangに慣れておくことが理にかなっていると判断しました。そうすることで、後で進みやすくなり、すべての新しい概念に集中できます。さあ、始めましょう！

• < 前へ
• 目次
• 次へ >

特に明記されていない限り、このサイトのコンテンツは、クリエイティブ・コモンズ表示非営利改変禁止ライセンスの下でライセンスされています。