[Caml-list] Map + Set

[Caml-list] Map + Set

[Martin Jambon]

Hi,

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.
Normally the Map module should be suitable, but it doesn't
provide set operations over the keys (union, inter, diff, ...).
The Set module is almost enough except that it doesn't provide a find
function:

val find : elt -> t -> elt  (* yes! *)

Finally I just copy-pasted set.mli and set.ml and inserted a find
function... but is there a better solution?


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

Re: [Caml-list] Map + Set

[Matt Gushee]

On Sun, Jul 25, 2004 at 04:17:55PM +0800, Martin Jambon wrote:
> 
> 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.
> 
> val find : elt -> t -> elt  (* yes! *)
> 
> Finally I just copy-pasted set.mli and set.ml and inserted a find
> function... but is there a better solution?

What I did when faced with a similar problem was:

  module MySet =
    struct
      module BaseSet = Set.Make(
        struct
          ....
        end)
      include BaseSet
      let find elt set = ...
    end

Now of course that will only handle one data type. If you want
polymorphism, I suppose you could try something like:

  module MySet =
    struct
      module Make =
        functor(SomeMod:SOMETYPE) ->
          struct
            include Set.Make
            let find elt set = ...
          end
    ....
    end

Though I haven't tried the more general approach.

-- 
Matt Gushee                 When a nation follows the Way,
Englewood, Colorado, USA    Horses bear manure through
mgushee@havenrock.com           its fields;
http://www.havenrock.com/   When a nation ignores the Way,
                            Horses bear soldiers through
                                its streets.
                                
                            --Lao Tzu (Peter Merel, trans.)

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

Re: [Caml-list] Map + Set

[Brian Hurt]

On Sun, 25 Jul 2004, Martin Jambon wrote:

> Hi,
> 
> 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.
> Normally the Map module should be suitable, but it doesn't
> provide set operations over the keys (union, inter, diff, ...).
> The Set module is almost enough except that it doesn't provide a find
> function:
> 
> val find : elt -> t -> elt  (* yes! *)

A better interface might be:

val find: (elt -> int) -> t -> elt

There is a lot of functionality I'd like to be able to add to map and set.  
I find myself reimplementing them on a regular basis myself (and no, I
haven't thought of a better solution).  Many people on this list don't
like modules, however.


-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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

Re: [Caml-list] Map + Set

[Diego Olivier Fernandez Pons]

    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 ?


        Diego Olivier

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

Re: [Caml-list] Map + Set

[Matthieu Sozeau]

[-- Attachment #1: Type: text/plain, Size: 1052 bytes --]

On Sun, Jul 25, 2004 at 12:01:03PM -0500, Brian Hurt wrote:
> On Sun, 25 Jul 2004, Martin Jambon wrote:
> 
> A better interface might be:
> 
> val find: (elt -> int) -> t -> elt

Why an int ? Isn't a boolean enough ?
 
> There is a lot of functionality I'd like to be able to add to map and set.  
> I find myself reimplementing them on a regular basis myself (and no, I
> haven't thought of a better solution).  

Apart from "val of_list : elt list -> t" (a one liner) and the find
function (a fold with an exception or using `exists` and keeping a
reference, which indicates, I think, that it should be implemented 
directly in set.ml), i don't remember truly missing functions. 
What are those ?

> Many people on this list don't like modules, however.

That seems like a weird opinion to me, and mine is that most OCaml hackers
are really caml hackers who don't want to know about the OO part.
-- 
"Are you sure you're not an encyclopedia salesman?"
No, Ma'am.  Just a burglar, come to ransack the flat."
-- Monty Python

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] Map + Set

[Brian Hurt]

On Mon, 26 Jul 2004, Matthieu Sozeau wrote:

> On Sun, Jul 25, 2004 at 12:01:03PM -0500, Brian Hurt wrote:
> > On Sun, 25 Jul 2004, Martin Jambon wrote:
> > 
> > A better interface might be:
> > 
> > val find: (elt -> int) -> t -> elt
> 
> Why an int ? Isn't a boolean enough ?

Two reasons:

1) This allows you to use Pervasives.compare (or other compatible 
function) partially applied.

2) In addition to equality, you also need less than/greater than in order 
to keep the function in O(log N)- which branch do you descend?  With just 
equality, you need to do an O(N) exhaustive search.

>  
> > There is a lot of functionality I'd like to be able to add to map and set.  
> > I find myself reimplementing them on a regular basis myself (and no, I
> > haven't thought of a better solution).  
> 
> Apart from "val of_list : elt list -> t" (a one liner) and the find
> function (a fold with an exception or using `exists` and keeping a
> reference, which indicates, I think, that it should be implemented 
> directly in set.ml), i don't remember truly missing functions. 
> What are those ?

Map, fold, and iter over pairs of maps or sets is the one I always end up 
needing.  Also, enums would be nice.  Actually, I could do the pairwise 
comprehensions if I had enums.

> 
> > Many people on this list don't like modules, however.
> 
> That seems like a weird opinion to me, and mine is that most OCaml hackers
> are really caml hackers who don't want to know about the OO part.
> 

When I tossed out my changes to map and set, they were bounced with a 
"they use modules- you should apply them to the demodulized versions of 
the code instead".  And about the only feed back I ever got on priority 
search queues amounted to "it uses modules- we don't like modules".  

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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

Re: [Caml-list] Map + Set

[Martin Jambon]

On Mon, 26 Jul 2004, Brian Hurt wrote:

> On Mon, 26 Jul 2004, Matthieu Sozeau wrote:
>
> > On Sun, Jul 25, 2004 at 12:01:03PM -0500, Brian Hurt wrote:
> > > On Sun, 25 Jul 2004, Martin Jambon wrote:
> > >
> > > A better interface might be:
> > >
> > > val find: (elt -> int) -> t -> elt
                ^^^^^^^^^^^^
This is a little unsafe, isn't it? What if you don't respect the ordering
of your set?

> > Why an int ? Isn't a boolean enough ?
>
> Two reasons:
>
> 1) This allows you to use Pervasives.compare (or other compatible
> function) partially applied.
>
> 2) In addition to equality, you also need less than/greater than in order
> to keep the function in O(log N)- which branch do you descend?  With just
> equality, you need to do an O(N) exhaustive search.

I think Brian and Matthieu are talking about 2 different things:
(1) Martin and Brian were talking of an O(log n) find just like mem.
(2) Matthieu and others are talking of a search using an
arbitrary predicate just like List.find, in O(n) steps.


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

Re: [Caml-list] Map + Set

[Martin Jambon]

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

Re: [Caml-list] Map + Set

[Brian Hurt]

On Mon, 26 Jul 2004, Martin Jambon wrote:

> > > > val find: (elt -> int) -> t -> elt
>                 ^^^^^^^^^^^^
> This is a little unsafe, isn't it? What if you don't respect the ordering
> of your set?

Then the function throws Not_found when it shouldn't.

If you already have the object you're looking for, why are you looking for 
it?  Either that or you're using a set to really implement a map- use a 
map instead.

> I think Brian and Matthieu are talking about 2 different things:
> (1) Martin and Brian were talking of an O(log n) find just like mem.
> (2) Matthieu and others are talking of a search using an
> arbitrary predicate just like List.find, in O(n) steps.
> 

What's the advantage of doing the search in O(n) time when you can do it 
in O(log n) time?

A function that finds *all* elements that fit a certain criteria I can 
understand- but that's pretty easy to implement with fold.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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

Re: [Caml-list] Map + Set

[Diego Olivier Fernandez Pons]

    Bonjour,

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

It seems to me that what you are looking for is an ('a, 'b set) map in
which the insertion does not replace the existing data but applies a
given function (like Set.add) to the current data.

I sometimes need an insert_with function for ('a, 'b list) map that
inserts the data in the list if any or creates a new list otherwise.
It is a simple modification of the 'insert' (resp. union, difference)
function.

On the other hand, if you are using strings as keys you should use a
trie instead of a map in order to ensure worst-case logarithmic
complexity (have a look to lexicalmaps in /trie of Baire).

Finally since the data part seems to be a set (and not a list as in my
example) the best solution would be a ternary tree (that is a binary
tree with one extra pointer to the set represented by a tree, which
makes 3 tree pointers)

Look in Baire the ternary tree implementation of the /graph directory


        Diego Olivier

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

[Caml-list] Camlp4 help/questions

[Josh Smith]

I apologize if this is not the right list to send this too, but I'm 
nearing my feeble wits' end and I'm starting here...

I have a project that is currently using c++ that I would like to convert to
Ocaml (parts of it are already in Ocaml and I'd like to simplify my
codebase). However, I am using the Spirit library from Boost to do parsing
in c++ and I cannot figure out Camlp4 to convert it.  If there is anyone who
knows both Spirit and Camlp4 who can help me I was appreciate it a lot.

Maybe I am an idiot, but I've been through the tutorial and it didn't help
me very much. I've been looking for example code for simple parsers and I've
found many, many calculators but little else. I've even tried to go back to 
ocamlyacc/ocamllex but the yacc/lex syntax bothers me.

I can even give you an example of what I'm trying to parse and then use the
resulting data structure (I could do regex, but these are from largish data
files and the robostness provided by a parser is what I need).

a23fassssadfj4532|10,2;13,3;20;20|10|20|30|B
aassafjeifdfj4532|11,21;13,33|1|2|3|T
... and so on for about a million lines or so

the unasked question here is "Is this the right way to go?" I mean, is
Camlp4 the tool I should be using?  I think it is, because the top down,
recursive descent parsing is what Spirit does, but maybe I've just confused
things.  

Any help is appreciated.  Thank you all.

-jbs









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

Re: [Caml-list] Camlp4 help/questions

[Brian Hurt]

On Tue, 27 Jul 2004, Josh Smith wrote:

> I apologize if this is not the right list to send this too, but I'm 
> nearing my feeble wits' end and I'm starting here...

I don't think Camlp4 is the right tool.  It's mainly an Ocaml 
preprocessor, you want Ocaml code that parses the line.

Ocamllex/Ocamlyacc are great for a lot of things- but I think I agree, 
they're also the wrong tools for the job.

I think what you want is a split function- a function that takes a string 
and splits it up at certan characters.  It'd have a type something like:
val split: char -> string -> string list

You'd then read an entire line, split it apart on '|'.  You could then 
split various substrings on ';' to get the integers, etc.

Hope this helps.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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

Re: [Caml-list] Camlp4 help/questions

[Josh Smith]

On Tue, Jul 27, 2004 at 05:11:32PM -0500, Brian Hurt wrote:
> 
> I think what you want is a split function- a function that takes a string 
> and splits it up at certan characters.  It'd have a type something like:
> val split: char -> string -> string list
>
> You'd then read an entire line, split it apart on '|'.  You could then 
> split various substrings on ';' to get the integers, etc.

This would work, and I've done it in the past. There is a split function in
the Str library that would be able to handle this.

The main problem with this is that it has to be changed a lot, and is 
error prone.  The data file that I'm parsing is changing a lot
and the line might tokenize correctly but not have the right data.  

> 
> Hope this helps.

Thank you.

-jbs

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

Re: [Caml-list] Camlp4 help/questions

[Josh Smith]

On Tue, Jul 27, 2004 at 11:07:50PM +0100, Jon Harrop wrote:
> 
> > the unasked question here is "Is this the right way to go?" I mean, is
> > Camlp4 the tool I should be using?  I think it is, because the top down,
> > recursive descent parsing is what Spirit does, but maybe I've just confused
> > things.
> 
> I am no expert on parser technology but I've written a few interpreters and 
> compilers in OCaml now and it is an excellent language for this kind of 
> stuff.

that's what I've read, but I've yet to be able to do work myself.

>Coming from a C++ background I can also say that C++ would be an awful 
> language for this and, as for template metaprogramming, well... :-)

Spirit is great.  The template metaprograming, from a user-developers
standpoint isn't so bad.  But it is one of the reasons I'd like to move 
all of my developement to Ocaml.  

> I've only used yacc, so only LALR(1) grammars. I'm not sure if this is 
> formally correct, but in a lot of cases you can get extended functionality by 
> parsing what you can and then manipulating the resulting data structures. For 
> example, in my latest compiler I need a parser which can understand not only 
> "a<b" but also "a<b<c" and so on. You can't use the same approach as for 
> addition ("a+b+c" = "(a+b)+c") so I parse into an intermediate representation 
> "Inequality[a, Less, b, Less, c]" which I postprocess into the equivalent of 
> "a<b<c".
> 
> You may find that, with similar tricks, you can parse what you need using 
> yacc.

this may be exactly what I need to do.  You don't have to do this in Spirit.
Not that that changes anything, I'm just noting it.

> Do you have a specification for the grammar? Can you give examples of input 
> and the corresponding data structure you would like?

Kinda.  I don't have an EBNF for it, but I do have input and desired output
for one of the sets (this is the simplest, but it's indicitive of
what is ussually there).

Input:
a23fassssadfj4532|10,2;13,3;20;20|10|20|30|B

Desired output (in Oaml'ish):

type origination = B | S | T | A;;
type pattern = {score:int;weight:int};;

type item = {id:string;patterns:pattern
list;max:int;min:int;time:int;origin:origination }

So, a23fassssadfj4532|10,2;13,3;20;20|10|20|30|B

would be 

id:a23fassssadfj4532
patterns:[{10,2};{13,3};{20,20}]
max:10
min:20
time:30
origin:B

It has also been noted that I could just use a combination of splits to
accomplish this, but I've found that approch to be fragile and slow.  

I've also got some ocamlyacc/ocamllex code that works (it parses a subset of
the desired input), but doesn't do what I want yet (it's mostly just
cut/paste from the manual).  I've that at http://www.bad-poetry.net/ocaml/
if anyone is interested.

Thanks for the help.

-jbs

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

Re: [Caml-list] Camlp4 help/questions

[Pierre Weis]

> I apologize if this is not the right list to send this too, but I'm 
> nearing my feeble wits' end and I'm starting here...
> 
> I have a project that is currently using c++ that I would like to convert to
> Ocaml (parts of it are already in Ocaml and I'd like to simplify my
> codebase). However, I am using the Spirit library from Boost to do parsing
> in c++ and I cannot figure out Camlp4 to convert it.  If there is anyone who
> knows both Spirit and Camlp4 who can help me I was appreciate it a lot.
> 
> Maybe I am an idiot, but I've been through the tutorial and it didn't help
> me very much. I've been looking for example code for simple parsers and I've
> found many, many calculators but little else. I've even tried to go back to 
> ocamlyacc/ocamllex but the yacc/lex syntax bothers me.
> 
> I can even give you an example of what I'm trying to parse and then use the
> resulting data structure (I could do regex, but these are from largish data
> files and the robostness provided by a parser is what I need).
> 
> a23fassssadfj4532|10,2;13,3;20;20|10|20|30|B
> aassafjeifdfj4532|11,21;13,33|1|2|3|T
> ... and so on for about a million lines or so
> 
> the unasked question here is "Is this the right way to go?" I mean, is
> Camlp4 the tool I should be using?  I think it is, because the top down,
> recursive descent parsing is what Spirit does, but maybe I've just confused
> things.  
> 
> Any help is appreciated.  Thank you all.
> 
> -jbs

If you need not parsing more complex things, you may also try the
Scanf module which is far more powerful than the C equivalent and
sounds the more appropriate for such kind of job.

I would be glad to help if you choose that way.

Best regards,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


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