Physical compare

Physical compare

[Tom Hawkins]

Is their a version of "compare" that is based on physical equality?  If 
not, how can I define one?  I tried:

let compareq a b = if a == b then 0 else if a > b then 1 else (-1)

But unfortunately, (>) is a structural comparison.

I need to make a Map where the keys are distinguished by the physical 
instance.

Thanks!

-Tom

Re: [Caml-list] Physical compare

[Jon Harrop]

On Wednesday 23 November 2005 19:20, Tom Hawkins wrote:
> Is their a version of "compare" that is based on physical equality?  If
> not, how can I define one?

Due to the use of a copying collector you cannot define one because the 
pointers that make up references can change value, i.e. a < b might not 
remain true for very long.

> I need to make a Map where the keys are distinguished by the physical
> instance.

Tag every key with a unique integer using something like this:

module Tag : sig
  type 'a t
  val make : 'a -> 'a t
  val compare : 'a t -> 'a t -> int
end = struct
  type 'a t = int * 'a
  let i = ref 0
  let make x =
    incr i;
    !i, x
  let compare (a, _) (b, _) = compare a b
end;;

Then use the Tag.compare function to perform physical comparison with a total 
ordering.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Physical compare

[Nicolas Cannasse]

Tom Hawkins wrote:
> Is their a version of "compare" that is based on physical equality?  If 
> not, how can I define one?  I tried:
> 
> let compareq a b = if a == b then 0 else if a > b then 1 else (-1)
> 
> But unfortunately, (>) is a structural comparison.
> 
> I need to make a Map where the keys are distinguished by the physical 
> instance.
> 
> Thanks!
> 
> -Tom

It's not possible.

One of the reason is that the GC might move your memory addresses around 
and then break your Map constitency. You need to attribute an unique id 
to each of your items and use it for comparison.

Nicolas

Re: [Caml-list] Physical compare

[Jean-Christophe Filliatre]

Hello,

Tom Hawkins writes:
 > Is their a version of "compare" that is based on physical equality?  If 
 > not, how can I define one?  I tried:
 > 
 > let compareq a b = if a == b then 0 else if a > b then 1 else (-1)
 > 
 > But unfortunately, (>) is a structural comparison.
 > 
 > I need to make a Map where the keys are distinguished by the physical 
 > instance.

Others already  gave the right answer  i.e. that you need  to tag your
values with unique integers to do that.

Just to  mention it, I wrote  a little hash-consing  library that does
precisely this, together with specialized  versions of Set and Map for
these tagged values  (based on Patricia trees). There  is even a short
article describing the technique. All is available on this page:

http://www.lri.fr/~filliatr/software.en.html

Hope this helps,
-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)