using sets

using sets

[Pierre Weis]

Hello,

> type Lien = {A_lien : Noeud ref ; B_lien :Noeud ref };;
> and now I would like to use sets of "Liens".
> I don't know how to define a total order over references

You cannot hope to write such a function, if it reads the contents of the
references, since further assignments to the references can change the
ordering of the references. The only way seems to compare their
adresses independantly of their contents, but due to the gc, these
adresses may change. If the gc changes these adresses consistently with
the ordering, then a piece of magic could be written, otherwise I
don't know how to deal with the problem.

However, the best solution is yours: simply add a field to compare
elements of type Lien!

Pierre Weis

PS: Have you good reasons to use records with fields containing
references, instead of records with mutable fields ? If no, just
remove the refs and add a new field to compare the Lien values: your
Lien data will be more compact than they are now, and you'll have no
more problems to compare them!

Re: using sets

[Xavier Leroy]

> 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

using sets

[Eric Dujardin]

Hello,

I have defined the following type :

type Lien = {A_lien : Noeud ref ; B_lien :Noeud ref };;

and now I would like to use sets of "Liens". The trouble is that I
don't know how to define a total order over references, to create the
set with the "empty" function. I do not want to compare the values of
the "Noeud" instances, as two distinct instances could have the same
value. I could add an explicit "Identifier" field to my "Noeud"
instances, but 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...


Thanks for any help,

Eric