Re: Polymorphic comparison

[John Harrison <John.Harrison@cl.cam.ac.uk>]

Judicael Courant writes:

| I think this polymorphic comparison is quite easy to implement in the
| following way:
|
| #open "hashtbl";;
| let c x y = (hash x) <= (hash y);;
| #infix "c";;

I should have pointed out that I want a true ordering, i.e. something
antisymmetric. (Presumably the above isn't, since several different items might
yield the same hash value). The idea is to be able to sort a list of elements
of any type into an arbitrary but fixed order.

Pierre Weis adds:

| In the next 0.7 version of Caml Light, we plan to extend comparisons to a
| polymorphic function (i.e. prefix < : 'a -> 'a -> bool, instead of the
| now available prefix < : int -> int -> bool).

That would be all I want, I think.

| To extend comparisons to unrelated pairs of values, that is defining
| prefix <  with type scheme 'a -> 'b -> bool seems a bit strange to me.
| What do you plan to do with such a general type scheme for comparisons ?

I don't foresee any use for such a general mechanism, although that's how it
was in Classic ML.

The applications I have in mind are in theorem proving; for example
canonicalizing expression trees based on an associative-commutative operation.
However I can envisage some other uses, e.g. set/multiset comparison. I suspect
that if you can only do pairwise comparison this is O(n^2), whereas just
sorting both sets first then comparing should be O(n log n).

John.