Re: polymorphic equality and overloading

[John R Harrison <johnh@ichips.intel.com>]

Eijiro Sumii writes:

| But as you know (and as I wrote in my previous messages), the
| polymorphic equality in Caml is not at all the "equality in
| mathematics" for many (or most?) datatypes.

Probably "most" is an exaggeration. But there are quite a few examples.
One I haven't seen mentioned in this thread is the type of floating point
numbers. The equality relation defined in the main standard for binary
floating point arithmetic (IEEE 754) is not reflexive. Specifically x = x
is false if x is a NaN ("not a number"). So again, this is really an
instance of overloading in CAML:

  #let x = 0.0 /. 0.0;;
  x : float = nan.0
  #x = x;;
  - : bool = false
  #x == x;;
  - : bool = true

Nevertheless, I find the CAML polymorphic equality and orderings pretty
useful and superficially simple, even if they sometimes have a touch of
arbitrariness about them.

Is it possible using just equality, not orderings, to write a set-compare
operation on polymorphic lists using fewer than 0(n^2) operations?
Trivially, using orderings, one can just sort both lists in O(n log n)
operations then run along them in order. Is there something comparably
efficient just using equality?

John.