PR

様々な型のキーを利用できるMap型

 Haskellでは,木を使った辞書用のデータ型として,Data.MapモジュールにMap型が用意されています。Map型の定義を見てみましょう。

data Map k a  = Tip 
              | Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a) 
type Size     = Int

 Tipは末端(leaf)である節を表すのに使います。MapがTipデータ構成子しか持たない場合には,Tipは空の木になります。

-- | /O(1)/. The empty map.
--
-- > empty      == fromList []
-- > size empty == 0

empty :: Map k a
empty 
  = Tip

 Binは,2分探索木(binary search tree)の分岐(branch)である節を表すのに使います。Binは,「分岐以下の木の大きさ(左部分木の大きさをl,右部分木の大きさrとした場合,l+r+1)であるSize」「k型のラベル」「キーを使って参照するa型の要素」の三つを保持します。木の大きさを表現するのにInt型を直接用いるのでなく,Sizeという別名を付けているのは,このフィールドが木の大きさの情報を保持していることを明示するためです。

 BinとTipを組み合わせることで木を構成できます。例えば,Binの左右にTipを直接持たせることで,1個の要素を持つ木を作成できます。1個の要素を持つ木を作成するsingleton関数の定義は以下の通りです。

-- | /O(1)/. A map with a single element.
--
-- > singleton 1 'a'        == fromList [(1, 'a')]
-- > size (singleton 1 'a') == 1

singleton :: k -> a -> Map k a
singleton k x  
  = Bin 1 k x Tip Tip

 1個の要素を持つ木の大きさは1なので,BinのSizeには1が格納されます。

 Map型を実際に使ってみましょう。キーを使ってMap型に保持されている要素を参照するには,lookup関数を使います。

Prelude Data.Map> :t Data.Map.lookup
Data.Map.lookup :: (Ord k) => k -> Map k a -> Maybe a

 lookup関数は,与えられたキーとBinデータ構成子のラベルを比較して要素の検索を行います。キーに一致するラベルがMap型の内部に存在する場合,lookup関数はそのラベルが存在するBinデータ構成子に格納されている要素をJustに包んで返します。キーに一致するラベルがMap型の内部に存在しない場合には,Nothingを返します。

Prelude Data.Map> Data.Map.lookup 4 $ singleton 4 "d"
Just "d"
Prelude Data.Map> Data.Map.lookup 5 $ singleton 4 "d"
Nothing
Prelude Data.Map> Data.Map.lookup 5 $ empty
Nothing
Prelude Data.Map> Data.Map.lookup "d" $ singleton "d" 4
Just 4
Prelude Data.Map> Data.Map.lookup "e" $ singleton "d" 4
Nothing
Prelude Data.Map> Data.Map.lookup ("d", True) $ singleton ("d", True) 4
Just 4
Prelude Data.Map> Data.Map.lookup ("d", True) $ singleton ("d", False) 4
Nothing

 こうした例やlookup関数の型からわかるように,Map型ではOrdクラスのインスタンスである型なら何でもキーとして利用できます。

 Map型を辞書として利用するには,キーと要素を追加したり削除したりする操作も必要です。Map型に新たなキーと要素を追加するにはinsert関数,キーに対応する要素を削除するにはdelete関数を使用します。それぞれの関数の型は以下の通りです。

Prelude Data.Map> :t insert
insert :: (Ord k) => k -> a -> Map k a -> Map k a
Prelude Data.Map> :t delete
delete :: (Ord k) => k -> Map k a -> Map k a

 実際にinsertとdeleteを使ってみましょう。

Prelude Data.Map> insert 4 "d" empty
fromList [(4,"d")]
Prelude Data.Map> insert 5 "e" $ singleton 4 "d"
fromList [(4,"d"),(5,"e")]
Prelude Data.Map> delete 4 $ singleton 4 "d"
fromList []
Prelude Data.Map> let t = insert 5 "e" $ singleton 4 "d"
Prelude Data.Map> delete 4 t
fromList [(5,"e")]
Prelude Data.Map> insert 3 "c" $ t
fromList [(3,"c"),(4,"d"),(5,"e")]

 プロンプト上では結果が連想リストの形で表現されるので,少しわかりにくいかもしれません。そこで,Map型の中身を木の形で出力するshowTree関数を利用します。

Prelude Data.Map> :t showTree
showTree :: (Show k, Show a) => Map k a -> String

 showTreeは,Map型を文字列に変換します。ただし,showTreeの結果をプロンプトに直接出力すると,改行文字である"\n"がそのまま出力されてしまいます。

Prelude Data.Map> showTree $ insert 5 "e" $ singleton 4 "d"
"4:=\"d\"\n+--|\n+--5:=\"e\"\n"

 そこで,文字列を出力する関数であるputStrで出力を行うことにします。

 では,showTreeとputStrを使って,insertとdeleteを使用した結果を表示してみましょう。

Prelude Data.Map> let showTree' t = putStr $ showTree t
Prelude Data.Map> showTree' empty
|
Prelude Data.Map> showTree' $ insert 4 "d" empty
4:="d"
Prelude Data.Map> showTree' $ singleton 4 "d"
4:="d"
Prelude Data.Map> showTree' $ insert 5 "e" $ singleton 4 "d"
4:="d"
+--|
+--5:="e"
Prelude Data.Map> showTree' $ delete 4 $ singleton 4 "d"
|
Prelude Data.Map> let t = insert 5 "e" $ singleton 4 "d"
Prelude Data.Map> showTree' $ delete 4 t
5:="e"
Prelude Data.Map> showTree' $ insert 3 "c" t
4:="d"
+--3:="c"
+--5:="e"

 showTree関数の出力では,Tipデータ構成子の節を「|」,Binデータ構成子の節を「ラベル:=要素」,部分木を「+--」で表現しています。この出力結果から,insert関数がMap型にキーと要素を追加していることや,delete関数がキーに対応する要素を削除していることがわかります。

 ちなみに,showTree関数では結果は決まった形式で出力されますが,showTreeWith関数を使えば出力をカスタマイズできます。

Prelude Data.Map> :t showTreeWith
showTreeWith
  :: (k -> a -> String) -> Bool -> Bool -> Map k a -> String

 showTreeWithでは,第1引数でラベルと要素を持つ節の表示方法,第2引数で木構造の出力形式,第3引数で木の節と節の間にスペースを空けるかどうかを指定します。

Prelude Data.Map> let showElem k x  = show k ++ ":=" ++ show x
Prelude Data.Map> let showTree'' t = putStr $ showTreeWith showElem True False t
Prelude Data.Map> showTree'' $ insert 3 "c" t
4:="d"
+--3:="c"
+--5:="e"
Prelude Data.Map> let showTree''' t = putStr $ showTreeWith showElem True True t
Prelude Data.Map> showTree''' $ insert 3 "c" t
4:="d"
|
+--3:="c"
|
+--5:="e"
Prelude Data.Map> let showTree'''' t = putStr $ showTreeWith showElem False True t
Prelude Data.Map> showTree'''' $ insert 3 "c" t
+--5:="e"
|
4:="d"
|
+--3:="c"

 第1引数にshowElem,第2引数にTrue,第3引数にFalseを与えたshowTree''では,showTree関数と同じ出力結果になります。実際に,showTree関数はshowTreeWith関数を使用して以下のように定義されています。

-- | /O(n)/. Show the tree that implements the map. The tree is shown
-- in a compressed, hanging format. See 'showTreeWith'.
showTree :: (Show k,Show a) => Map k a -> String
showTree m
  = showTreeWith showElem True False m
  where
    showElem k x  = show k ++ ":=" ++ show x

 第2引数にTrueを与えたshowTree''とshowTree'''では,親の木に部分木がぶらさがる形で木構造が表示されます。一方,第2引数にFalseを与えたshowTree''''では,木を右に倒した形で木構造が表示されます。木を右に倒しているので,左部分木は分岐の下,右部分木は分岐の上に表示されます。

 第3引数にFalseを与えたshowTree''では,節と節の間が詰まった形で表示されています。一方,第3引数にTrueを与えたshowTree'''とshowTree''''では,節と節の間が空いた形で表示されています。

 このように,showTreeWithを使うことで,Map型が構成する木構造の表示をカスタマイズできます。