to merge list of lists
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20070305 (14:42) 
From:  Zheng Li <li@p...> 
Subject:  Re: to merge list of lists 
hi, > A few weeks ago, someone else asked the permute question [1] in this > list. There are instructive followups you may want to read. I'll also post my > answer here sometime later. This is not a direct response to you question, but it could be related to the problem you want to solve. The original version of this post was posted at a FP forum several years ago. I recently read [1] which is almost identical, and now your question which is closely related, so here I repost it for your reference. [1] http://caml.inria.fr/pub/mlarchives/camllist/2007/02/cf0ae15f6f6e18ebf71c79c127d41a74.en.html The permute question raised in [1], and also in many other situation, is just solving the 8queen problem in another form (in OP, n = 8, whereas the n could be any). There are typically two ways to solve such kind of problem: combination and iteration. The former first combinatrially *generate* all the configurations then filter (or other op) them according to some condition; the later does not generate configurations, instead it iterates over them. Almost any book I read would suggest to use iteration instead of combination for such problems. But in case you're not solving the nqueen like problem and really need to generate it by combination, here we investigate both of them. By Combination  You probably won't be able to write such a function on the fly, especially when taking functional, tailrecursion and rowmajor all into consideration. This is due to the fact that there are usually 3 nested layers of recursion you need to deal with here (if you really walk through them all by recursion):  the arbitrary dimension $n$  the range in each dimension (min, max)  and any underlying operation over a list (e.g. prefix all elements of a list with sth etc.) Anyway, here is a possible version. We use (int * int) list, other than int list * int list, to represent range pairs in each dimension to ensure we always have the same number of lower/upper bounds.  open List let permute : (int * int) list > int list list = let rec aux res tmp = function  [] > res  (a,b) :: t when a <= b > let tmp' = fold_left (fun l x > (a :: x) :: l) tmp res in aux res tmp' ((a + 1, b) :: t)  _ :: t > aux (rev tmp) [] t in function [] > []  l > aux [[]] [] (rev l)  test it: (given min <= max )  # permute [];;  : int list list = [] # permute [1,4];;  : int list list = [[1]; [2]; [3]; [4]] permute [(1,4); (12,15); (5,6); (21,22)];;  : int list list = [[1; 12; 5; 21]; [1; 12; 5; 22]; [1; 12; 6; 21]; [1; 12; 6; 22]; [1; 13; 5; 21]; [1; 13; 5; 22]; [1; 13; 6; 21]; [1; 13; 6; 22]; [1; 14; 5; 21]; [1; 14; 5; 22]; [1; 14; 6; 21]; [1; 14; 6; 22]; [1; 15; 5; 21]; [1; 15; 5; 22]; [1; 15; 6; 21]; [1; 15; 6; 22]; [2; 12; 5; 21]; [2; 12; 5; 22]; [2; 12; 6; 21]; [2; 12; 6; ...]; ...]  Though, doing such kind of job with combination is really bad:  It's difficult to write, esp. fully functional, tailrecursive, rowmajor etc.  It generates and hold *all* the configurations in *memory*, which is unnecessary in most cases when you just want to iter (esp. filter) them. It has serious problem with huge data.  It generates all the result at last  at the final step, but nothing before that. Think about the situation if data is huge and take months to permute before you can see a single result, and after that you found something is initially wrong with your algorithm. You definitely want to see the frontal configurations coming out without waiting for the latter, but the combination way doesn't work like that. One should aware the many points above don't apply to lazy language like haskell, as the configurations are not really computed and hold in memory unless required. By Iteration  So as in any book, in most case you should use iteration, I won't repeat them. It can be done functionally in OCaml without doubt. I give a version written in stream, you won't have any problem in rewrite it with list if you want.  let rec next = function  h::t, min::min_t, max::max_t > if h < max then h + 1 :: t else min :: next (t, min_t, max_t)  _ > raise (Invalid_argument "next") let permute l = let min, max = List.split (rev l) in let rec gen x = [< 'rev x; if x = max then [<>] else gen (next (x,min,max)) >] in gen min;;  Then you just use Stream.iter, Stream.next or parser to do whatever you want with it, including store it globally to get the same reult as the combination method if you really need. e.g let s = permute [(1,4); (12,17); (5,6)] in Stream.iter (fun l > List.iter (Printf.printf "%d ") l; print_newline ()) s There is another stream version which doesn't use the "next" function above, instead recursion over the dimensions and ranges, similar to the combination way but can produce result lazily.  let rec map f = parser [<'x ; rest>] > [<'f x; map f rest>]  [< >] > [< >] let rec permute = function  (a, b) :: t when a <= b > [< (match t with [] > [<'[a]>]  _ > map (fun x > a :: x) (permute t)); permute ((a + 1, b) :: t) >]  _ > [< >];;  HTH.  Zheng Li http://www.pps.jussieu.fr/~li/software (OcamlP3l, STM for OCaml, Enhanced toplevel etc.)