From mboxrd@z Thu Jan  1 00:00:00 1970
Received: by pauillac.inria.fr; Tue, 29 Mar 94 13:57:08 +0200
Received: from margaux.inria.fr by pauillac.inria.fr; Mon, 28 Mar 94 23:51:16 +0200
Received: from concorde.inria.fr by margaux.inria.fr, Mon, 28 Mar 94 23:51:13 +0200
Received: from Tamuz.Stanford.EDU (Tamuz.Stanford.EDU [36.28.0.48]) by concorde.inria.fr (8.6.8/8.6.6) with SMTP id XAA23422 for <caml-list@margaux.inria.fr>; Mon, 28 Mar 1994 23:51:09 +0200
Received:  by Tamuz.Stanford.EDU (5.61/25-theory-eef) id AA23982; Mon, 28 Mar 94 13:50:36 -0800
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)
Cc: caml-list@margaux.inria.fr, dujardin@naima.inria.fr
In-Reply-To: <199403281237.AA12519@naima.inria.fr> from "Eric Dujardin" at Mar 28, 94 02:37:54 pm
Content-Type: text/plain
Sender: weis@pauillac.inria.fr

> 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