Search the web
Sign In
New User? Sign Up
ocaml_beginners · Ocaml Beginners
? Already a member? Sign in to Yahoo!

Yahoo! Groups Tips

Did you know...
Want your group to be featured on the Yahoo! Groups website? Add a group photo to Flickr.

Best of Y! Groups

   Check them out and nominate your group.
Having problems with message search? Fill out this form to ensure your group is one of the first to be migrated to the new message search system.

Messages

  Messages Help
Advanced
Messages 11562 - 11591 of 11591   Oldest  |  < Older  |  Newer >  |  Newest
Messages: Show Message Summaries   (Group by Topic) Sort by Date ^  
#11562 From: Tim Hanson <sideskate@...>
Date: Tue Nov 17, 2009 11:12 pm
Subject: Re: "ocaml_beginners"::[] >>=
lifekidyeaa
Offline Offline
Send Email Send Email
 
It is syntactic sugar for 'bind' - see the documentation at
http://ocsigen.org/docu/1.2.0/Lwt.html

Tim

On Tue, Nov 17, 2009 at 2:04 PM, Rakotomandimby Mihamina <
mihamina@...> wrote:

>
>
> Hi all,
> In http://ocsigen.org/eliom/manual/1.2.0/2#p2sessiondata I find this
> portion of code:
> [...]
> let session_data_example_with_post_params_handler sp _ login =
> Eliom_sessions.close_session ~sp () >>= fun () ->
> Eliom_sessions.set_volatile_session_data ~table:my_table ~sp login;
> return
> (html
> (head (title (pcdata "")) [])
> (body
> [p [pcdata ("Welcome " ^ login ^ ". You are now connected.");
> br ();
> Eliom_predefmod.Xhtml.a session_data_example sp [pcdata "Try again"] ()
> ]]))
> [...]
>
> What is that ">>="?
> Does it have a name so that I could make some search about it?
>
> Thank you.
>
> --
> Architecte Informatique chez Blueline/Gulfsat:
> Administration Systeme, Recherche & Developpement
> +261 33 11 207 36
>
>


[Non-text portions of this message have been removed]

#11563 From: rixed@...
Date: Wed Nov 18, 2009 9:07 am
Subject: red black tree with constant time iterator
rixed
Offline Offline
Send Email Send Email
 
While advertising the OCaml language around me at work showing how nice the red
black tree implementation was (the one from Okasaki), I was asked how would one
build a constant time iterator over this map.

With a mutable map, one would classicly store a pointer on each node to the
node containing the next value (so that you can traverse the map in values
order merely by following this pointer).

But with a persistant map that's less straighforward.  The problem is that we
now have two references to any node ; the only solution I can think of require
adding a "key" on the node values to mimick object addresses, and I find this
very inelegant.

Do you know of any solution to this problem ; maybe using a "zipper" trick of
some sort ?

#11564 From: Mac Mason <mac@...>
Date: Wed Nov 18, 2009 4:08 pm
Subject: Re: "ocaml_beginners"::[] red black tree with constant time iterator
macfoobar
Offline Offline
Send Email Send Email
 
On Nov 18, 2009, at 4:07 AM, rixed@... wrote:
> While advertising the OCaml language around me at work showing how
> nice the red black tree implementation was (the one from Okasaki), I
> was asked how would one build a constant time iterator over this map.
> With a mutable map, one would classicly store a pointer on each node
> to the node containing the next value (so that you can traverse the
> map in values order merely by following this pointer).

What you're describing there is called a "threaded tree", and I don't
(offhand) know of any functional implementations. Maintaining threaded
trees is a pain in the neck, even in the imperative setting. (TAOCP is a
good reference for this, if you're curious)

> Do you know of any solution to this problem ; maybe using a "zipper"
> trick of some sort ?

How attached are you to exact constant-time complexity? Doing a tree
traversal (say, in-order) runs in amortized constant time per element
[0], and is trivially implemented recursively. With a lazy
implementation, you're (pretty much) there, and it's really, really
easy to implement.

   --Mac

[0]: Finding the first element in O(lg n), but each edge in the tree is
traversed exactly twice (once on the way up, once on the way down), and
the number of edges is O(the number of nodes), so it's amortized
constant per node.

--
Julian "Mac" Mason      mac@...      www.cs.duke.edu/~mac

#11565 From: Jon Harrop <jon@...>
Date: Wed Nov 18, 2009 5:32 pm
Subject: Re: "ocaml_beginners"::[] red black tree with constant time iterator
jon@...
Send Email Send Email
 
On Wednesday 18 November 2009 09:07:07 rixed@... wrote:
> While advertising the OCaml language around me at work showing how nice the
> red black tree implementation was (the one from Okasaki), I was asked how
> would one build a constant time iterator over this map.
>
> With a mutable map, one would classicly store a pointer on each node to the
> node containing the next value (so that you can traverse the map in values
> order merely by following this pointer).

Yes. That's a bit nightmarish because you just turned your elegant tree into a
non-trivial graph, significantly increasing the size of a node (therefore
decreasing locality and cache efficiency) and adding 50% more pointers for
the GC to traverse. Moreover, you've greatly complicated reachability because
any subtree is now tied to the rest of the tree so you references to subtrees
will misbehave wrt iteration. Then people add parent pointers as
well "because they are also fast" and so on...

In practice, you probably want to keep your tree as a real tree and push the
complexity into the iterator. The problem is what happens when the tree gets
mutated in place while it is being iterated. The usual imperative cop-out is
to apply the infamous "where does the program counter go? who knows."
semantics and just let it crash.

> But with a persistant map that's less straighforward.  The problem is that
> we now have two references to any node ; the only solution I can think of
> require adding a "key" on the node values to mimick object addresses, and I
> find this very inelegant.

Push the complexity into the iterator: keep an immutable stack (i.e. list) in
the iterator and, when you see a node (l, v, r), push v and r onto the stack
and branch into l. In terms of machinery, look at the enumeration code in the
Set and Map modules that is used :

     type enumeration = End | More of elt * t * enumeration

     let rec cons_enum s e =
       match s with
         Empty -> e
       | Node(l, v, r, _) -> cons_enum l (More(v, r, e))

     let rec compare_aux e1 e2 =
         match (e1, e2) with
         (End, End) -> 0
       | (End, _)  -> -1
       | (_, End) -> 1
       | (More(v1, r1, e1), More(v2, r2, e2)) ->
           let c = Ord.compare v1 v2 in
           if c <> 0
           then c
           else compare_aux (cons_enum r1 e1) (cons_enum r2 e2)

     let compare s1 s2 =
       compare_aux (cons_enum s1 End) (cons_enum s2 End)

This has lots of advantages: you're only keeping references to bits of tree
that you might need and, therefore, the GC can collect unreachable data
correctly. These iterators are persistent like the tree itself, so you can do
things like backtracking easily by reusing old iterators safe in the
knowledge that they are still valid. This data structure is very efficient in
OCaml.

Then there is the question of how you actually expose this to the user. The
enumerations in the Set and Map modules are not exposed, they are just used
for the "compare" function to enumerate over two sets/maps simultaneously
comparing their elements. One simple approach is to write your enumeration
code in continuation passing style and then pass your user's function a
continuation that will continue the enumeration on to the next element.

--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

#11566 From: rixed@...
Date: Thu Nov 19, 2009 7:46 am
Subject: Re: "ocaml_beginners"::[] red black tree with constant time iterator
rixed
Offline Offline
Send Email Send Email
 
-[ Wed, Nov 18, 2009 at 05:32:33PM +0000, Jon Harrop ]----
> Push the complexity into the iterator: keep an immutable stack (i.e. list) in
> the iterator and, when you see a node (l, v, r), push v and r onto the stack
> and branch into l. In terms of machinery, look at the enumeration code in the
> Set and Map modules that is used :
>
> (...)
>
> This has lots of advantages: you're only keeping references to bits of tree
> that you might need and, therefore, the GC can collect unreachable data
> correctly. These iterators are persistent like the tree itself, so you can do
> things like backtracking easily by reusing old iterators safe in the
> knowledge that they are still valid. This data structure is very efficient in
> OCaml.

Thank you very much for these explanations and comments.
I think I understood all of this, but yet I fail to see how this iterator can
be faster than the trivial recursive one.

I did some measurements using this programm :

-----[ tree.ml ]-------------------------------------------------------------
(* Simple iterator over a red-black tree benchmark.
    Compile with : ocamlopt -o tree unix.cmxa tree.ml *)

type color = Red | Black
type 'a rbtree = Node of color * 'a * 'a rbtree * 'a rbtree | Leaf

let balance = function
	 | Black, z, Node (Red, y, Node (Red, x, a, b), c), d
	 | Black, z, Node (Red, x, a, Node (Red, y, b, c)), d
	 | Black, x, a, Node (Red, z, Node (Red, y, b, c), d)
	 | Black, x, a, Node (Red, y, b, Node (Red, z, c, d)) ->
		 Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
	 | a, b, c, d -> Node (a, b, c, d)

let insert x s =
	 let rec ins = function
		 | Leaf -> Node (Red, x, Leaf, Leaf)
		 | Node (color, y, a, b) as s ->
			 if x < y then balance (color, y, ins a, b)
			 else if x > y then balance (color, y, a, ins b)
			 else s in
	 match ins s with (* guaranteed to be non-empty *)
	 | Node (_, y, a, b) -> Node (Black, y, a, b)
	 | Leaf -> raise (Invalid_argument "insert");;

let rec mem x = function
	 | Leaf -> false
	 | Node (_, y, left, right) ->
		 x = y || (x < y && mem x left) || (x > y && mem x right)

let rec iter1 f = function
	 | Leaf -> ()
	 | Node (_, x, left, right) ->
		 iter1 f left ;
		 f x ;
		 iter1 f right

type 'a enumeration = End | More of 'a * 'a rbtree * 'a enumeration

let rec iter2 f t =
	 let rec cons_enum e = function
		 | Leaf -> e
		 | Node (_, x, left, right) -> cons_enum (More (x, right, e)) left in
	 let rec aux = function
		 | End -> ()
		 | More (x, right, e) -> f x ; aux (cons_enum e right) in
	 aux (cons_enum End t)

let () =
	 Random.self_init () ;
	 let rec ins t count =
		 if count > 0 then
			 let x = Random.int max_int in
			 ins (insert x t) (count-1)
		 else t in
	 let t = ref (ins Leaf 1_000_000) in
	 let bench iterator =
		 let start = Unix.gettimeofday () in
		 let size = ref 0 in
		 iterator (fun _ -> incr size) !t ;
		 let delay = (Unix.gettimeofday ()) -. start in
		 Printf.printf "%d %f " !size delay
	 in
	 for run = 0 to 10 do
		 bench iter1 ;
		 bench iter2 ;
		 Printf.printf "\n" ;
		 t := ins !t 1_000_000
	 done
------------------------------------------------------[ tree.ml ]------------

Which seams to shows (using for instance gnuplot) that both iter1 and iter2 are
vaguely linear and that iter1 is slightly faster than iter2.

So I might have misunderstood what you've said after all :-)

> Then there is the question of how you actually expose this to the user.
> (...)  One simple approach is to write your enumeration code in continuation
> passing style and then pass your user's function a continuation that will
> continue the enumeration on to the next element.

I'm not used to passing continuations, as you can tell by the code above.
With proper inlining, would this make any difference ?

#11567 From: Jon Harrop <jon@...>
Date: Thu Nov 19, 2009 4:07 pm
Subject: Re: "ocaml_beginners"::[] red black tree with constant time iterator
jon@...
Send Email Send Email
 
On Thursday 19 November 2009 07:46:12 rixed@... wrote:
> Which seams to shows (using for instance gnuplot) that both iter1 and iter2
> are vaguely linear and that iter1 is slightly faster than iter2.

Yes.

> So I might have misunderstood what you've said after all :-)

The enumeration is not supposed to be faster; it is supposed to be more
expressive.

> > Then there is the question of how you actually expose this to the user.
> > (...)  One simple approach is to write your enumeration code in
> > continuation passing style and then pass your user's function a
> > continuation that will continue the enumeration on to the next element.
>
> I'm not used to passing continuations, as you can tell by the code above.
> With proper inlining, would this make any difference ?

Specifically, it control inverts the process of iterating over the sequence.
For example, you can write compare using the enumeration but not using iter
because there is no way to iter two sets simultaneously.

--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

#11568 From: Martin DeMello <martindemello@...>
Date: Thu Nov 19, 2009 3:06 pm
Subject: applying int_to_float to every element in a tuple
martindemello
Offline Offline
Send Email Send Email
 
I have a function, f, returning a tuple of three floats, and a
function, g: int -> int -> int -> whatever. Right now I'm saying

let (x, y, z) = f args in g (int_of_float x) (int_of_float y) (int_of_float z)

Is there any nicer way to do that?

martin

#11569 From: Jon Harrop <jon@...>
Date: Thu Nov 19, 2009 4:31 pm
Subject: Re: "ocaml_beginners"::[] applying int_to_float to every element in a tuple
jon@...
Send Email Send Email
 
On Thursday 19 November 2009 15:06:55 Martin DeMello wrote:
> I have a function, f, returning a tuple of three floats, and a
> function, g: int -> int -> int -> whatever. Right now I'm saying
>
> let (x, y, z) = f args in g (int_of_float x) (int_of_float y) (int_of_float
> z)
>
> Is there any nicer way to do that?

You can factor out a map_3 function:

   let map_3 f (x, y, z) = f x, f y, f z;;

   let x, y, z = map_3 int_of_float (f args) in
   g x y z

--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

#11570 From: Richard Jones <rich@...>
Date: Thu Nov 19, 2009 10:58 pm
Subject: Re: "ocaml_beginners"::[] applying int_to_float to every element in a tuple
rwmjones
Offline Offline
Send Email Send Email
 
On Thu, Nov 19, 2009 at 08:36:55PM +0530, Martin DeMello wrote:
> I have a function, f, returning a tuple of three floats, and a
> function, g: int -> int -> int -> whatever. Right now I'm saying
>
> let (x, y, z) = f args in g (int_of_float x) (int_of_float y) (int_of_float z)
>
> Is there any nicer way to do that?

Well, it largely depends on how you define the word "nicer" but in the
current implementation tuples are basically the same as Arrays (even
for tuples of floats) so doing an Obj.magic cast to an array, followed
by using Array.map, and then another cast back to the original type
should work.

# let t4 = (1, 2, 3, 4) ;;
val t4 : int * int * int * int = (1, 2, 3, 4)
# Array.map float_of_int (Obj.magic t4 : int array) ;;
- : float array = [|1.; 2.; 3.; 4.|]
# let t4' = (1., 2., 3., 4.) ;;
val t4' : float * float * float * float = (1., 2., 3., 4.)
# Array.map int_of_float (Obj.magic t4' : float array) ;;
- : int array = [|1; 2; 3; 4|]

Rich.

--
Richard Jones
Red Hat

#11571 From: Martin Jambon <martin_jambon@...>
Date: Fri Nov 20, 2009 9:27 am
Subject: Re: "ocaml_beginners"::[] applying int_to_float to every element in a tuple
BioMim
Offline Offline
Send Email Send Email
 
Richard Jones wrote:
> On Thu, Nov 19, 2009 at 08:36:55PM +0530, Martin DeMello wrote:
>> I have a function, f, returning a tuple of three floats, and a
>> function, g: int -> int -> int -> whatever. Right now I'm saying
>>
>> let (x, y, z) = f args in g (int_of_float x) (int_of_float y) (int_of_float
z)
>>
>> Is there any nicer way to do that?
>
> Well, it largely depends on how you define the word "nicer" but in the
> current implementation tuples are basically the same as Arrays (even
> for tuples of floats) so doing an Obj.magic cast to an array, followed
> by using Array.map, and then another cast back to the original type
> should work.
>
> # let t4 = (1, 2, 3, 4) ;;
> val t4 : int * int * int * int = (1, 2, 3, 4)
> # Array.map float_of_int (Obj.magic t4 : int array) ;;
> - : float array = [|1.; 2.; 3.; 4.|]
> # let t4' = (1., 2., 3., 4.) ;;
> val t4' : float * float * float * float = (1., 2., 3., 4.)
> # Array.map int_of_float (Obj.magic t4' : float array) ;;
> - : int array = [|1; 2; 3; 4|]

Beginners should note however that the Obj module should not be used in
regular programs and that float arrays use a special internal representation
which prevents them to being cast to tuples:

# let t4 = (1, 2, 3, 4);;
val t4 : int * int * int * int = (1, 2, 3, 4)
# let a4 = Array.map float_of_int (Obj.magic t4 : int array);;
val a4 : float array = [|1.; 2.; 3.; 4.|]
# let t4' = (Obj.magic a4 : float * float * float * float);;
val t4' : float * float * float * float = (1., 2., 3., 4.)
# match t4' with (x,_,_,_) -> x;;
Segmentation fault


Martin

--
http://mjambon.com/

#11572 From: Richard Jones <rich@...>
Date: Fri Nov 20, 2009 8:21 pm
Subject: Re: "ocaml_beginners"::[] applying int_to_float to every element in a tuple
rwmjones
Offline Offline
Send Email Send Email
 
On Fri, Nov 20, 2009 at 10:27:36AM +0100, Martin Jambon wrote:
> Beginners should note however that the Obj module should not be used in
> regular programs and that float arrays use a special internal representation
> which prevents them to being cast to tuples:
>
> # let t4 = (1, 2, 3, 4);;
> val t4 : int * int * int * int = (1, 2, 3, 4)
> # let a4 = Array.map float_of_int (Obj.magic t4 : int array);;
> val a4 : float array = [|1.; 2.; 3.; 4.|]
> # let t4' = (Obj.magic a4 : float * float * float * float);;
> val t4' : float * float * float * float = (1., 2., 3., 4.)
> # match t4' with (x,_,_,_) -> x;;
> Segmentation fault

Ah yes, I forgot about *that* case, which just goes to show that what
Martin says is right :-)

Rich.

--
Richard Jones
Red Hat

#11573 From: "kxenator" <kxenator@...>
Date: Mon Nov 23, 2009 1:09 am
Subject: Toploop and others
kxenator
Offline Offline
Send Email Send Email
 
Hi!
According to OCaml documentation, standard library modules can be used in
toplevel phrases without having to load any .cmo file in memory. But I found out
that there are other modules that I can use - for example Toploop or Topdirs. Is
there any comprehensive list of modules that are loaded in startup of toplevel?
Is there any documentation for Toploop and Topdirs etc.? I didn't find anything
about that.

Thanks for an answer.

#11574 From: Rakotomandimby Mihamina <mihamina@...>
Date: Mon Nov 23, 2009 3:56 pm
Subject: nntp
rakotomandim...
Offline Offline
Send Email Send Email
 
Hello,

Is there any known NNTP (Newsgroups) piece of code to ease fetching and posting
to a newsgroup server?

No problem if it does not handle binaries, I just need full text one.

--
        Architecte Informatique chez Blueline/Gulfsat:
     Administration Systeme, Recherche & Developpement
                                     +261 33 11 207 36

#11575 From: Richard Jones <rich@...>
Date: Mon Nov 23, 2009 7:38 pm
Subject: Re: "ocaml_beginners"::[] Toploop and others
rwmjones
Offline Offline
Send Email Send Email
 
On Mon, Nov 23, 2009 at 01:09:04AM -0000, kxenator wrote:
> According to OCaml documentation, standard library modules can be
> used in toplevel phrases without having to load any .cmo file in
> memory. But I found out that there are other modules that I can use -
> for example Toploop or Topdirs. Is there any comprehensive list of
> modules that are loaded in startup of toplevel? Is there any
> documentation for Toploop and Topdirs etc.? I didn't find anything
> about that.

No, not very much.  You can examine the interface, the easiest
way being to type:

module T = Toploop ;;

This would be a very good subject for a tutorial if you can
explore useful functions of the toplevel :-)

Rich.

--
Richard Jones
Red Hat

#11576 From: Richard Jones <rich@...>
Date: Mon Nov 23, 2009 7:44 pm
Subject: Re: "ocaml_beginners"::[] nntp
rwmjones
Offline Offline
Send Email Send Email
 
On Mon, Nov 23, 2009 at 06:56:45PM +0300, Rakotomandimby Mihamina wrote:
> Is there any known NNTP (Newsgroups) piece of code to ease fetching
> and posting to a newsgroup server?
>
> No problem if it does not handle binaries, I just need full text one.

I thought that ocamlnet could do this, but I just checked and there is
no NNTP module I could see.  It would probably be easy enough to write
one.

However ...

I suggest for these sorts of tasks, which are not very CPU intensive,
use perl4caml to access the corresponding Perl module (Net::NNTP) from
OCaml code.

   http://merjis.com/developers/perl4caml/

I've been slowly moving my private CVS repositories to
http://git.annexia.org so if you would like git access to perl4caml
then let me know.

Rich.

--
Richard Jones
Red Hat

#11577 From: Richard Jones <rich@...>
Date: Mon Nov 23, 2009 8:05 pm
Subject: Re: "ocaml_beginners"::[] nntp
rwmjones
Offline Offline
Send Email Send Email
 
On Mon, Nov 23, 2009 at 07:44:38PM +0000, Richard Jones wrote:
> I've been slowly moving my private CVS repositories to
> http://git.annexia.org so if you would like git access to perl4caml
> then let me know.

Done for perl4caml:

http://git.annexia.org/?p=perl4caml.git;a=summary

Rich.

--
Richard Jones
Red Hat

#11578 From: Rakotomandimby Mihamina <mihamina@...>
Date: Tue Nov 24, 2009 11:04 am
Subject: please review
rakotomandim...
Offline Offline
Send Email Send Email
 
Hi all,
I am slowly learning ocsigen.
I note each recipe I find important (at least for me) here:
http://www.rktmb.org/category/work/ocaml

Please review, and kindly ;-) tell me if I write dumb things.

--
        Architecte Informatique chez Blueline/Gulfsat:
     Administration Systeme, Recherche & Developpement
                                     +261 33 11 207 36

#11579 From: Sylvain Le Gall <sylvain@...>
Date: Tue Nov 24, 2009 3:01 pm
Subject: Re: please review
gildor16478
Offline Offline
Send Email Send Email
 
Hello,
On 24-11-2009, Rakotomandimby Mihamina <mihamina@...> wrote:
>
> Hi all,
> I am slowly learning ocsigen.
> I note each recipe I find important (at least for me) here:
> http://www.rktmb.org/category/work/ocaml
>

For this kind of recipe, you can maybe submit it to
https://forge.ocamlcore.org/snippet/browse.php?by=lang&lang=1
where people can help you correct them online.

Regards
Sylvain Le Gall

#11580 From: Erick Matsen <ematsen@...>
Date: Tue Nov 24, 2009 6:33 pm
Subject: "hashtable" on integer lists with approximate matching
slothkisser
Offline Offline
Send Email Send Email
 
Hello ocamlers--


I'm like to get a little bit of advice on something I will be
implementing soon. It seems fairly standard, and I hope you don't mind
the mundane question.

I'd like to have something like a hashtable on integer lists with
approximate matching.

That is, if I put in keys [1;2;3] and [1;3;6], I'd like a query with
[1;7;9] to match the first element 1, then have some specifiable
behavior for dealing with the next step. For example, we might proceed
on to matching 3 in the second element, as it has the smallest
absolute value.

We could certainly do this with a tree of hash tables, but for some
reason my "inelegant" light is going on. This route might have a type
like

type 'a lorder = Node of (int, lorder) Hashtbl.t | Leaf of 'a

"In place" modification is probably desireable, because I'll be
wanting to add lots of entries into such a data structure, and I'll
only need one at a time.


Any advice would be much appreciated!

Erick

#11581 From: Jon Harrop <jon@...>
Date: Tue Nov 24, 2009 8:03 pm
Subject: Re: "ocaml_beginners"::[] "hashtable" on integer lists with approximate matching
jon@...
Send Email Send Email
 
On Tuesday 24 November 2009 18:33:01 Erick Matsen wrote:
> Any advice would be much appreciated!

Study the use of the "trie" data structure for spell checking because that is
also an approximate search over a sequence.

--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

#11582 From: Hugo Ferreira <hmf@...>
Date: Tue Nov 24, 2009 7:05 pm
Subject: Re: "ocaml_beginners"::[] "hashtable" on integer lists with approximate matching
hugotwo3
Offline Offline
Send Email Send Email
 
Hi,

Erick Matsen wrote:
> Hello ocamlers--
>
>
> I'm like to get a little bit of advice on something I will be
> implementing soon. It seems fairly standard, and I hope you don't mind
> the mundane question.
>
> I'd like to have something like a hashtable on integer lists with
> approximate matching.
>
> That is, if I put in keys [1;2;3] and [1;3;6], I'd like a query with
> [1;7;9] to match the first element 1, then have some specifiable
> behavior for dealing with the next step. For example, we might proceed
> on to matching 3 in the second element, as it has the smallest
> absolute value.

It seems like you are looking for approximate string searching or
comparison. Don't know which. Two solutions come to mind:

1. Use the Trie data structure for approximate string searching [1].
2. Use the Levenshtein distance to determine how different two string
are (uses dynamic programming) [2].

Take a look at [3] for more references.

HTHs,
Hugo F.

[1] E. Ukkonen: Finding approximate patterns in strings. J. Algorithms 6
(1985), 132-137. See http://www.cs.helsinki.fi/u/ukkonen/
[2] http://en.wikipedia.org/wiki/Levenshtein_distance
[3] http://en.wikipedia.org/wiki/Edit_distance

>
>
> ------------------------------------
>
> Archives up to December 31, 2008 are also downloadable at
http://www.connettivo.net/cntprojects/ocaml_beginners/
> The archives of the very official ocaml list (the seniors' one) can be found
at http://caml.inria.fr
> Attachments are banned and you're asked to be polite, avoid flames etc.Yahoo!
Groups Links
>
>
>

#11583 From: Erick Matsen <ematsen@...>
Date: Wed Nov 25, 2009 4:08 pm
Subject: Re: "ocaml_beginners"::[] "hashtable" on integer lists with approximate matching
slothkisser
Offline Offline
Send Email Send Email
 
Hello again--


Thanks to Jon and Hugo for the suggestions.

As can be seen from my original post, I was already thinking about a trie,
but didn't know the name. It seems like my original idea of using a trie of
hashtables should work well.

I also found
http://alaska-kamtchatka.blogspot.com/2009/06/simple-efficient-trie
-maps.html


Erick

On Tue, Nov 24, 2009 at 11:05 AM, Hugo Ferreira <hmf@...> wrote:

>
>
> Hi,
>
>
> Erick Matsen wrote:
> > Hello ocamlers--
> >
> >
> > I'm like to get a little bit of advice on something I will be
> > implementing soon. It seems fairly standard, and I hope you don't mind
> > the mundane question.
> >
> > I'd like to have something like a hashtable on integer lists with
> > approximate matching.
> >
> > That is, if I put in keys [1;2;3] and [1;3;6], I'd like a query with
> > [1;7;9] to match the first element 1, then have some specifiable
> > behavior for dealing with the next step. For example, we might proceed
> > on to matching 3 in the second element, as it has the smallest
> > absolute value.
>
> It seems like you are looking for approximate string searching or
> comparison. Don't know which. Two solutions come to mind:
>
> 1. Use the Trie data structure for approximate string searching [1].
> 2. Use the Levenshtein distance to determine how different two string
> are (uses dynamic programming) [2].
>
> Take a look at [3] for more references.
>
> HTHs,
> Hugo F.
>
> [1] E. Ukkonen: Finding approximate patterns in strings. J. Algorithms 6
> (1985), 132-137. See http://www.cs.helsinki.fi/u/ukkonen/
> [2] http://en.wikipedia.org/wiki/Levenshtein_distance
> [3] http://en.wikipedia.org/wiki/Edit_distance
>
> >
> >
> > ------------------------------------
>
> >
> > Archives up to December 31, 2008 are also downloadable at
> http://www.connettivo.net/cntprojects/ocaml_beginners/
> > The archives of the very official ocaml list (the seniors' one) can be
> found at http://caml.inria.fr
> > Attachments are banned and you're asked to be polite, avoid flames
> etc.Yahoo! Groups Links
> >
> >
> >
>
>
>


[Non-text portions of this message have been removed]

#11584 From: citromatik <miguel.pignatelli@...>
Date: Thu Nov 26, 2009 1:09 pm
Subject: Combinations of lists -- tail recursive
miguel.pignatelli@...
Send Email Send Email
 
In a previous post some weeks ago, I asked for advice in getting a function
that gets all possible combinations of a list of lists using 1 element of
each sublist. i.e.

# comb;;
comb: 'a list list -> 'a list list
# comb [[1;2];[3;4;5];[6;7]];;
[[1;3;6];[1;3;7];[1;4;6];[1;4;7];[1;5;6];[1;5;7];[2;3;6];[2;3;7]...]

A couple of possible solutions were given (thanks to all who replied), but
unfortunately I am getting stack overflows in complex (real) list of lists.
So I think I need a tail recursive solution.

Also I was told to write functions that does the job for a list with n
elements (sublists) and write one (using the former) for a list with
n+1 elements. And finally, turn this into a recursive function.
That is what I tried:

(* Function that build a lol adding the element e to each element of l *)
let combo1N e l =
   List.map (fun x -> x::e::[]) l

(* Combinations of 2 lists using the former *)
let comboNN l1 l2 =
   let rec aux acc l =
     match l with
       [] -> List.flatten acc
     | h::t -> aux ((combo1N h l2)::acc) t
   in aux [] l1

(* Combinations of 3 lists using the former *)
let comboNNN l1 l2 l3 =
   let rec aux acc l =
     match l with
       [] -> List.flatten acc
     | h::t -> aux ((List.fold_left (fun acc x -> (h::x)::acc) [] (comboNN l2
l3))::acc) t
   in aux [] l1

Having that I end up with a recursive function that does the job:

(* Combinations of lol -- recursive *)
let rec combo (lol:'a list list) =
   match lol with
   | x::y::[] -> List.fold_left (fun acc e -> ((List.map (fun x -> x::e::[]))
x)@acc) [] y (* = comboNN x y *)
   | l::lot ->
       let rec aux acc l =
         match l with
         | [] -> List.flatten acc
         | h::t -> aux ((List.fold_left (fun acc x -> (h::x)::acc) [] (combo
lot))::acc) t
       in aux [] l

Unfortunately, there are still cases where I get an stack overflow error, so
I need to write the function in a tail recursive form.
My last attempt was this:

let combo (lol:'a list list) =
   let rec aux1 acc1 (l1:'a list list) =
     match l1 with
     | [] -> acc1
     | x::[] -> comboNN x (List.flatten acc1)
     | h1::t1::tl ->
         aux1 ((
         let rec aux2 acc2 (l2:'a list) =
           match l2 with
             [] -> List.flatten acc2
           | h2::t2 -> aux2 ((List.fold_left (fun acc x -> (h2::x)::acc) []
(aux1 ([t1]) tl))::acc2) t2
         in aux2 [] h1)@acc1) (t1::tl)
   in aux1 [(List.hd lol)] (List.tl lol)

But this doesn't work. I'm trying to bend my mind a bit more, but any help
would be appreciated.

Thanks in advance,

M;

--
View this message in context:
http://old.nabble.com/Combinations-of-lists----tail-recursive-tp26529218p2652921\
8.html
Sent from the Ocaml Beginner mailing list archive at Nabble.com.

#11585 From: Martin Jambon <martin_jambon@...>
Date: Thu Nov 26, 2009 1:48 pm
Subject: Re: "ocaml_beginners"::[] Combinations of lists -- tail recursive
BioMim
Offline Offline
Send Email Send Email
 
citromatik wrote:
> In a previous post some weeks ago, I asked for advice in getting a function
> that gets all possible combinations of a list of lists using 1 element of
> each sublist. i.e.
>
> # comb;;
> comb: 'a list list -> 'a list list
> # comb [[1;2];[3;4;5];[6;7]];;
> [[1;3;6];[1;3;7];[1;4;6];[1;4;7];[1;5;6];[1;5;7];[2;3;6];[2;3;7]...]
>
> A couple of possible solutions were given (thanks to all who replied), but
> unfortunately I am getting stack overflows in complex (real) list of lists.
> So I think I need a tail recursive solution.
>
> Also I was told to write functions that does the job for a list with n
> elements (sublists) and write one (using the former) for a list with
> n+1 elements. And finally, turn this into a recursive function.
> That is what I tried:
>
> (* Function that build a lol adding the element e to each element of l *)
> let combo1N e l =
>   List.map (fun x -> x::e::[]) l
>
> (* Combinations of 2 lists using the former *)
> let comboNN l1 l2 =
>   let rec aux acc l =
>     match l with
>       [] -> List.flatten acc
>     | h::t -> aux ((combo1N h l2)::acc) t
>   in aux [] l1
>
> (* Combinations of 3 lists using the former *)
> let comboNNN l1 l2 l3 =
>   let rec aux acc l =
>     match l with
>       [] -> List.flatten acc
>     | h::t -> aux ((List.fold_left (fun acc x -> (h::x)::acc) [] (comboNN l2
> l3))::acc) t
>   in aux [] l1
>
> Having that I end up with a recursive function that does the job:
>
> (* Combinations of lol -- recursive *)
> let rec combo (lol:'a list list) =
>   match lol with
>   | x::y::[] -> List.fold_left (fun acc e -> ((List.map (fun x -> x::e::[]))
> x)@acc) [] y (* = comboNN x y *)
>   | l::lot ->
>       let rec aux acc l =
>         match l with
>         | [] -> List.flatten acc
>         | h::t -> aux ((List.fold_left (fun acc x -> (h::x)::acc) [] (combo
> lot))::acc) t
>       in aux [] l
>
> Unfortunately, there are still cases where I get an stack overflow error, so
> I need to write the function in a tail recursive form.
> My last attempt was this:
>
> let combo (lol:'a list list) =
>   let rec aux1 acc1 (l1:'a list list) =
>     match l1 with
>     | [] -> acc1
>     | x::[] -> comboNN x (List.flatten acc1)
>     | h1::t1::tl ->
>         aux1 ((
>         let rec aux2 acc2 (l2:'a list) =
>           match l2 with
>             [] -> List.flatten acc2
>           | h2::t2 -> aux2 ((List.fold_left (fun acc x -> (h2::x)::acc) []
> (aux1 ([t1]) tl))::acc2) t2
>         in aux2 [] h1)@acc1) (t1::tl)
>   in aux1 [(List.hd lol)] (List.tl lol)
>
> But this doesn't work. I'm trying to bend my mind a bit more, but any help
> would be appreciated.


I did not follow the thread at the time, but here is what I would do:


let iter_product f ll =
   let aa = Array.map Array.of_list (Array.of_list ll) in
   let n = Array.length aa in
   let zero = Array.make n 0 in
   let rec next p q =
     (f q : unit);
     (try
        for i = 0 to n - 1 do
	  let pi = p.(i) + 1 in
	  let m = Array.length aa.(i) in
	  if pi >= m then (
	    p.(i) <- 0;
	    q.(i) <- aa.(i).(0)
	  )
	  else (
	    p.(i) <- pi;
	    q.(i) <- aa.(i).(pi);
	    raise Exit
	  )
        done
      with Exit -> ()
     );
     if p <> zero then
       next p q
   in
   next (Array.make n 0) (Array.init n (fun i -> aa.(i).(0)))

let build_product ll =
   let accu = ref [] in
   iter_product (fun p -> accu := Array.copy p :: !accu) ll;
   !accu



Martin

--
http://mjambon.com/

#11586 From: Martin Jambon <martin_jambon@...>
Date: Thu Nov 26, 2009 2:16 pm
Subject: Re: "ocaml_beginners"::[] Combinations of lists -- tail recursive
BioMim
Offline Offline
Send Email Send Email
 
Martin Jambon wrote:
> citromatik wrote:
>> In a previous post some weeks ago, I asked for advice in getting a function
>> that gets all possible combinations of a list of lists using 1 element of
>> each sublist. i.e.
>>
>> # comb;;
>> comb: 'a list list -> 'a list list
>> # comb [[1;2];[3;4;5];[6;7]];;
>> [[1;3;6];[1;3;7];[1;4;6];[1;4;7];[1;5;6];[1;5;7];[2;3;6];[2;3;7]...]
>>
>> A couple of possible solutions were given (thanks to all who replied), but
>> unfortunately I am getting stack overflows in complex (real) list of lists.
>> So I think I need a tail recursive solution.
>>
>> Also I was told to write functions that does the job for a list with n
>> elements (sublists) and write one (using the former) for a list with
>> n+1 elements. And finally, turn this into a recursive function.
>> That is what I tried:
>>
>> (* Function that build a lol adding the element e to each element of l *)
>> let combo1N e l =
>>   List.map (fun x -> x::e::[]) l
>>
>> (* Combinations of 2 lists using the former *)
>> let comboNN l1 l2 =
>>   let rec aux acc l =
>>     match l with
>>       [] -> List.flatten acc
>>     | h::t -> aux ((combo1N h l2)::acc) t
>>   in aux [] l1
>>
>> (* Combinations of 3 lists using the former *)
>> let comboNNN l1 l2 l3 =
>>   let rec aux acc l =
>>     match l with
>>       [] -> List.flatten acc
>>     | h::t -> aux ((List.fold_left (fun acc x -> (h::x)::acc) [] (comboNN l2
>> l3))::acc) t
>>   in aux [] l1
>>
>> Having that I end up with a recursive function that does the job:
>>
>> (* Combinations of lol -- recursive *)
>> let rec combo (lol:'a list list) =
>>   match lol with
>>   | x::y::[] -> List.fold_left (fun acc e -> ((List.map (fun x -> x::e::[]))
>> x)@acc) [] y (* = comboNN x y *)
>>   | l::lot ->
>>       let rec aux acc l =
>>         match l with
>>         | [] -> List.flatten acc
>>         | h::t -> aux ((List.fold_left (fun acc x -> (h::x)::acc) [] (combo
>> lot))::acc) t
>>       in aux [] l
>>
>> Unfortunately, there are still cases where I get an stack overflow error, so
>> I need to write the function in a tail recursive form.
>> My last attempt was this:
>>
>> let combo (lol:'a list list) =
>>   let rec aux1 acc1 (l1:'a list list) =
>>     match l1 with
>>     | [] -> acc1
>>     | x::[] -> comboNN x (List.flatten acc1)
>>     | h1::t1::tl ->
>>         aux1 ((
>>         let rec aux2 acc2 (l2:'a list) =
>>           match l2 with
>>             [] -> List.flatten acc2
>>           | h2::t2 -> aux2 ((List.fold_left (fun acc x -> (h2::x)::acc) []
>> (aux1 ([t1]) tl))::acc2) t2
>>         in aux2 [] h1)@acc1) (t1::tl)
>>   in aux1 [(List.hd lol)] (List.tl lol)
>>
>> But this doesn't work. I'm trying to bend my mind a bit more, but any help
>> would be appreciated.
>
>
> I did not follow the thread at the time, but here is what I would do:
>
>
> let iter_product f ll =
>   let aa = Array.map Array.of_list (Array.of_list ll) in
>   let n = Array.length aa in
>   let zero = Array.make n 0 in
>   let rec next p q =
>     (f q : unit);
>     (try
>        for i = 0 to n - 1 do
> 	 let pi = p.(i) + 1 in
> 	 let m = Array.length aa.(i) in
> 	 if pi >= m then (
> 	   p.(i) <- 0;
> 	   q.(i) <- aa.(i).(0)
> 	 )
> 	 else (
> 	   p.(i) <- pi;
> 	   q.(i) <- aa.(i).(pi);
> 	   raise Exit
> 	 )
>        done
>      with Exit -> ()
>     );
>     if p <> zero then
>       next p q
>   in
>   next (Array.make n 0) (Array.init n (fun i -> aa.(i).(0)))
>
> let build_product ll =
>   let accu = ref [] in
>   iter_product (fun p -> accu := Array.copy p :: !accu) ll;
>   !accu

Or this ;-)  :


let flatten ll =
   List.rev (List.fold_left (fun accu l -> List.rev_append l accu) [] ll)

let map f l =
   List.rev (List.rev_map f l)

let combine ll =
   let rec comb accu = function
       [] -> accu
     | l :: ll ->
	 let accu =
	   flatten (
	     map (fun x -> map (fun l -> x :: l) accu) l
	   )
	 in
	 comb accu ll
   in
   comb [[]] (List.rev ll)



Martin

--
http://mjambon.com/

#11587 From: Martin DeMello <martindemello@...>
Date: Thu Nov 26, 2009 5:07 pm
Subject: indentation question
martindemello
Offline Offline
Send Email Send Email
 
is this an omlet.vim bug, or am i doing something stylistically wrong?
i expected the 'done' matching the 'for j' to outdent.

let refresh_board screen cfg q =
   acquire_screen();

   for i = 0 to (cfg.m - 1) do
     for j = 0 to (cfg.n - 1) do
       let col = board_color q.board.(i).(j) in
       let x1, y1, x2, y2 = cell_boundaries i j in
       rectfill screen x1 y1 x2 y2 col
       done
     done;

     release_screen()

#11588 From: Zheng Li <zheng_li@...>
Date: Thu Nov 26, 2009 5:07 pm
Subject: Re: Combinations of lists -- tail recursive
zheng_li@...
Send Email Send Email
 
Hi,

I came up with the following snippet. Hopefully it's tail recursive and can save
you a few list flips.

---- code ----
open List
let comb lol =
   let _,lol = fold_left (fun (r,a) l -> not r, (if r then rev l else l)::a)
(true,[]) lol in
   fold_left (fun ll -> fold_left (fun tl e -> fold_left (fun t l -> (e::l)::t)
tl ll) []) [[]] lol
--------------

and

---- test ----
# comb[[1;2]];;
- : int list list = [[1]; [2]]
# comb[[1;2];[3;4;5]];;
- : int list list = [[1; 3]; [1; 4]; [1; 5]; [2; 3]; [2; 4]; [2; 5]]
# comb[[1;2];[3;4;5];[6;7]];;
- : int list list =
[[1; 3; 6]; [1; 3; 7]; [1; 4; 6]; [1; 4; 7]; [1; 5; 6]; [1; 5; 7]; [2; 3; 6];
  [2; 3; 7]; [2; 4; 6]; [2; 4; 7]; [2; 5; 6]; [2; 5; 7]]
--------------

Cheers
Zheng


citromatik wrote:
> In a previous post some weeks ago, I asked for advice in getting a function
> that gets all possible combinations of a list of lists using 1 element of
> each sublist. i.e.
>
> # comb;;
> comb: 'a list list -> 'a list list
> # comb [[1;2];[3;4;5];[6;7]];;
> [[1;3;6];[1;3;7];[1;4;6];[1;4;7];[1;5;6];[1;5;7];[2;3;6];[2;3;7]...]
>
> A couple of possible solutions were given (thanks to all who replied), but
> unfortunately I am getting stack overflows in complex (real) list of lists.
> So I think I need a tail recursive solution.
>
> Also I was told to write functions that does the job for a list with n
> elements (sublists) and write one (using the former) for a list with
> n+1 elements. And finally, turn this into a recursive function.
> That is what I tried:
>
> (* Function that build a lol adding the element e to each element of l *)
> let combo1N e l =
> List.map (fun x -> x::e::[]) l
>
> (* Combinations of 2 lists using the former *)
> let comboNN l1 l2 =
> let rec aux acc l =
> match l with
> [] -> List.flatten acc
> | h::t -> aux ((combo1N h l2)::acc) t
> in aux [] l1
>
> (* Combinations of 3 lists using the former *)
> let comboNNN l1 l2 l3 =
> let rec aux acc l =
> match l with
> [] -> List.flatten acc
> | h::t -> aux ((List.fold_left (fun acc x -> (h::x)::acc) [] (comboNN l2
> l3))::acc) t
> in aux [] l1
>
> Having that I end up with a recursive function that does the job:
>
> (* Combinations of lol -- recursive *)
> let rec combo (lol:'a list list) =
> match lol with
> | x::y::[] -> List.fold_left (fun acc e -> ((List.map (fun x -> x::e::[]))
> x)@acc) [] y (* = comboNN x y *)
> | l::lot ->
> let rec aux acc l =
> match l with
> | [] -> List.flatten acc
> | h::t -> aux ((List.fold_left (fun acc x -> (h::x)::acc) [] (combo
> lot))::acc) t
> in aux [] l
>
> Unfortunately, there are still cases where I get an stack overflow error, so
> I need to write the function in a tail recursive form.
> My last attempt was this:
>
> let combo (lol:'a list list) =
> let rec aux1 acc1 (l1:'a list list) =
> match l1 with
> | [] -> acc1
> | x::[] -> comboNN x (List.flatten acc1)
> | h1::t1::tl ->
> aux1 ((
> let rec aux2 acc2 (l2:'a list) =
> match l2 with
> [] -> List.flatten acc2
> | h2::t2 -> aux2 ((List.fold_left (fun acc x -> (h2::x)::acc) []
> (aux1 ([t1]) tl))::acc2) t2
> in aux2 [] h1)@acc1) (t1::tl)
> in aux1 [(List.hd lol)] (List.tl lol)
>
> But this doesn't work. I'm trying to bend my mind a bit more, but any help
> would be appreciated.
>
> Thanks in advance,
>
> M;
>

#11589 From: Martin DeMello <martindemello@...>
Date: Thu Nov 26, 2009 5:12 pm
Subject: Re: "ocaml_beginners"::[] indentation question
martindemello
Offline Offline
Send Email Send Email
 
oops, looks like gmail destroyed the formatting. here's a pastie:
http://pastebin.org/57496
martin

On Thu, Nov 26, 2009 at 10:37 PM, Martin DeMello
<martindemello@...> wrote:
>
>
>
> is this an omlet.vim bug, or am i doing something stylistically wrong?
> i expected the 'done' matching the 'for j' to outdent.
>
> let refresh_board screen cfg q =
> acquire_screen();
>
> for i = 0 to (cfg.m - 1) do
> for j = 0 to (cfg.n - 1) do
> let col = board_color q.board.(i).(j) in
> let x1, y1, x2, y2 = cell_boundaries i j in
> rectfill screen x1 y1 x2 y2 col
> done
> done;
>
> release_screen()
>
>

#11590 From: Richard Jones <rich@...>
Date: Thu Nov 26, 2009 6:56 pm
Subject: Re: "ocaml_beginners"::[] indentation question
rwmjones
Offline Offline
Send Email Send Email
 
On Thu, Nov 26, 2009 at 10:37:35PM +0530, Martin DeMello wrote:
> is this an omlet.vim bug, or am i doing something stylistically wrong?
> i expected the 'done' matching the 'for j' to outdent.
>
> let refresh_board screen cfg q =
>   acquire_screen();
>
>   for i = 0 to (cfg.m - 1) do
>     for j = 0 to (cfg.n - 1) do
>       let col = board_color q.board.(i).(j) in
>       let x1, y1, x2, y2 = cell_boundaries i j in
>       rectfill screen x1 y1 x2 y2 col
>       done
>     done;
>
>     release_screen()

I'd say that's a vim bug.  Here's how emacs / tuareg-mode formats it:

let refresh_board screen cfg q =
   acquire_screen();

   for i = 0 to (cfg.m - 1) do
     for j = 0 to (cfg.n - 1) do
       let col = board_color q.board.(i).(j) in
       let x1, y1, x2, y2 = cell_boundaries i j in
       rectfill screen x1 y1 x2 y2 col
     done
   done;

   release_screen()

Rich.

--
Richard Jones
Red Hat

#11591 From: "vincent" <vincent.aravantinos@...>
Date: Thu Nov 26, 2009 10:02 pm
Subject: Re: indentation question
vincent.arav...
Offline Offline
Send Email Send Email
 
Hi

--- In ocaml_beginners@yahoogroups.com, Martin DeMello <martindemello@...>
wrote:
>
> is this an omlet.vim bug, or am i doing something stylistically wrong?
> i expected the 'done' matching the 'for j' to outdent.

It works perfectly well on my machine.
I think you should not use omlet : it has been integrated into vim quite a long
time ago.
Omlet is probably outdated now w.r.t. the standard vim-ocaml plugin.

V.

Messages 11562 - 11591 of 11591   Oldest  |  < Older  |  Newer >  |  Newest
Advanced
Add to My Yahoo!      XML What's This?

Copyright © 2009 Yahoo! Inc. All rights reserved.
Privacy Policy - Terms of Service - Guidelines - Help