top page > computer > haskell > web_lecture > for_programmer > nsc_map.html
更新日:
文責: 重城良国

Nano Scheme: Map型

(工事中 30%)

リストを使った辞書

ペアのリストによる辞書はPrelude.lookupで検索する。

% ghci
Prelude> lookup 8 [(3, 5), (8, 2)]
Just 2

要素をはじめから順に調べていく。要素数に比例した時間がかかる。時間効率はO(n)だ。

Map型

Data.Mapという標準的なモジュールがある。これによる辞書の検索はO(log n)だ。O(log n)はO(1)とO(n)のあいだではあるが中間ではない。対数時間は実用的には定数時間に近い。

Prelude> :m Data.Map
Prelude Data.Map> empty
fromList []
Prelude Data.Map> insert 3 "hello" it
fromList [(3,"hello")]
Prelude Data.Map> insert 15 "world" it
fromList [(3,"hello"),(15,"world")]
Prelude Data.Map> insert 8 "good-bye" it
fromList [(3,"hello"),(8,"good-bye"),(15,"world")]
Prelude Data.Map> let d = it
Prelude Data.Map> Data.Map.lookup 8 d
Just "good-bye"
Prelude Data.Map> Data.Map.lookup 10 d
Nothing

空の辞書にinsertでkeyとvalueとを追加した。fromList [...]は関数showによるMapの文字列表現だ。Data.Mapモジュールの関数lookupはPreludeのlookupと名前がかぶるのでモジュール名をつけた「修飾名」とした。

関数fromListによっていっきに作ることもできる。

Prelude Data.Map> fromList [(3, "hello"), (15, "world"), (8, "good-bye")]
fromList [(3,"hello"),(8,"good-bye"),(15,"world")]

fromList [...]という表現はshowによる文字列表現だ。中身は二分木だ。

中身

詳しくは説明しない。Map型はkey-valueペアの二分木だ。検索、挿入、更新、削除がO(log n)でできる。重み平衡木というアルゴリズムを使っている。挿入や削除のときに木の形を調整し、左右の木の大きさをだいたい同じくらいに保つ。時間効率はO(log n)に保たれる。

まとめ

Map型の使いかたを学んだ。本格的なコードでは辞書にペアのリストではなくMap型を使う。Map型には重み平衡木というアルゴリズムが使われている。巧妙で面白いので機会があれば説明する。Map型はきれいなインターフェースを持っているので中身を意識しなくても使える。

アルゴリズム: 重み平衡木 (工事中 40%)

「Nano Scheme: Maybe型の演算」へもどる 「Nano Scheme: 整数値」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics