[入門]関数プログラミング―質の高いコードをすばやく直感的に書ける!

第4章 木構造とハッシュ―平衡二分探索木「赤黒木」で知る豊かなデータ型

この記事を読むのに必要な時間:およそ 5 分

insertの実装

赤黒木へ要素を追加するには次のようにします。

  • 新しい要素は赤いノードとして,根から下に向かって挿入する。赤を挿入するので,不変条件2は守られる
  • 新しい赤いノードが黒と黒の間に収まれば問題ない。しかし,赤の下に収まった場合,赤が連続し,不変条件3が満たせなくなる。そこで,不変条件2と不変条件3を満たすように,上に向かってバランスを取りながら戻る
  • バランスを取った結果,最終的に根が赤になって,不変条件1が満たされないことがある。そこで,根を黒にして不変条件1を満たす。黒ノードが増えるのは根に限る。根で黒が増えた場合は,すべてのパスで黒の数が1増えることになる

ここでは,insertを補助関数insert'を使って定義しました。turnBは,無条件に根を黒に変える関数です。

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

葉にたどり着いた場合は,赤いノードを作成しています。

対象がノードの場合を扱うコードに,caseという新しい構文が出てきました。caseは,パターンマッチのための構文です。caseとofの間の計算結果であるデータに対して,⁠パターン -> 本体」を列挙します。

つまり,対象がノードの場合,新しい要素のキーとノードのキーを比較します。同じであれば,元のノードをそのまま返します(新しい値に置き換える仕様でもかまいません⁠⁠。小さければ左の部分木に,大きければ右の部分木に要素を挿入します。この様子を図3に示します。

図3 赤いノードが挿入される様子:赤黒木に5を挿入する

図3 赤いノードが挿入される様子:赤黒木に5を挿入する

新しい赤いノードを挿入したら,次にバランスを取ります。バランスを取る関数balanceは次のようになります。

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

balanceの引数の意味は,⁠色」⁠左の木」⁠キーと値の組」⁠右の木」です。このコードを理解するために,図4を見てください。連続した赤に対して,黒を挟むことによって,不変条件3を満たすことがわかります。パスに対する黒の数も変化していませんから,不変条件2も守られます。この図が入れ子になったパターンマッチのおかげで,直感的に実現できています。これが豊かな型と,その表裏一体の機能であるパターンマッチの力です。

図4 バランスの回復

図4 バランスの回復

バランスが回復される様子を図5に示します。

図5 バランスが回復される様子

図5 バランスが回復される様子

※矢印は関数呼び出しから戻ることを表す

fromListの実装

fromListは,foldlと前に作成したinsertを使えば実装できます。foldlが要求する型に合わせるために,補助関数insert''も定義しています。

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の実装

searchの実装は簡単です。もし,葉にたどり着いてしまった場合は,そのキーは格納されていないことになりますので,Nothingを返します。

ノードを対象にしている場合,検索キーとノードのキーを比較します。小さければ,左の木を再帰的に検索します。大きければ,右の木を再帰的に検索します。等しければ,それをJustでくるんで返します。

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

命令的な実装との比較

赤黒木のinsertを命令プログラミングで実装するとどうなるでしょうか? ⁠アルゴリズムイントロダクション 改訂2 版 第1 巻 数学的基礎とデータ構造』注4の第13章3節に,入門的な実装が載っています。その方法は,場合分けが6通りあり,ポインタの再代入とあいまって,とてもわかりにくいと感じるでしょう。興味があれば,この章で紹介した関数的な実装と比較してみてください注5⁠。

注5)
Thomas H. Cormen/Charles E. Leiserson/Ronald L. Rivest/Clifford Stein著,浅野哲夫/岩野和生/梅尾博司/山下雅史/和田幸一訳,近代科学社,2007年
注5)
左側の子のみが赤になれるという制約を入れ,高度に最適化すれば,命令的なinsertもコンパクトに実装できることが知られていますが,関数型ほど直感的ではありません。

関数型も命令型と同様の開発手順

これまで書いたコードだけでも,立派なハッシュライブラリになります。まだわからないのは,定義した型や関数を公開/非公開にする方法ぐらいでしょう。⁠関数型では大きなプログラムを作れる気がしない」という感想をときどき耳にしますが,関数型でもこのように関数を定義していき,ライブラリとしてまとめ,あとはライブラリを利用するメインのコードを書くという命令型と同様の作業になるので,けっして難しくはありません。

著者プロフィール

山本和彦(やまもとかずひこ)

株式会社IIJイノベーションインスティテュート(IIJ-II)技術研究所 主幹研究員。

開発した代表的なオープンソフトにMew,Firemacs,Mightyがある。『プログラミングHaskell』や『Haskellによる並列・並行プログラミング』の翻訳者。職場ではHaskell,家庭では3人の子供と格闘する日々を送っている。

web:http://www.mew.org/~kazu/

twitter:@kazu_yamamoto