Re: [Caml-list] Map + Set

[Martin Jambon <martin_jambon@emailuser.net>]

On Mon, 26 Jul 2004, Diego Olivier Fernandez Pons wrote:

>     Bonjour,
>
> > I need a functional data structure that has a decent efficiency
> > (i.e. not lists) and can represent `sets of named containers' so
> > that I can find a container in a set, remove it from the set, update
> > it and put it back into the set.
>
> Do you mean the containers will be indexed by a string or a list of
> elements (list of char, list of abstract keys) ? If this is the case
> what you are looking for is a trie (or lexical tree).
>
> There are many Caml implementation available including JCF's and
> various data structures libraries.
>
> I am not sure I understood properly what you meant. Could you give an
> example using "union" or "difference" of keys ?

diff { ("a", {1;2;4}); ("b", {1}) } { ("a", {3;2;7;8}) } = { "b" }
union { ("b", [1]) } { ("a", {3;2;7;8}) } = { "a"; "b" }
inter { ("b", [1]) } { ("a", {3;2;7;8}) } = { }

I define a `merge' function so that:
merge { ("a", {1;2;4}); ("b", {1}) } { ("a", {3;2;7;8}) } =
    { ("a", {1;2;3;4;7;8}); ("b", {1}) }

For this I define a `really_add' function so that:
really_add ("a", {1}) { ("a", {3;2;7;8}); ... } =
    { ("a", {1;3;2;7;8}); ... }

which should perform O(log n) comparisons of keys (the strings) and
not O(n). This is where I need an O(log n) find, or a remove that returns
me the element that was removed.


Martin

-------------------
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