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

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

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

型の定義

Maybeという新しい型が出てきましたので,ここではいったんハッシュの実装をお休みし,型について説明します。

列挙型

Haskellで最も簡単な型は真理値Boolです。次のように定義されています。

data Bool = False | True

Haskellで新しい型を定義する際は,dataというキーワードを使います。Boolのような列挙型では,=の右側に値を|で区切って列挙します。この値のことを構成子と呼びます。型と構成子は大文字で始める必要があります。

列挙型の例として,順序を表す型Orderingも見てみましょう。

data Ordering = LT | EQ | GT

LT,EQ,GTは,それぞれ「より小さい」⁠等しい」⁠より大きい」を表します。第3章で出てきたcompareは,実はこのOrderingを返します。

> compare 1 2
LT

型変数を取る型

前節で出てきたMaybeは次のように定義されています。

data Maybe a = Nothing | Just a

Maybeは型変数を取る型です。まだ型変数に親しみが湧かない方は,aを具体的な型,たとえばCharに置き換えてみてください。

-- 以下は疑似コード
data Maybe Char = Nothing | Just Char

Maybeは,ある型に失敗する可能性を付加するための型です。Nothingが失敗を,Justが成功を表します。たとえば先述の「search」では,要素が格納されていないときにNothing,格納されているときにJust 'a'が返ってきていました。

重要なのできちんと区別していただきたいのですが,Charは失敗しない型,Maybe Charは失敗するかもしれない型です。一般的に関数型言語では,型を見れば失敗する可能性があるのかがわかります。そして,そういった関数を使った場合は,⁠パターンマッチを使って)失敗も処理しないと,コンパイラが警告を発します。

一方,命令型にはほかの型に紛れ込めるnull(nil,None)が存在します。型を見ただけでは,関数が失敗する可能性があるのかわかりません。このため,nullの処理を忘れて,実行時にnullを踏んでしまうことがたびたび起こります。nullの発明者であり,チューリング賞を受賞したTony Hoare氏は,⁠nullは10億ドルの失敗」と後悔しているようです。

構造体

実はMaybeは,列挙型と構造体が混合されていた例になっていました。少しわかりにくかったかもしれませんので,ここでは簡単な構造体を定義してみます。

data Pair = MkPair Int Char

構造体Pairは,型IntとCharを格納する型で,構成子はMkPairになります。実は,型と構成子の名前空間は分かれているので,同じ名前にしてもかまいません。また,格納する型を抽象化して,型変数にすることもできます。

data Pair k v = Pair k v

再帰型

構造体では,構成子のあとに型を書きました。ここに自分自身の型を書けば再帰型になります。次はIntを格納する二分木の例です。

data Tree = Leaf | Node Tree Int Tree

Leafと Nodeが構成子,Nodeの右にあるTreeとIntは型です。

赤黒木を実装しよう

赤黒木とは

赤黒木の説明に戻りましょう。赤黒木とは,各ノードが赤か黒に塗られた二分木です(本当はリンクに色が付くのですが,ノードに色を付けて説明することが多いようです⁠⁠。終端を表す葉は,黒として扱われます。図2に赤黒木の例を示します。

図2 赤黒木の例

図2 赤黒木の例

※丸がノードで,三角が葉を表す。黒が黒,白が赤を意味する。
ノードにはキーとなる整数のみを表示している

二分木が赤黒木として成り立つためには,次の不変条件を満たさなければなりません。

  • 不変条件1:(図2で最上部にある)根は黒である
  • 不変条件2:根から葉に至るすべてのパスで,黒の数が同じ
  • 不変条件3:赤は連続してはならない

図2では,根は黒で,(図中では白)は連続しておらず,すべてのパスで葉も含めた黒の数が3になっています。

不変条件から中間ノードが最も少ない葉(浅い葉)は,そこに至るパス上のノードがすべて黒だとわかります。また,中間ノードが最も多い葉(深い葉)は,そこに至るパス上で,黒と黒の間すべてに赤が挟まっている場合になります。図2では,ノード1が最も浅く深さ2,ノード6が最も深く深さ4です。このように,最も浅い部分と最も深い部分の差が高々2倍であるという意味でバランス(平衡)しています。

赤黒木の定義

赤黒木の定義には,まず赤と黒の色が必要です。これをColorという名前の型で定義しましょう。これ以降,すべてファイルtree.hsに書き込むようにしてください注3⁠。

data Color = R | B deriving Show

Rが赤,Bが黒を表します。deriving Showは,対話環境でこのまま表示してくれるようにするおまじないです(前述のBool,Maybe,Orderingなどにも,実際はこのおまじないが付けられています⁠⁠。Hash k vは木構造なので,再帰的に定義します。

data Hash k v = Leaf -- 葉は黒
              | Node Color (Hash k v) (k,v) (Hash k v)
              deriving Show

Haskellでは,このようにインデントされた行は継続行として扱われますので,このコードは1行に書いたのと同じ意味になります。emptyはLeafで表現できますので,定義は次のようになります。

empty :: Hash k v
empty = Leaf
注3)
WEB+DB PRESS Vol.67サポートサイトで完成したtree.hsを公開しています。

著者プロフィール

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

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

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

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

twitter:@kazu_yamamoto