Re: new library modules (sets and maps)

[remy@research.att.com (Didier Remy)]

Of  course, the typechecker cannot tell  whether you are using two different
orderings on the same map. If you pack the ordering with the primitives in a
record, you could also associate a stamp to the package (each timem you pass
a different  ordering) which  you be  used to  mark all sets created by this
package.   Then  you could  dynamically  check  whether  two  sets sets  are
originated from the same package.  Except that you cannot generate stamps in
a purely applicative style!

Using an object oriented style, you could consider the functions on  sets as
methods, and pack them with each set (instead of the stamp).  The primitives
then take just call the  right methods from the set they  operate  on, which
prevent from  using  two  differnt ordering on the same set.  In fact it  is
enough to pack only the ordering "method".

The interface would still be:

        type 'a t;;

        type 'a ordering == 'a -> 'a -> int;;

        type ('a, 'b) set_operations =
          { empty: 'a t;
            is_empty: 'a t -> bool;
            mem: 'a -> 'a t -> bool;
            add: 'a -> 'a t -> 'a t;
            iter: ('a -> 'b) -> 'a t -> unit;
            (* and so on *) };;

        value make: 'a ordering -> ('a, 'b) set_operations;;

but the implementation of 'a t is now

         type 'a t = {ordering : 'a -> 'a -> 'int;
                      val : 'a old_t};;

and  the  implementation of the functions would changed accordingly  to take
the ordering from their argument rather than from their closure.  Of course,
there is an ambiguity for functions working on  several sets.  The functions
could be written to work with  two orderings, one for each set, but this may
complicate their implementation  or slower their execution, for a  situation
that should not arise in practice...

    Didier.