To: caml-list@pauillac.inria.fr
Subject: Re: Polymorphic comparison
In-Reply-To: Your message of "Tue, 18 Oct 94 11:40:09 BST." <9410181040.AA18410@lip.ens-lyon.fr>
Date: Tue, 18 Oct 94 13:54:01 +0100
From: John Harrison <John.Harrison@cl.cam.ac.uk>
Message-Id: <"swan.cl.cam.:256500:941018125425"@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.