効率的なプログラムを書くには,その処理に適したデータ構造を利用しなければなりません。これまでは,リストや配列といった組み込みのデータ型を主に扱ってきました。しかし,処理によってはリストや配列の代わりに「キュー(queue,待ち行列とも呼ぶ)」や「両端キュー(double-ended queue,deque,デック)」といった,並び(sequence,シーケンス)を表現するデータ構造のほうが向いていることもあります。

 今回は,キューを表現する「Seq型」を紹介します。Seq型は,containersパッケージのData.Sequenceモジュールで提供されています。

リストでキューを表現してみる

 Haskellでどのようにすればキューを表現できるか考えてみましょう。

 この連載の第14回でTVar型を使ったメッセージ・キューの実装について紹介したのを覚えているでしょうか。このときは「先頭のポインタと,データを追加するための末尾のポインタを保持する」という方法でキューを定義しました。通常の命令型言語でよく使われる方法です。しかし,これだと「TVar型への読み書き」というまさに大域的な副作用を起こす操作を使うため,IOモナドやSTMモナドといった副作用を利用するモナドの外側ではキューを利用できません。キューをHaskellプログラムのどこでも使えるようにするには,純粋関数を使ってキューを操作する別の表現が必要になります。

 では,リストをキューとして使えないでしょうか? 残念ながら,そのままではあまり現実的ではありません。リストは,先頭の要素を定数時間(「O(1)」と表現します)で取り出せます。しかし末尾に要素を追加するには,リストを先頭から最後まで逐次的にたどっていく必要があるため,リストの大きさに比例した線形時間(すなわち「O(n)」)が必要になります。リストをそのままキューとして利用するのは,処理のコストが高すぎて不適切なのです。

 そこで,キューを以下のようなリストの組で表現する方法がよく使われます。

type Queue a = ([a], [a])

empty = ([], [])
isEmpty (xs, _) = null xs
cons x (ys, zs) = valid (ys, x:zs)
head (x:xs, _) = x
tail (x:xs, ys) = valid (xs,ys)

valid (xs, ys) = if null xs then (reverse ys, []) else (xs, ys)

 headで前方のリストから要素を取り出し,consで後方のリストに要素を追加しています。「要素を取り出す前方のリスト」と「要素を追加する後方のリスト」を別々に用意し,二つのリストを組としてとじ合わせることでキューを表現しているのです。こうすることで,キューへの要素の追加とキューからの要素の取出しの両方を「リストの先頭に対する定数時間の操作」として実現できます。

 要素の追加と取り出しといった単純な演算を行うだけなら,このような「キューをリストの組として表現する方法」で十分です。しかし,単なるキューではなく両端キューの機能を実現したり,キューの連結や任意の個所での分割といった操作を行いたい場合には,この方法だけでは効率の良い実装にはなりません。リストには「必ず先頭から順に要素をたどっていく」という制約があるため,リストをそのまま利用してキューを実装すると,リストの内部では要素を先頭から順にたどらなければならないからです。

 より多くの操作を持つ汎用的なキューには,もう少し複雑なデータ構造である木構造が適しています。木構造を採用すれば,例えばキュー同士を連結する「append」を,リストの内部をたどることなく実現できます。木構造の中分岐の単位で処理を行うことで,キューを任意の個所で分割する「splitAt」やキューの大きさを調べる「length」といった操作も効率的に実装できます。