This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

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

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2007-03-05 (09:46) From: Zheng Li Subject: Re: to merge list of lists
```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