Blogに続いて入門記事を書いてみます。前回はバイナリを作ったので今回はライブラリを作ります。題材は(非平衡)二分木。非平衡なのは平衡にすると複雑になるのと、平衡にするときは別のネタ(依存型)があるのでそれまでとっておくためです。対象読者は前回の数当てゲームのチュートリアルを終えた人に設定します。今回のコード全体像はこちらにあります。以下のような構成でディレクトリを作りましょう。BTree.idrbtree.ipkgには以下を書きます。今から二分木を実装していきます。二分木とは二分木はデータ構造です。値の保持、検索、削除ができるので集合やKey-Valueストアの実装に使われます。手続き型言語ではそれらの実装にハッシュセットやハッシュマップがよく使われますが、関数型言語では二分木の方がよく使われるようです。二分木はノード(節)とリーフ(葉)からなります。リーフは何もデータを持ちません。ノードは1つの値と2つ(左右)の子(部分木)を持ちます。ノードには「ノードの左の子に保持されている全ての値よりもノードの保持している値の方が大きい。ノードの右の子に保持されている全ての値よりも値の方が小さい。」という条件が成つように作ります。5がノードに保持されている値です。上にあるノード(ここでは3を保持しているノード)を根と呼びます。「ノードの左の子に保持されている全ての値よりもノードの保持している値の方が大きい。ノードの右の子に保持されている全ての値よりも値の方が小さい。」という条件もちゃんと成り立っています。今回は非平衡二分木なので条件はここまでです。平衡二分木だとここからさらに「左右が大体同じくらいの高さ」という条件が付きます。二分木への操作まずは検索と挿入を説明しましょう。検索は二分探索をそのまま行えます。5を保持している木に2が含まれるか検索してみましょう。2は3より小さいので、あるとしたら左の子にあるはずです。右の子は3より大きい値しか保持していないので絶対ありません。左の子を見てみましょう。左の子は1を保持しています。2は1より大きいのであるとしたら右の子にあるはずです。右の子をみてましょう。右の子は2を保持しています。検索している値が見つかったのでこの木に2が含まれることが分かります。同様の検索をして、葉に行き当たったら検索している値はなかったということが分かります。挿入も検索と似たようなことをします。先程の木に6という値を挿入してみましょう。6は3より大きいので右の子を見ます。右の子を見ると6は4より大きいのでさらに右の子を見ます。6は5より大きいので更に右の子を見ます。右の子はリーフなのでこの木には6がいないことが分かりました。新しいノードを作ります。新しいノードを作ります。新しいノードを作ります。新しいノードを作ります。これで更新が完了しました。更新というよりは挿入する値も保持した新しい木を作る操作ですね。Idrisは純粋関数型言語なので破壊的変更ができません。更新ではなく新しい値を作ることになります。いったときに部分構造を共有できる二分木は無駄が少なく、効率的なデータ構造になるのです。更新したあとも古い値が使える、データが順に保持される、などのおまけ付きです。二分木の実装さて、座学はこのくらいにして実装していきましょう。データ型の定義まずはデータ構造の定義です。二分木とはリーフ、または2つの子と値を持ったノードからなるのでした。BTree.idrに以下を実装します。a)これはデータ型の定義です。型の値を保持するBTreeという意味です。ジェネリクスになってますね。