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

[Julien Moutinho <julien.moutinho@gmail.com>]

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:

# let split l f =
	let rec aux =
		function
		| h::t as l ->
			if f h then
			let a,b = aux t in h::a,b
			else [],l
		| [] -> [],[]
	in aux l;;
val split : 'a list -> ('a -> bool) -> 'a list * 'a list = <fun>
# split [1;2;3;4;5;6] ((>=) 4);;
- : int list * int list = ([1; 2; 3; 4], [5; 6])

(* may trash the given list but tail-recursive *)
# let magic_split l f =
	let rec aux p =
		function
		| [] -> l,[]
		| h::t as b ->
			if f h then aux (Some b) t
			else match p with None -> [],l
			| Some p -> (Obj.magic p).(1) <- None; l,b
	in aux None l;;
val magic_split : 'a list -> ('a -> bool) -> 'a list * 'a list = <fun>
# let l = [1;2;3;4;5;6];;
val l : int list = [1; 2; 3; 4; 5; 6]
# magic_split l ((>=) 4);;
- : int list * int list = ([1; 2; 3; 4], [5; 6])
# l;;
- : int list = [1; 2; 3; 4]

HTH,
  Julien.