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