Polymorphic comparison

Judicael.Courant@l...
 John Harrison
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  19941018 (12:54) 
From:  John Harrison <John.Harrison@c...> 
Subject:  Re: Polymorphic comparison 
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 associativecommutative 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.