この章ではリストから一歩進み，永続データとして利用できる木構造を説明します。木構造の例として赤黒木という平衡二分探索木を取り上げ，ハッシュテーブル（以下，ハッシュと略記）を実装します。

ハッシュを実現できる木構造

関数プログラミングと（C言語などで使われる）配列は相性が良くありません。なぜなら，配列を永続データとして使おうとすると，一部を変更するだけでも配列全体をコピーしなければならないからです。ということは，関数プログラミングでは，必要に応じて平均O(1)（注1）で要素を追加したり検索したりできるハッシュがないことを意味します（注2⁠）⁠。

もちろん，キーと値の組を要素に持つリスト（連想リスト：型は[(k,v)]）を使えば，要素の追加や検索は可能ですが，効率がO(N)となりうれしくありません。そこで，関数プログラミングではハッシュの実現にO(log N)の平衡木を使います。この章では，赤黒木という平衡二分探索木を使ってハッシュを実現します。

注1）

Oはアルゴリズムの効率を表す表記です。効率が良い順に，O(1)，O(log N)，O(N)，O(N log N)，O(N2)となります。

注2）

初期化のみで更新しなくてよいのであれば，平均O(1)のハッシュが作れます。

木構造の特徴

木構造は永続データとして利用できます。図1を見てください。左の探索木に要素oを挿入すると，左の木を破壊することなく，右側の新しい木が作られていることがわかります。このように，木に要素を加えたり削除したりする場合，新たに作られるノードは，探索に使われたパス上のもののみです。たとえば，10,000個の要素を持つ木がバランスしているとすると，新たに作られるのは単純計算（log2 10000）で平均13ノードとなります。古い木が不要になれば，共有されていないノードは，GC（Garbage Collection）によって回収されます。

木構造を使えば，集合，ハッシュ，ヒープ，キュー，両端キュー，操作効率の良い巨大な文字列などを実現できます。これらは通常ライブラリとして整備されているので，単に使うだけなら中身を知る必要はありません。API（Application Program Interface）を理解するだけで大丈夫です。

ハッシュのAPI

これから赤黒木を用いてハッシュを実装します。まず，そのAPIを示します。

empty :: Hash k v
insert :: Ord k => (k,v) -> Hash k v -> Hash k v
fromList :: Ord k => [(k,v)] -> Hash k v
search :: Ord k => k -> Hash k v -> Maybe v

ハッシュの型はHash k vとします。キーの型がkで，値のほうがvになります。型変数が2つ出てくると最初はわかりにくいかもしれませんが，連想リストの型[(k,v)]と同等の意味です。

empty─⁠─空のハッシュ

emptyは空のハッシュを表します。emptyはO(1)です。

insert─⁠─要素を追加する

insertは，キーと値の組をハッシュに登録し，新しいハッシュを返します。insertはO(log N)です。Ord k =>というのは，任意のkではだめで，「⁠順序付けられる性質を持つk」という意味です。たとえば，IntやCharは順序付けられますが，関数は順序付けられません。赤黒木は探索木なので，キーを順序付ける必要があります。

まだ実装していませんが，理解しやすいように使用例を示します。実際に試す場合は，のちほど作成するtree.hsを読み込んでください。

> empty
Leaf
> insert (1,'a') empty
Node B Leaf (1,'a') Leaf

返ってくる値は赤黒木のリテラル表現ですが，ここではまだ理解する必要はありません。木の内部に，加えたキーと値があることがわかれば十分です。このハッシュは永続データですから，たとえば2回要素を加える場合は，insertが返したハッシュにさらにinsertする必要があります。

> insert (2,'b') (insert (1,'a') empty)
Node B Leaf (1,'a') (Node R Leaf (2,'b') Leaf)

fromList─⁠─要素をまとめて登録する

上記の例のようにinsertを何回も使うのは面倒なので，連想リストをハッシュに変換する関数fromListも実装します。fromListはO(N log N)です。

> fromList [(1,'a'),(2,'b')]
Node B Leaf (1,'a') (Node R Leaf (2,'b') Leaf)

search─⁠─要素を検索する

ハッシュを検索するには関数searchを使います。searchはO(log N)です。

> let hash = fromList [(1,'a'),(2,'b')]
> search 1 hash
Just 'a'
> search 3 hash
Nothing

ハッシュにキーが格納されている場合は「Just値」が返り，そうでない場合はNothingが返ってきています。これらは，searchの戻り値の型であるMaybe vに対応しています。