This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] Re: Sets and home-made ordered types
• Damien Guichard
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Damien Guichard Subject: [Caml-list] Re: Sets and home-made ordered types
Hi Matthias,

I guess what you actually need is not a weird set datatype but some memoized function of type t -> t.

What i propose is the following code :

type t = F of t | G of t * t | A | B

let top_most () =
let f = ref None and g = ref None in
fun x ->
match x with
| F _ -> (match !f with None -> f := Some x; x | Some y -> y)
| G _ -> (match !g with None -> g := Some x; x | Some y -> y)
| A -> A
| B -> B

Then top_most () gives you a function with the expected behavior.

Hope it helps,

- damien

Damien Guichard
2009-09-17

En réponse au message
de : Matthias Puech
du : 2009-09-16 23:38:43
À : caml-list@yquem.inria.fr
CC :
Sujet : Re: [Caml-list] Sets and home-made ordered types

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.

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

It seems to me rather natural to have it: otherwise, what's the point of
being able to provide your own compare, beside just checking for
membership of the class? The implementation of the function is
straightforward: just copy mem and  make it return the element in case
of success:

let rec find x = function
Empty - > raise Not_found
| Node(l, v, r, _) - >
let c = Ord.compare x v in
if c = 0 then v else
find x (if c  < 0 then l else r)

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

Here is what I want to do: Given a purely first-order datastructure,
let's say:
type t = F of t | G of t * t | A | B
I want to index values of type t according to their first constructor.
So in my set structure, there will be at most one term starting with
each constructor, and:
find (F(A)) (add (F(B)) empty) will return F(B)

With a Set.find, it's easy:

let compare x y = match x,y with
| (F,F | G,G | A,A | B,B) - > 0
| _ - > Pervasives.compare x y

module S = Set.Make ...

With the Map solution, i'm obliged to define:

type cstr = F' | G' | A' | B'
let cstr_of x = F _ - > F' | G _ - > G' etc.

and then make a Map : cstr |-- > t, which duplicates the occurrence of
the constructor (F' in the key, F in the element). Besides, I'm
responsible for making sure that the pair e.g. (G', F(A)) is not added.