Re: [Caml-list] equality of Big_ints

[skaller <skaller@users.sourceforge.net>]

On Mon, 2005-10-10 at 00:12 -0400, Ian Zimmerman wrote:
> Is Big_int.eq_big_int the same as polymorphic equality on Big_int.big_int?

No. Polymorphic equality does not work for Big_int.

Example:

let x = Big_int.big_int_of_int 42;;
let y = Big_int.big_int_of_int 42;;

if x = y then print_endline "Equal" else print_endline "Not equal";;

Compile and execute:

skaller@rosella:/work/felix/flx$ ocamlopt nums.cmxa x.ml -o bite
skaller@rosella:/work/felix/flx$ ./bite
Fatal error: exception Invalid_argument("equal: abstract value")

Examining 'custom.h' this just looks like a bug:

struct custom_operations {
  char *identifier;
  void (*finalize)(value v);
  int (*compare)(value v1, value v2);
  long (*hash)(value v);
  void (*serialize)(value v,
                    /*out*/ unsigned long * wsize_32 /*size in bytes*/,
                    /*out*/ unsigned long * wsize_64 /*size in bytes*/);
  unsigned long (*deserialize)(void * dst);
};

So custom blocks can support finalisers, comparators, hashing
and serialisation. Big_int CAN be serialised .. looks like 
the the comparator simply wasn't installed.

For 'nat' I see this:

static struct custom_operations nat_operations = {
  "_nat",
  custom_finalize_default,
  custom_compare_default,
  custom_hash_default,
  serialize_nat,
  deserialize_nat
};

[Nat is the underlying C type used in Big_int]

So, a custom serialiser/deserialiser has been provided,
but the default comparator is left in place (which throws
an exception I guess).

The reason may be because the equality of integers
isn't the same as algebraic equality of the data structures:
for example using signed magnitude minus 0 is not algebraically
equal to plus 0 -- and polymorphic comparison compares the
(ocaml) representations. So even if Nat custom block could
provide a custom comparator that worked correctly, the Big_int
built on it would only work if the representation was canonical,
and the invariant could be expensive to maintain. But it does
not seem like this is so in this case...

For Rationals, however, it could be very much the case that
maintaining the usual invariant (no common divisors of the
numerator and denominator) would be expensive to maintain.

So perhaps this is another case where polymorphic compare
was a 'good idea at the time' but actually fails with abstract
types. It really only works with sums, products, and some primitives,
and fails with functions and general abstract types. The problem
is Ocaml (rather than C) abstractions have no way to provide
the run time with custom operations -- the type information
is lost.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net