Re: to merge list of lists

[Zheng Li <li@pps.jussieu.fr>]

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 re-post it for your
reference.

[1] http://caml.inria.fr/pub/ml-archives/caml-list/2007/02/cf0ae15f6f6e18ebf71c79c127d41a74.en.html

The permute question raised in [1], and also in many other situation, is just
solving the 8-queen 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 n-queen 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, tail-recursion and row-major 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, tail-recursive, row-major
   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.)