Erlang の queue モジュールを一通り試す - 準備

キューを扱いたかったので queue モジュールを学ぶ。

引数が間違った型の場合、たとえば、キュー引数がキューではなく、インデックスが整数ではなく、リスト引数がリストではない場合、すべての関数はbadargで失敗する。 不適切なリストは内部クラッシュを引き起こす。 キューの範囲外のインデックスも、badargで失敗する。

いくつかの関数は、空のキューで失敗する。

実行時間はO(n)であるfilter/2, join/2, len/1, member/2, split/2 を除いて、すべての関数はO(1)である。

キュー操作によって構築されるガーベッジの量を最小限に抑えるため、キューのサイズを最小限にする。そのため、キューには明示的に長さ情報が含まれておらずlen/1がO(n)になる。

この特定の操作がのパフォーマンスを向上させることが重要な場合、ユーザは簡単に長さを追跡することができる。

キューはダブルエンド(double-ended)である。キューのイメージは、順番を待っている人（や物）の列である。キューの前は、最も長く待機したアイテムのエンドである。キューの後は、アイテムが待機を開始するときに入るエンドである。

前から入り、後ろから出るのはキューの逆の操作である。

このモジュールには、"Original API" と "Extended API" と "Okasaki API" の3つのインターフェース関数のセットがある。

"Original API" と "Extended API" はどちらも、アイテムの待機列のイメージを使う。両方とも"_r"という接尾辞が付いた逆の操作がある。

"Original API" のアイテム削除関数は、削除されたアイテムと結果のキューの両方を含む複合語を返す。

"Extended API"には、ガベージを削減する代替関数と、キューの終了を検査するための関数が含まれてる。

また、"Okasaki API" 関数はガーベッジを少なくする。

"Okasaki API" は Chris Okasaki による「Purely Functional Data Structures」に触発さされている。これはキューをリストと見なす。