This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Preferred Way to Split a List
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Brian Hurt Subject: Re: [Caml-list] Preferred Way to Split a List
```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

```