Sets and homemade ordered types

Matthias Puech
 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:   (:) 
From:  Matthias Puech <puech@c...> 
Subject:  Re: [Camllist] Sets and homemade 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 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. Thanks for your answer anyway!  Matthias