分123この章ではリストから一歩進み,永続データとして利用できる木構造を説明します。木構造の例として赤黒木という平衡二分探索木を取り上げ,ハッシュテーブル(以下,ハッシュと略記)を実装します。関数プログラミングと(C言語などで使われる)配列は相性が良くありません。配列を永続データとして使おうとすると,一部を変更するだけでも配列全体をコピーしなければならないからです。いうことは,関数プログラミングでは,必要に応じて平均O(1)(注1)で要素を追加したり検索したりできるハッシュがないことを意味します(注2⁠)⁠。キーと値の組を要素に持つリスト(連想リスト:型は[(k,v)])を使えば,要素の追加や検索は可能ですが,効率がO(N)となりうれしくありません。N)の平衡木を使います。この章では,赤黒木という平衡二分探索木を使ってハッシュを実現します。注1)Oはアルゴリズムの効率を表す表記です。N),O(N2)となります。注2)初期化のみで更新しなくてよいのであれば,平均O(1)のハッシュが作れます。木構造は永続データとして利用できます。左の探索木に要素oを挿入すると,左の木を破壊することなく,右側の新しい木が作られていることがわかります。このように,木に要素を加えたり削除したりする場合,新たに作られるノードは,探索に使われたパス上のもののみです。10000)で平均13ノードとなります。Collection)によって回収されます。木構造を使えば,集合,ハッシュ,ヒープ,キュー,両端キュー,操作効率の良い巨大な文字列などを実現できます。これらは通常ライブラリとして整備されているので,単に使うだけなら中身を知る必要はありません。Interface)を理解するだけで大丈夫です。ハッシュのAPIこれから赤黒木を用いてハッシュを実装します。そのAPIを示します。キーの型がkで,値のほうがvになります。型変数が2つ出てくると最初はわかりにくいかもしれませんが,連想リストの型[(k,v)]と同等の意味です。empty─⁠─空のハッシュemptyは空のハッシュを表します。emptyはO(1)です。insert─⁠─要素を追加するinsertは,キーと値の組をハッシュに登録し,新しいハッシュを返します。=>というのは,任意のkではだめで,「⁠順序付けられる性質を持つk」という意味です。IntやCharは順序付けられますが,関数は順序付けられません。赤黒木は探索木なので,キーを順序付ける必要があります。実装していませんが,理解しやすいように使用例を示します。実際に試す場合は,のちほど作成するtree.hsを読み込んでください。Leaf返ってくる値は赤黒木のリテラル表現ですが,ここではまだ理解する必要はありません。木の内部に,加えたキーと値があることがわかれば十分です。このハッシュは永続データですから,たとえば2回要素を加える場合は,insertが返したハッシュにさらにinsertする必要があります。Leaf)fromList─⁠─要素をまとめて登録する上記の例のようにinsertを何回も使うのは面倒なので,連想リストをハッシュに変換する関数fromListも実装します。Leaf)search─⁠─要素を検索するハッシュを検索するには関数searchを使います。hashNothingハッシュにキーが格納されている場合は「Just値」が返り,そうでない場合はNothingが返ってきています。