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

[skaller <skaller@users.sourceforge.net>]

On Tue, 2007-10-30 at 02:20 +0100, Julien Moutinho wrote:
> On Mon, Oct 29, 2007 at 06:33:11PM -0500, Robert Fischer wrote:
> > What is the preferred way to split a list into two, at an arbitrary point?  
> > There's lots of ways you could do it, but I'm not sure if there's a 
> > standard best practice for this.
> 
> Two answers for what they're worth:

Ouch. A simpler way is:

	let split ls n = let rec aux inp out n =
		if n = 0 then unsafe_rev_cat out inp
		else match inp with
		| [] -> unsafe_rev_cat out []
		| h :: t -> aux t (h::out) (n-1)
	in aux ls [] n

Here 'unsafe_rev_cat' uses magic to reverse a list in place
and tack the tail onto the end. 

However this isn't the fastest way. The fastest way is:

	let split ls n = 
		let out = magic_list() in
		let rec aux inp n =
			if n = 0 then magic_cat out inp
			else match inp with
			| [] -> ()
			| h :: t -> magic_append h out; aux t (n-1)
	in 
		aux ls n;
		list_of out

Here the magic list is the usual list data structure PLUS a pointer
to the last element allowing O(1) append. This is of course a mutable
data structure. All the operations here can be implemented without
Obj.magic, however it's much faster WITH Obj.magic: by using a 
magic list structure identical to an actual list, the 'list_of'
function becomes a typecast.

A similar code uses a reversed ordinary list for the temporary,
and then reverses it inplace (safe because it is a temporary)
and tacks the tail on. Felix uses that algorithm in its standard
library, however the one actually coded above is optimal (it isn't
possible to do it any faster).

Note the function above is purely functional (mutations are
isolated to the implementation) and does not itself use any
unsafe features (but the magic implementation is unsafe,
so it should be put in a library to limit bugs and 
implementation dependencies).

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net