Re: new library modules

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

Guy Cousineau writes:
> The sets that you  propose are not only totally ordered sets
> but rather totally pre-ordered  and I think that it is indeed important
> for  many applications.  It is very often the case that you have
> to deal with a set of complex objects  a part which is used for
> the pre-order relation.

This sounds intriguing. Can you give an example or two? So far, the
sets I've used were either over base types (integers, strings), or
over complex objects represented as records with an integer "stamp"
field to identify them in a unique way, in which case two objects with
the same stamps were by definition the same object.

> Why not let us have access directly to your balanced trees package?

Well, actually, I don't have a general balanced tree package, the modules
"set" and "map" have their own balanced tree type. This makes for a
more compact representation of maps, but is probably a poor design.

What would the interface of a general balanced tree package look like?
Any suggestions?

> Rather than using type "int" for comparison, it would be clearer
> to use an explicit type  comparison= Smaller | Equiv | Greater.

I agree that using "int" is much less clear. The reasons I can give
are: 1- I don't know where to define the type "comparison" in the
standard library; 2- we get efficient comparison functions for
integers (prefix -) and for strings (compare_string, which is a
primitive). Both reasons are pretty lame, and I can be convinced
otherwise.

While I'm sending a message to the mailing list, here are some more
feedback I got:

Damien Doligez writes:
> Pour les sets et les maps, pourquoi est-ce que tu ne mets pas l'ordre et
> l'ensemble dans un record (ou un type abstrait quelconque), ce qui
> eliminerait le bug du mec qui passe la mauvaise fonction en argument ?

I guess you mean (in the case of "set"):

        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;;

And to work with integer sets, one would do:

        let intset = set__make (fun i j -> i-j);;

        ... intset.empty ... intset.mem ... intset.add ...

This is more elegant than parameterizing each operation by the
ordering, but still not foolproof: if we do

        let intset2 = set__make (fun i j -> j-i);;
then
        intset2.mem 2 (intset.add 1 (intset.add 2 intset.empty));;

is well-typed, though incorrect. We need structures and functors to do
this properly; ordinary functions and records are not enough...

Any opinion?

Christophe Raffali writes:
> Is it impossible to use an internal order invisible for the user to represent
> the type "'a set" ? perhaps in another library "set" (with no
> specified order)? This order could be constructed like the equality ?

Yes, it's easy to turn the generic equality primitive into a generic
ordering primitive. The problem is: just as with equality, you won't
get the relation you really want. For instance, sets will be compared by
structure rather than by contents, so you won't be able to do sets of
sets. We Bourbaki fans all want to do that. This does not work either
with my stamped objects: generic ordering will insist on comparing all
fields of the object, possibly looping, while all is needed is to
compare the stamp fields.

We can also settle for this solution, claiming that this behavior is
no worse than, e.g., list__assoc or hashtbl__find, and that the
problem will be solved when we figure out how to attach nonstructural
equality/comparison functions to specific types.

- Xavier Leroy