Pervasives.compareしてはいけない型 (2): Set.S.t, Map.S.t, Big_int.big_int

Pervasives.compare というか、 = で比較できない、あるいはしても意味がない型について。
OCaml 3.10.0 (Cygwin) にてテスト。

Set.S.t

Set.S.compare を使いましょう。

Pervasives.compareで比較すると、集合として正しく比較できません。

module IntSet = Set.Make(struct type t = int let compare = compare end);;

let a = IntSet.add 1 (IntSet.singleton 0) in
let b = IntSet.add 0 (IntSet.singleton 1) in
Printf.printf
  "Pervasives.compare: %d\nSet.S.compare: %d\n"
  (Pervasives.compare a b)
  (IntSet.compare a b)

このコードで、aとbは共に0と1の二要素からなる集合ですが、Pervasives.compareで比較すると等しくなりません。

Pervasives.compare: -1
Set.S.compare: 0

Set.S.tは内部ではbalanced binary treesで実装されていて(/usr/local/lib/ocaml/set.ml)、追加順序が異なると木構造が違うものになり、Pervasive.compareで比較すると一致しないためだと思います。

Map.S.t

Set.S.t 同様、Pervasives.compare で比較すると、マップとして正しく比較できません。

module IntMap = Map.Make(struct type t = int let compare = compare end);;
let a = IntMap.add 1 0 (IntMap.add 0 0 IntMap.empty) in
let b = IntMap.add 0 0 (IntMap.add 1 0 IntMap.empty) in
Printf.printf
  "Pervasives.compare: %d\n"
  (Pervasives.compare a b)

Pervasives.compare: -1

Map.S.compare が無いので自分で書けと?

Big_int.big_int

Big_int.compare_big_int を使いましょう。

Pervasives.compareで比較すると、この前書いたように落ちます。