Map型を操作する関数の実装を知る
では，Map型の定義やMap型を操作する関数の定義を詳しく見ていきましょう。こうした定義を詳しく知ることには，二つの意義があります。
一つ目の意義は，関数型言語ならではの定義を知ることができることです。Haskellを学んだり，Haskellを使って実用的なプログラムを書いたりする中で，Haskellを使って様々なデータ構造を書きたくなることがあります。しかし，アルゴリズムとデータ構造に関する文献の大半は，C言語やJavaのような命令型言語を使って実装することを想定したものです。Haskellを使って書かれたデータ構造の定義を知ることは，こうした文献の内容とHaskellとの間のギャップを埋め，Haskellを使ってデータ構造を自作する手助けになります。
二つ目の意義は，Map型というデータ構造が実際にどんな特性を持っているかを理解できることです。単純にMap型を利用するだけなら，Map型の特性を理解する必要はありません。しかし，プログラムの実行効率を最適化する場合には，細部への理解が重要になります。Map型では，参照のコストを下げるため，左右の部分木の大きさを揃える平衡化という操作を行っています。平衡化には様々な方法があります。辞書を使うプログラムの性質によっては，Map型が採用している手法とは別の手法で平衡化を行うほうが適しているかもしれません。例えば，Map型の代わりにAVL木を定義したライブラリを使ったほうがいい場合もあります。性能の問題をいち早く見つけ出し，より適したデータ構造を選択，もしくは自作するには，Map型の実装を深く理解する必要があります。
では，Map型の定義をもう一度見てみましょう。
data Map k a = Tip
| Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a) Binデータ構成子のaを除く各フィールドに，正格性注釈が付いています。したがって，要素aを除く，木の大きさであるSize，キーであるk，左右の部分木である（Map k a）は，すべて正格に評価されます。
このことは，Map型を使った木の再構成には遅延評価が用いられないことを意味します。つまり，insertによる要素の追加やdeleteによる要素の削除が行われた場合には，その時点ですぐに木が再構成されます。この特徴は，木を平衡化することでlookupを使った参照コストを下げるのに役立ちます。
それでは，キーを使ってMap型の要素を参照するlookup関数の定義を見てみましょう。
lookup :: Ord k => k -> Map k a -> Maybe a
lookup k t
= case t of
Tip -> Nothing
Bin _ kx x l r
-> case compare k kx of
LT -> lookup k l
GT -> lookup k r
EQ -> Just x lookup関数が引数として取るキーであり，Map型が使用するラベルであるk型には，Ordクラスのインスタンスという文脈が与えられています。したがってlookup関数は，Ordクラスのインスタンスを通して定義された「k型の値の間の順序関係」を利用して木を探索することになります。
比較演算を使って順序関係を決めるcompareメソッドはOrdクラスで提供されています。
class (Eq a) => Ord a where
compare :: a -> a -> Ordering
～ 略 ～
-- Using compare can be more efficient for complex types.
compare x y
| x == y = EQ
| x <= y = LT
| otherwise = GT
～ 略 ～
data Ordering = LT | EQ | GT
deriving (Eq, Ord, Enum, Read, Show, Bounded)デフォルト定義からわかるように，compareメソッドは1番目の引数と2番目の引数の値が等しければEQ（equal），1番目の引数よりも2番目の引数のほうが大きければLT（less than），1番目の引数のほうが2番目の引数よりも大きければGT（greater than）を返します（参考リンク1，参考リンク2）。
compareメソッドの意味をふまえてlookup関数の定義を詳しく見ていきましょう。lookup関数の定義では，対象が空の木（Tip）である場合にはNothingを返すようになっています。それ以外の場合，lookup関数の第1引数として与えられたキーが節のラベルよりも小さい場合には左部分木，キーがラベルよりも大きい場合には右部分木を再帰的に探索します。キーとラベルが等しい場合には要素をJustに包んで返し，キーと等しいラベルが見つからないままTipにたどりついた場合にはNothingを返します。
Map型に要素を追加するinsert関数の定義は以下の通りです。
-- | /O(log n)/. Insert a new key and value in the map.
-- If the key is already present in the map, the associated value is
-- replaced with the supplied value. 'insert' is equivalent to
-- @'insertWith' 'const'@.
--
-- > insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]
-- > insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]
-- > insert 5 'x' empty == singleton 5 'x'
insert :: Ord k => k -> a -> Map k a -> Map k a
insert kx x t
= case t of
Tip -> singleton kx x
Bin sz ky y l r
-> case compare kx ky of
LT -> balance ky y (insert kx x l) r
GT -> balance ky y l (insert kx x r)
EQ -> Bin sz kx x l r要素を追加する木が空である場合には，singletonが呼ばれて大きさが1の木が作られます。木が空でない場合には，追加する要素のキーが節のラベルよりも小さい場合には左側の部分木，大きい場合には右側の部分木を再帰的にたどります。キーと同じラベルを持つ節が見つかれば，その節が格納する要素を更新します。最後までキーと同じラベルを持つ節が見つからなければ，singleton関数で要素を追加します。
このように，insert関数は要素を追加するだけではなく，キーと同じラベルを持つ節が存在する場合には要素を更新します。Data.Mapモジュールには要素を更新するためのupdate関数なども用意されていますが，ここでは説明を省略します。気になる方は自分で調べてみてください（参考リンク）。
木に要素を追加する際には注意すべき点があります。insert関数の定義を見てみればわかりますが，小さい順あるいは大きい順などに整列された形で木に要素を追加していくと，左右の部分木の一方だけに分岐が続く偏った構造になります。一方向の分岐が多いと，木の形がリストに近づきます。リストに近い構造になれば，木に対する参照などの個々の操作に，木の大きさに比例した線形時間に近いコストがかかるようになってしまいます。
こうした事態を防ぐには，木に要素を追加したり削除したりするときに，木が偏った構造にならないよう工夫する必要があります。こうした役割を担っているのが，insert関数の再帰呼び出しの際に呼ばれているbalance関数です。balanceは木を平衡化します。
balance :: k -> a -> Map k a -> Map k a -> Map k a
balance k x l r
| sizeL + sizeR <= 1 = Bin sizeX k x l r
| sizeR >= delta*sizeL = rotateL k x l r
| sizeL >= delta*sizeR = rotateR k x l r
| otherwise = Bin sizeX k x l r
where
sizeL = size l
sizeR = size r
sizeX = sizeL + sizeR + 1delta,ratio :: Int delta = 5 ratio = 2
balanceは，左部分木と右部分木の大きさの合計が1よりも大きく，左部分木と右部分木の大きさの差がdelta変数を使って指定した閾値を超える場合，木を平衡化するために節の位置を回転（rotate）します。
言葉だけで説明してもわかりにくいので，例を挙げましょう。1と2をラベルとして持つ木があったとします。
Prelude Data.Map> let t = insert 2 () $ singleton 1 () Prelude Data.Map> showTree'''' t +--2:=() | 1:=() | +--|
この木にinsert関数を使って3というラベルの節を加えると，右部分木が大きくなります。
+--3:=0 | +--2:=() | | | +--| | 1:=() | +--|
Tipの大きさは0です。したがって右部分木の大きさが0，左部分木の大きさが2になります。
-- > size empty == 0
-- > size (singleton 1 'a') == 1
-- > size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
size :: Map k a -> Int
size t
= case t of
Tip -> 0
Bin sz _ _ _ _ -> sz左部分木の大きさが右部分木よりも5倍以上大きいので，rotateRを使った回転が行われます。結果は以下のようになります。
Prelude Data.Map> let t' = insert 3 () $ t Prelude Data.Map> showTree'''' t' +--3:=() | 2:=() | +--1:=()
節の位置が一つずつ右側に移動し，その結果，左部分木と右部分木の大きさはそれぞれ1になります。
同様に，1から6までのラベルを持つ木に，insert関数を使って7というラベルの節を加えた場合にも回転が行われます。
+--7:=()
|
+--6:=()
| |
| +--5:=()
|
+--4:=()
| |
| +--3:=()
|
2:=()
|
+--1:=()この木では4というラベルを持つ節が左部分木を抱えているため，大小関係が正しくなるように，平衡化前の左部分木を移動します。
Prelude Data.Map> let t'' = insert 4 () $ t' Prelude Data.Map> let t''' = insert 5 () $ t'' Prelude Data.Map> let t'''' = insert 6 () $ t''' Prelude Data.Map> let t''''' = insert 7 () $ t'''' Prelude Data.Map> showTree'''' t''''' +--7:=() | +--6:=() | | | +--5:=() | 4:=() | | +--3:=() | | +--2:=() | +--1:=()
これが木の平衡化させるための回転です。
実際には，右側が大きいか左側が大きいかによって回転する向きを変える必要があるので，回転にはrotateLとrotateRの2種類が用意されています。
ただし，左部分木よりも右部分木が大きいときに「右部分木の左部分木」が「右部分木の右部分木」よりも大きくなったり，右部分木よりも左部分木のほうが大きいときに「左部分木の右部分木」が「左部分木の左部分木」よりも大きくなったりしている場合には，1度の回転や同じ回転の再帰的な繰り返しでは木を平衡化できません。
例を見てみましょう。1と3をラベルとして持つ木があったとします。
Prelude Data.Map> showTree'''' $ insert 3 () $ singleton 1 () +--3:=() | 1:=() | +--|
この木にinsert関数を使って2というラベルの節を加えると，左部分木および「左部分木の右部分木」が大きくなります。
+--| | +--3:=() | | | +--2:=() | 1:=() | +--|
この部分木に対して先ほどと同様の回転を行うと，平衡化されずに，今度は右部分木が左部分木よりも大きくなってしまいます。
+--| | 3:=() | | +--2:=() | | +--1:=0 | +--|
そこで，rotateLやrotateRの内部では，「部分木の部分木」の大きさをbalanceの中で用いていたのとは別の閾値で検査し，単純回転（single rotate）を行うか2重回転（double rotate）を行うかを決めています。
-- rotate rotateL :: a -> b -> Map a b -> Map a b -> Map a b rotateL k x l r@(Bin _ _ _ ly ry) | size ly < ratio*size ry = singleL k x l r | otherwise = doubleL k x l r rotateL _ _ _ Tip = error "rotateL Tip"
rotateR :: a -> b -> Map a b -> Map a b -> Map a b rotateR k x l@(Bin _ _ _ ly ry) r | size ry < ratio*size ly = singleR k x l r | otherwise = doubleR k x l r rotateR _ _ Tip _ = error "rotateR Tip"
単純回転と2重回転の例として，rotateLの実装に使われているsingleLとdoubleLの定義を見てみましょう。
-- basic rotations singleL, singleR :: a -> b -> Map a b -> Map a b -> Map a b singleL k1 x1 t1 (Bin _ k2 x2 t2 t3) = bin k2 x2 (bin k1 x1 t1 t2) t3 singleL _ _ _ Tip = error "singleL Tip" ～ 略 ～ doubleL, doubleR :: a -> b -> Map a b -> Map a b -> Map a b doubleL k1 x1 t1 (Bin _ k2 x2 (Bin _ k3 x3 t2 t3) t4) = bin k3 x3 (bin k1 x1 t1 t2) (bin k2 x2 t3 t4) doubleL _ _ _ _ = error "doubleL"
木を再構成するために使われているbinは，木を構成するために必要な知識を含んだスマート構成子（smart constructor）です。Haskellでデータ型を作成する際には，新しい型を構成するのに必要な型を決めるだけで，その型の値については何も決めません。このため，適切な値を作成できるように，型を作成するのに必要な知識を含んだ便利な補助関数をあらかじめ定義し，データ構成子の代わりに使うことがよくあります。型を作成するのに必要な知識を持ったこのような関数のことを「賢い」構成子，すなわちスマート構成子と呼びます（参考リンク）。
{--------------------------------------------------------------------
The bin constructor maintains the size of the tree
--------------------------------------------------------------------}
bin :: k -> a -> Map k a -> Map k a -> Map k a
bin k x l r
= Bin (size l + size r + 1) k x l rbinには，「木の大きさは左右の部分木に分岐自身を加えたもの（size l + size r + 1）である」という，Bin型の定義には書かれていない制約が含まれているのがわかります。
singleLとdoubleLはいずれも，節の要素を右部分木に移して木を再構成しています。両者の違いは，singleLが左部分木の節の要素を中央の節に持ってくるのに対し，doubleLでは「右部分木の左部分木」の要素を中央の節に持ってくる点です。この違いにより，singleLでは平衡化できない「右部分木の左部分木が右部分木の右部分木よりも大きくなった構造」をdoubleLは平衡化できます。
例を見てみましょう。
+--| | +--3:=() | | | +--2:=() | 1:=() | +--|
1というラベルを持つ節の「左部分木の右部分木」には，2というラベルを持つ節があります。この2というラベルを持つ節を中央に持ってくることで，木を平衡化させることができます。
Prelude Data.Map> showTree'''' $ insert 2 () $ insert 3 () $ singleton 1 () +--3:=() | 2:=() | +--1:=()
この二つの図を見比べると，doubleLが行う「右部分木の左部分木の要素を中央の節に持ってくる操作」が「右部分木の節を右回転してから節を左回転する2回の回転操作」になっているのがわかると思います。
このような回転操作によって，木は平衡化されます。balanceはinsertを再帰的に呼び出したあとに呼ばれるため，insertを使って要素を追加した木は平衡化されています。
次に，Map型から要素を削除するdelete関数を見ていきましょう。この関数の定義は以下の通りです。
-- | /O(log n)/. Delete a key and its value from the map. When the key is not
-- a member of the map, the original map is returned.
--
-- > delete 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
-- > delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
-- > delete 5 empty == empty
delete :: Ord k => k -> Map k a -> Map k a
delete k t
= case t of
Tip -> Tip
Bin _ kx x l r
-> case compare k kx of
LT -> balance kx x (delete k l) r
GT -> balance kx x l (delete k r)
EQ -> glue l r要素を削除する木がすでに空である場合には何も行いません。木が空でない場合，要素のキーが節のラベルよりも小さい場合には左側の部分木，大きい場合には右側の部分木を再帰的にたどります。insertと同様に，balanceで木を平衡化しています。キーと同じラベルを持つ節が見つかれば要素を削除し，glue関数を使って残った部分木を連結します。キーと同じラベルを持つ節が見つからなかった場合には何も行いません。
{--------------------------------------------------------------------
[glue l r]: glues two trees together.
Assumes that [l] and [r] are already balanced with respect to each other.
--------------------------------------------------------------------}
glue :: Map k a -> Map k a -> Map k a
glue Tip r = r
glue l Tip = l
glue l r
| size l > size r = let ((km,m),l') = deleteFindMax l in balance km m l' r
| otherwise = let ((km,m),r') = deleteFindMin r in balance km m l r'glueは，連結する木のどちらか一方が空である場合には，単にもう一方をそのまま返します。連結する木がどちらも空でない場合には，二つの木を連結したあとにbalanceを呼び，作成した木を平衡化します。
このようにinsertやdeleteが木を平衡化するため，Map型を使って構成する木は平衡2分探索木（self-balancing binary search tree）になるのです。
Map型に対する参照・追加・更新・削除の操作のコストを考えてみましょう。Map型は2分探索木の一種であるため，参照・更新・追加・削除はいずれも対数時間の処理です。さらに，操作にかかるコストが最悪のケースである線形時間に近づくのを平衡化で防いでいるのです。
