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 mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 0047BBC6B for ; Tue, 30 Oct 2007 13:30:56 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAB7BJkfC2fJWnmdsb2JhbACOXwIBAQcEBhEYgRM X-IronPort-AV: E=Sophos;i="4.21,347,1188770400"; d="scan'208";a="5278568" Received: from anchor-post-36.mail.demon.net ([194.217.242.86]) by mail3-smtp-sop.national.inria.fr with ESMTP; 30 Oct 2007 13:30:56 +0100 Received: from orion.metastack.com ([80.177.38.218]) by anchor-post-36.mail.demon.net with esmtp (Exim 4.67) id 1ImqF3-0008uZ-L9 for caml-list@yquem.inria.fr; Tue, 30 Oct 2007 12:30:45 +0000 Received: from countertenor (cpc3-cmbg6-0-0-cust100.cmbg.cable.ntl.com [81.101.140.101]) (authenticated bits=0) by orion.metastack.com (8.13.4/8.13.3) with ESMTP id l9UCSbSS031184 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NO) for ; Tue, 30 Oct 2007 12:28:38 GMT From: "David Allsopp" To: References: <47266DB7.1020009@SmokejumperIT.com> <20071030012012.GA29836@localhost> <1193723182.6129.66.camel@rosella.wigram><4726E433.7060408@frisch.fr> <4725A915.3020005@univ-savoie.fr> Subject: RE: [Caml-list] Preferred Way to Split a List Date: Tue, 30 Oct 2007 12:30:36 -0000 Organization: MetaStack Solutions Ltd. Message-ID: <000001c81af0$ad1ad830$017ca8c0@countertenor> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Office Outlook 11 Thread-Index: Acga13AJFn2WhCBuQCCoqYg/tZd+/gAGSi8g In-Reply-To: <4725A915.3020005@univ-savoie.fr> X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.3198 X-Spam: no; 0.00; christophe:01 raffalli:01 pointer:01 casts:01 violate:01 semantics:01 o'caml:01 wrote:01 rec:01 rec:01 caml-list:01 functions:01 match:02 match:02 let:03 Christophe Raffalli wrote: > let split l n = > let rec aux acc l n = > if n = 0 then List.rev acc, l > else match l with > [] -> List.rev acc, [] > | hd::l -> aux (hd::acc) l (n-1) > in aux [] l n I'd go one stage further and use Obj.magic to eliminate the List.rev calls (cf. ExtList.List in ExtLib). I'm sensibly wary of using Obj.magic in general but find it acceptable here because its use is hidden within the function (you are constructing a new list anyway, you just use Obj.magic to allow tail-consing instead) - and there is no risk of "entertaining" side effects (cf. John's earlier email!). I've got tail-consing wrapped in a few extra functions in List so that this would become: let split l n = let acc = List.tlempty () in let rec aux l n = if n = 0 then (List.tlresult acc, l) else match l with [] -> (List.tlresult acc, []) | hd::l -> List.tlcons hd acc; aux l (n-1) in aux l n David PS List.tlempty: returns a new, empty tail-consing list List.tlcons x tlist: adds x to the end of the given tlist and returns the same tlist pointer List.tlresult tlist: casts an 'a tlist to an 'a list - and marks the tlist as "exported", preventing future tail-consing (which would violate the semantics of O'Caml 'a lists)