Re: [Caml-list] to merge list of lists

[Pal-Kristian Engstad <pal_engstad@naughtydog.com>]

Sometimes, imperative style is easier to understand (and probably faster):

let transpose ll =
  let array = Array.map Array.of_list (Array.of_list ll) in (* create 2d 
array *)
  let maxlen = Array.fold_left (fun acc lst -> max acc (Array.length 
lst)) 0 array in (* find maximum length *)
  let res = Array.create maxlen [] in (* create return value *)
    for j = 0 to maxlen - 1 do
      for i = 0 to Array.length array - 1 do
        if j < Array.length array.(i) then
          res.(j) <- array.(i).(j) :: res.(j)
      done
    done;
    Array.to_list (Array.map List.rev res)

PKE.


Pietro Abate wrote:
> 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]]
>
> I've written it down, but to me, it looks overly complicated :
>
> let rec mergel acc ll =
>     let rec aux (al,all) = function
>         [] -> (List.rev al,List.rev all)
>       | [] :: tl -> aux (al,all) tl
>       | (h :: l) :: tl -> aux ((h::al),(l::all)) tl
>     in match aux ([],[]) ll with
>       |([],[]) -> List.rev acc
>       |(l,[]) -> l::acc
>       |(l,tl) -> mergel (l::acc) tl
> ;;
>
> 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,
> ...). (?)
>
> 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 ?
>
> Any hints ?
>
> :)
> p
>
>   

-- 
Pål-Kristian Engstad (engstad@naughtydog.com), Lead Programmer, ICE
team, Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
Santa Monica, CA 90404, USA. Ph.: (310) 633-9112.

"Most of us would do well to remember that there is a reason Carmack
is Carmack, and we are not Carmack.",
                       Jonathan Blow, 2/1/2006, GD Algo Mailing List