Re: to merge list of lists

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

Pietro Abate <Pietro.Abate@anu.edu.au> writes:

> Hi all,
> I want to write a small function to merge a list of lists
>
> mergel [] [[1;2;3];[4;5;6];[7;8;9]];;
> - : int list list = [[1; 4; 7]; [2; 5; 8]; [3; 6; 9]]
>
> Since my goal is to write it lazily, I'm wondering if there is a way of
> re-write the same function just by using list primitives (map, flatten,
> ...). (?)
If you want to use high-order functions in the standard list library, here are
my versions:

open List
let rec merge = function
  | [] -> [] 
  | h :: [] -> map (fun x -> [x]) h
  | h::t -> map2 (fun x y -> x::y) h (merge t);;

Note that, it's not efficient at all but quite easy to understand. Another
version,

let rec merge l = match rev l with
  | [] -> []
  | h :: t -> fold_left (map2 (fun x y -> y::x)) (map (fun x -> [x]) h) t

maybe better.

> I always feel that when solving these kind of problems I miss some
> greater truth ... for example, by using list comprehensions it's easy to
> generalize a class of combinatorial problems. Is there a similar notion
> I can use in this case ?

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.

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

-- 
Zheng Li
http://www.pps.jussieu.fr/~li