木構造を使えば、集合、ハッシュ、ヒープ、キュー、両端キュー、操作効率の良い巨大な文字列などを実現できます。これらは通常ライブラリとして整備されているので、単に使うだけなら中身を知る必要はありません。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は順序付けられますが、関数は順序付けられません。赤黒木は探索木なので、キーを順序付ける必要があります。
turnB :: Hash k v -> Hash k v
turnB (Node c l (k,v) r) = Node B l (k,v) r
insert :: Ord k => (k,v) -> Hash k v -> Hash k v
insert (k,v) t = turnB (insert' k v t)
insert'の定義は次のようになります。
insert' :: Ord k => k -> v -> Hash k v -> Hash k v
insert' kx vx Leaf = Node R Leaf (kx,vx) Leaf
insert' kx vx (Node c l (k,v) r) = case compare kx k of
-- 左部分木に挿入してバランスを回復
LT -> balance c (insert' kx vx l) (k,v) r
-- 右部分木に挿入してバランスを回復
GT -> balance c l (k,v) (insert' kx vx r)
-- 元のノードをそのまま返す
EQ -> Node c l (k,v) r
balance :: Color -> Hash k v -> (k,v) -> Hash k v -> Hash k v
-- 場合1
balance B (Node R (Node R a x b) y c) z d =
Node R (Node B a x b) y (Node B c z d)
-- 場合2
balance B (Node R a x (Node R b y c)) z d =
Node R (Node B a x b) y (Node B c z d)
-- 場合3
balance B a x (Node R b y (Node R c z d)) =
Node R (Node B a x b) y (Node B c z d)
-- 場合4
balance B a x (Node R (Node R b y c) z d) =
Node R (Node B a x b) y (Node B c z d)
-- それ以外
balance c a x b = Node c a x b
insert'' :: Ord k => Hash k v -> (k, v) -> Hash k v
insert'' t kv = insert kv t
fromList :: Ord k => [(k,v)] -> Hash k v
fromList = foldl insert'' empty
search :: Ord k => k -> Hash k v -> Maybe v
search kx Leaf = Nothing
search kx (Node c l (k,v) r) = case compare kx k of
LT -> search kx l
GT -> search kx r
EQ -> Just v
