From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id E4111BC6B for ; Tue, 6 Mar 2007 01:11:26 +0100 (CET) Received: from sdmx1.scea.com (sdmx1.scea.com [160.33.44.36]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l260BPEl017704 for ; Tue, 6 Mar 2007 01:11:26 +0100 Received: from edenfox.989studios.com (edenfox.989studios.com [160.33.45.60]) by sdmx1.scea.com (8.13.6/8.13.1) with ESMTP id l260B0sa007172; Mon, 5 Mar 2007 16:11:00 -0800 X-Envelope-From: X-Envelope-To: X-Envelope-To: Received: from postal1-dog.naughtydog.com (testmail.naughtydog.com [10.15.0.5]) by edenfox.989studios.com (8.13.7/8.13.7/SCEAint-1.0) with ESMTP id l260AwYQ008588; Mon, 5 Mar 2007 16:10:58 -0800 Received: from [127.0.0.1] ([150.0.6.116]) by postal1-dog.naughtydog.com with Microsoft SMTPSVC(6.0.3790.1830); Mon, 5 Mar 2007 16:10:00 -0800 Message-ID: <45ECB0AB.7010404@naughtydog.com> Date: Mon, 05 Mar 2007 16:07:07 -0800 From: Pal-Kristian Engstad User-Agent: Thunderbird 1.5.0.10 (Windows/20070221) MIME-Version: 1.0 To: Pietro Abate Cc: caml-list@inria.fr Subject: Re: [Caml-list] to merge list of lists References: <20070305061050.GA21256@pulp.rsise.anu.edu.au> In-Reply-To: <20070305061050.GA21256@pulp.rsise.anu.edu.au> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-OriginalArrivalTime: 06 Mar 2007 00:10:00.0245 (UTC) FILETIME=[C7E61E50:01C75F83] X-Scanned-By: MIMEDefang 2.48 on 160.33.44.36 X-Scanned-By: MIMEDefang 2.48 on 160.33.45.59 X-BorderEnvelope-To: X-BorderEnvelope-To: X-Miltered: at concorde with ID 45ECB1AD.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; maxlen:01 maxlen:01 pke:01 flatten:01 dog:98 wrote:01 rec:01 rec:01 caml-list:01 imperative:01 int:01 primitives:01 match:02 overly:02 pal-kristian:03 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