Sets and homemade ordered types

Matthias Puech

Matthias Puech
 Vincent Aravantinos
 David Allsopp
 Goswin von Brederlow

Matthias Puech
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20090923 (10:46) 
From:  Goswin von Brederlow <goswinvb@w...> 
Subject:  Re: [Camllist] Sets and homemade ordered types 
Matthias Puech <puech@cs.unibo.it> writes: > 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. If your key is part of the value then you could use the value itself as key. You still get a key and a value but they would point to the same object in memory. >> 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 firstorder 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. Don't define a cstr but use the t as key and value. You still need to make sure (A, B) isn't added but you can trivialy wrap the Map module with functions like let add m x = Map.add m x x that hide the duplication of key and value. The problem I see with your approach though is that you can't find m (F) but must use find m (F(A)) You need a dummy value for F to create a F key. Idealy I think type prefixes could solve your problem. But ocaml doesn't have them. MfG Goswin