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

RE: [Caml-list] Efficient and canonical set representation?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-11-07 (15:27) From: Fred Smith Subject: RE: [Caml-list] Efficient and canonical set representation?
```
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

> -----Original Message-----
> From: owner-caml-list@pauillac.inria.fr
> [mailto:owner-caml-list@pauillac.inria.fr] On Behalf Of
> Harrison, John R
> Sent: Friday, November 07, 2003 9:16 AM
> To: erayo@cs.bilkent.edu.tr; caml-list@inria.fr
> Cc: Harrison, John R
> Subject: RE: [Caml-list] Efficient and canonical set representation?
>
>
> | You basically want O(1) for set equality, I suppose.
>
> Actually, no --- perhaps I should have made clearer what I
> *really* want. The efficiency of comparison wasn't my
> motivation, but rather elegance and aesthetics. And I meant
> "canonical" with respect to ordinary structural equality, not
> necessarily pointer equality, so the problem is potentially a
> bit easier than you might have thought.
>
> I want to be able to treat an abstract type in a truly
> abstract way, and not worry about special-purpose equality
> relations on certain types. Otherwise it's an ugly mess
> dealing with complicated nestings like sets of pairs of lists of sets.
>
> Now, I think the right solution, conceptually speaking, is to
> allow user-defined equality on abstract types. But as far as
> I know this cannot be done in OCaml, and I've never met much
> enthusiasm for the idea among the CAML or SML experts.
>
> So a poor second best is to define abstract types in a canonical way,
> which was the starting-point of my question.
>
> After your remarks and Brian's, I'm starting to wonder if it
> is possible at all to do what I want. Maybe I should be
> looking for an impossibility proof instead...
>
> John.
>
> -------------------
> 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

```