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=AWL,HTML_MESSAGE autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id AD4F9BC6B for ; Tue, 30 Oct 2007 14:05:36 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ah4FAFPJJkdCm3xr/2dsb2JhbACCcik X-IronPort-AV: E=Sophos;i="4.21,347,1188770400"; d="scan'208,217";a="3733775" Received: from www.janestcapital.com (HELO smtp.janestcapital.com) ([66.155.124.107]) by mail2-smtp-roc.national.inria.fr with ESMTP; 30 Oct 2007 14:05:36 +0100 Received: from [172.25.129.161] [38.96.172.125] by janestcapital.com with ESMTP (SMTPD-9.10) id AC1D0834; Tue, 30 Oct 2007 09:05:33 -0400 Message-ID: <47272C1C.4060009@janestcapital.com> Date: Tue, 30 Oct 2007 09:05:32 -0400 From: Brian Hurt User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: skaller Cc: Alain Frisch , caml-list@yquem.inria.fr Subject: Re: [Caml-list] Preferred Way to Split a List References: <47266DB7.1020009@SmokejumperIT.com> <20071030012012.GA29836@localhost> <1193723182.6129.66.camel@rosella.wigram> <4726E433.7060408@frisch.fr> <1193742901.6697.5.camel@rosella.wigram> In-Reply-To: <1193742901.6697.5.camel@rosella.wigram> Content-Type: multipart/alternative; boundary="------------020009010103060104000901" X-Spam: no; 0.00; 0100,:01 frisch:01 accum:01 accum:01 arrays:01 0100,:01 frisch:01 arrays:01 W8:98 W8:98 wrote:01 wrote:01 rec:01 rec:01 caml-list:01 This is a multi-part message in MIME format. --------------020009010103060104000901 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit skaller wrote: >On Tue, 2007-10-30 at 08:58 +0100, Alain Frisch wrote: > > >>skaller wrote: >> >> >>>The fastest way is: >>> >>> >>How can you be so sure? >> >> > >Why do I need to be something naturally impossible? >Certainty isn't even possible in the presence of a proof. > >The fact here is I made a complete mess! > >My algorithm doesn't meet the specification. LOL! >It doesn't split a list in two dang it! It actually >splits it in two then recombines the result and >returns the original list! :) > > > > Just so people know, Obj.magic is not necessary here: let take n lst = let rec loop accum n lst = if n == 0 then List.rev accum else match lst with | x :: xs -> loop (x :: accum) (n - 1) xs | [] -> List.rev accum in if n < 0 then invalid_arg "Negative argument to List.take" else loop [] n lst ;; let rec drop n lst = if n < 0 then invalid_arg "Negative argument to List.drop" else if n == 0 then lst else match lst with | _ :: xs -> drop (n - 1) xs | [] -> [] ;; I'd also take a look at the standard library functions List.filter and List.partition. With their standard, Obj.magic-less, implementations. If the list is long enough that the extra overhead of calling List.rev is a problem, I'd recommend using a better data structure than a list. I'm fond of tree-based "functional arrays", which allow for splitting them in O(log N), instead of O(N). We're clock cycle tuning bubble sort here. Brian --------------020009010103060104000901 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit skaller wrote:

On Tue, 2007-10-30 at 08:58 +0100, Alain Frisch wrote:

skaller wrote:

The fastest way is:

How can you be so sure?


Why do I need to be something naturally impossible?
Certainty isn't even possible in the presence of a proof.

The fact here is I made a complete mess!

My algorithm doesn't meet the specification. LOL!
It doesn't split a list in two dang it! It actually
splits it in two then recombines the result and
returns the original list! :)

Just so people know, Obj.magic is not necessary here:

let take n lst =
   let rec loop accum n lst =
      if n == 0 then
         List.rev accum
      else match lst with
         | x :: xs -> loop (x :: accum) (n - 1) xs
         | [] -> List.rev accum
   in
   if n < 0 then
      invalid_arg "Negative argument to List.take"
   else
      loop [] n lst
;;

let rec drop n lst =
   if n < 0 then
      invalid_arg "Negative argument to List.drop"
   else if n == 0 then
      lst
   else match lst with
      | _ :: xs -> drop (n - 1) xs
      | [] -> []
;;

I'd also take a look at the standard library functions List.filter and List.partition. With their standard, Obj.magic-less, implementations.

If the list is long enough that the extra overhead of calling List.rev is a problem, I'd recommend using a better data structure than a list. I'm fond of tree-based "functional arrays", which allow for splitting them in O(log N), instead of O(N). We're clock cycle tuning bubble sort here.

Brian

--------------020009010103060104000901--