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]

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 ?

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

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

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

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

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

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

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

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/

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

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.

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

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

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

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

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

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

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

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

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

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]

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.

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/

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/

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

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

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

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

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.