Re: [Caml-list] Preferred Way to Split a List

[Brian Hurt <bhurt@janestcapital.com>]

[-- Attachment #1: Type: text/plain, Size: 1543 bytes --]

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


[-- Attachment #2: Type: text/html, Size: 2603 bytes --]