Re: using sets

[Xavier Leroy <xavier@Theory.Stanford.EDU>]

> 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