From: Xavier Leroy <xavier@Theory.Stanford.EDU>
Message-Id: <9403282150.AA23982@Tamuz.Stanford.EDU>
Subject: Re: using sets
To: Eric.Dujardin@inria.fr (Eric Dujardin)
Date: Mon, 28 Mar 1994 13:50:35 -0800 (PST)
In-Reply-To: <199403281237.AA12519@naima.inria.fr> from "Eric Dujardin" at Mar 28, 94 02:37:54 pm
> it seems that a "magic" function, that would for example take any
> reference as parameter and return an integer, would be more
> efficient. However, I have no idea how it could be written...
The obvious choice would be to use the memory address of the cell
representing the reference, but this does not work with a copying
garbage collector such as Caml Light's, where the address of a cell
may change during garbage collection. Similar problems arise in
connection with structured input-output (output_value and
input_value).
> I could add an explicit "Identifier" field to my "Noeud"
> instances,
Yes, that's a good trick. I use it all the time. Basically, you would
define your Lien type as
type Lien =
{ stamp: int;
mutable A_lien: Noeud;
mutable B_lien: Noeud }
and always create values of type Lien through the following function:
let stamp_counter = ref 0;;
let new_lien a b =
incr stamp_counter;
{ stamp = !stamp_counter; A_lien = a; B_lien = b };;
Then, a total order over these objects is
let order_lien l1 l2 = l1.stamp - l2.stamp;;
The stamp also comes handy for printing the data structure during
debugging.
- Xavier Leroy