RE: [Caml-list] Efficient and canonical set representation?

["Fred Smith" <fsmith@mathworks.com>]

Ocaml has a structural comparison function (<=) : 'a -> 'a -> bool.  

But the bigger problem with this approach (as Jean-Baptiste Rouquier) kindly pointed out to me is that insertion takes O(n), not O(log(n)) time. Duh.

-Fred


> -----Original Message-----
> From: owner-caml-list@pauillac.inria.fr 
> [mailto:owner-caml-list@pauillac.inria.fr] On Behalf Of Samuel Lacas
> Sent: Friday, November 07, 2003 10:44 AM
> To: caml-list@inria.fr
> Subject: Re: [Caml-list] Efficient and canonical set representation?
> 
> 
> Fred Smith a écrit 2.2K le Fri, Nov 07, 2003 at 10:27:25AM -0500: # 
> # I guess what you're looking for are sorted arrays:
> #   1) O(log n) lookup and insertion via binary search
> #   2) O(n) union and intersection are simple
> #   3) Equal sets are represented by structurally equivalent objects.
> # 
> # -Fred
> 
> Hmm, except that, if I'm not wrong, it was required the 
> structure to hold any kind of object. Sorted arrays require 
> the elements to be sortable. Using the hash of the objects 
> may be an answer ?
> 
> sL
> 
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: 
http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners