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

["Damien Guichard" <alphablock@orange.fr>]

[-- Attachment #1: Type: text/plain, Size: 3325 bytes --]

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.

Thanks for your answer anyway!

-- Matthias


_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

[-- Attachment #2: Type: text/html, Size: 10026 bytes --]