この章ではリストから一歩進み，
ハッシュを実現できる木構造
関数プログラミングと
もちろん，
- 注1）
- Oはアルゴリズムの効率を表す表記です。効率が良い順に，
O(1)， O(log N)， O(N)， O(N log N)， O(N2)となります。 - 注2）
- 初期化のみで更新しなくてよいのであれば，
平均O(1)のハッシュが作れます。
木構造の特徴
木構造は永続データとして利用できます。図1を見てください。左の探索木に要素oを挿入すると，
図1 永続データとしての木構造
木構造を使えば，
ハッシュの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で，
empty──空のハッシュ
emptyは空のハッシュを表します。emptyはO(1)です。
insert──要素を追加する
insertは，Ord k =>というのは，
まだ実装していませんが，
> empty
Leaf
> insert (1,'a') empty
Node B Leaf (1,'a') Leaf
返ってくる値は赤黒木のリテラル表現ですが，
> insert (2,'b') (insert (1,'a') empty)
Node B Leaf (1,'a') (Node R Leaf (2,'b') Leaf)
fromList──要素をまとめて登録する
上記の例のようにinsertを何回も使うのは面倒なので，
> 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
ハッシュにキーが格納されている場合は
