Set の真ん中を取ってくる

Set は binary balanced tree なので、その（おおよそ）真ん中の元を取ってくることが出来れば、バイナリーサーチを書くことが出来るはずだ。Binary tree の一番根元のノードを取ってくるだけなので、簡単なはずなのだが、なぜか、真ん中の元を取ってくる関数は用意されていない! S.choose がそうかと思ったが、なぜか S.min_elt として定義されている…

Set.filter を使って無理やり実装してみた:

module SET = struct
  include Set.Make(O)
  exception Found of elt
  let middle set =
    try
      ignore (exists (fun v -> raise (Found v)) set);
      raise Not_found 
    with
    | Found v -> v
end

この middle と split を使えば、バイナリサーチが書ける。

ファンクターSet.Make自体を拡張したい人は良い演習になるので自分でやってみると良いだろう。

すこし効率は落ちるので、気になる場合は set.ml を自分用にコピーして拡張するしかない。