RE: [Caml-list] Sets and home-made ordered types

["David Allsopp" <dra-news@metastack.com>]

Matthias Puech wrote:
> David Allsopp a écrit :
> > Is it not possible to model your requirement using Map.Make instead -
> > where the keys represent the equivalence classes and the values whatever
> > data you're associating with them?
> 
> Yes, that's exactly the workaround I ended up using, although I'm not
> very happy with it because, among other things, these keys/class
> disciminant get duplicated (once inside the key, once inside the
> element). I'm getting more concrete below.

While I agree that the duplication is unfortunate, it is only one word (the
number needed in each instance to store the Constructor value for the key -
you get the Constructor "for free" with a tuple as it's "stored" in the tag
of the block allocated to hold the tuple.)

> > In terms of a strictly pure implementation of a functional Set, it
> > would be odd to have a "find" function - you'll also get some
interesting
> > undefined behaviour with these sets if you try to operations like union
and
> > intersection but I guess you're already happy with that!

<snip - see other posts>

> For union and inter, I don't see how their behavior would be undefined,
> since neither the datastructure nor the functions are changed.

The element put into the sets on intersection and union is undefined. Say
you have the trivial case with just one equivalence class 

type u = A of int
module MySet = Set.Make(struct type t = u let compare x y = 0 end)

So your sets will all be singletons. What is the result of:

MySet.inter (MySet.singleton (A 1)) (MySet.singleton (A 2))

In 3.11.1, it's the singleton set containing [A 2] but the definition
intersection reasonably allows for it to be [A 1] instead. However, this of
itself isn't an argument against having [find] - it's just that what you're
doing already isn't really a set.

<snip>

> Besides, I'm responsible for making sure that the pair e.g. (G', F(A)) is
not added.

Jacques Garrigue has a syntax extension (PolyMap, I think is its name) which
may help you here - it allows you to enforce this invariant automatically
(and provides neater syntax for it). But I agree that for your case adding a
"find" method to a custom (i.e. copied) version of Set is probably the way
forward - I'm just not sure that you'll convince the guys at Inria to add
the method to the standard library's version of Set.Make!


David