この章ではリストから一歩進み、永続データとして利用できる木構造を説明します。木構造の例として赤黒木という平衡二分探索木を取り上げ、ハッシュテーブル(以下、ハッシュと略記)を実装します。 ハッシュを実現できる木構造 関数プログラミングと(C言語などで使われる)配列は相性が良くありません。なぜなら、配列を永続データとして使おうとすると、一部を変更するだけでも配列全体をコピーしなければならないからです。ということは、関数プログラミングでは、必要に応じて平均O(1)[1]で要素を追加したり検索したりできるハッシュがないことを意味します[2]。 もちろん、キーと値の組を要素に持つリスト(連想リスト:型は[(k,v)])を使えば、要素の追加や検索は可能ですが、効率がO(N)となりうれしくありません。そこで、関数プログラミングではハッシュの実現にO(log N)の平衡木を使います。この章では、赤黒木と