Preferred Way to Split a List

Preferred Way to Split a List

[Robert Fischer]

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.

~~ Robert.

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

[Matthew William Cox]

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

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.
That's the thing, there are lots of best ways. Which is the best depends
on what properties your list-splitter needs.

Do you need to preserve ordering in the sublists? Do they need to be
roughly equivalent lengths? Elaborating on these requirements will guide
your search.

Cheers,
Matt

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 827 bytes --]

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

[Robert Fischer]

> Do you need to preserve ordering in the sublists? 
>   
Yes.
> Do they need to be roughly equivalent lengths?
No -- the head list will probably be shorter than the tail list.

~~ Robert.

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

[Nathaniel Gray]

On Oct 30, 2007 6:18 AM, Robert Fischer <robert@fischerventure.com> wrote:
>
> > Do you need to preserve ordering in the sublists?
> >
> Yes.
> > Do they need to be roughly equivalent lengths?
> No -- the head list will probably be shorter than the tail list.

Hmm...

let fast_list_splitter = function
   | h :: t -> [h], t
   | [] -> [], []  (* Or maybe raise an exception? *)

Or if you're really shooting for speed:

let golly_it's_fast_list_splitter lst = [], lst

I win.  Seriously, you must have *some* further constraints!

Cheers,
-n8

-- 
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->

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

[Julien Moutinho]

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.

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

[Karl Zilles]

Julien Moutinho wrote:
 > (* 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]

Wow, this looks like a horrible idea!  You're modifying a non-mutable 
data structure and using object magic.  This leads to madness:

# let test () = magic_split [1; 2; 3; 4; 5; 6] ((>=) 4);;
val test : unit -> int list * int list = <fun>
# test ();;
- : int list * int list = ([1; 2; 3; 4], [5; 6])
# test ();;
- : int list * int list = ([1; 2; 3; 4], [])

I'm sure you're aware of this, but to suggest this as an answer to his 
question...

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

[skaller]

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

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

[Alain Frisch]

skaller wrote:
> The fastest way is:

How can you be so sure? Do you have a proof or some intuitive argument?
Or maybe you tried all the possible other implementations? The following 
should not be that much slower (I did not try it, though, and of course, 
it is not tail-rec):

let split l n =
   let l2 = ref [] in
   let rec aux l n =
     if n = 0 then (l2 := l; [])
     else match l with
       | [] -> []
       | hd :: tl -> hd :: (aux tl (n - 1))
   in
   let l1 = aux l n in
   (l1, !l2)


Alain

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

[Christophe Raffalli]

[-- Attachment #1.1: Type: text/plain, Size: 1043 bytes --]

Or

let split l n =
  let rec aux acc l n =
     if n = 0 then List.rev acc, l
     else match l with
        [] -> List.rev acc, []
     | hd::l -> aux (hd::acc) l (n-1)
  in aux [] l n

This is tail recursive, it does not use magic nor  references
and keed the original ordering of the list.

Finally, I did in the past some testing  comparing a tail-rec append or map
using magic and the composition of rev and rev-append or rev-map ...
There was no noticable difference, because the extra cost  of
mutability (regarding the managment of the grey val list) compensate
the extra call to reverse.

So I think I would write split the way shown above if ordering matters.

Cheers,
Christophe
>
> Alain
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

[-- Attachment #1.2: Christophe.Raffalli.vcf --]
[-- Type: text/x-vcard, Size: 380 bytes --]

begin:vcard
fn:Christophe Raffalli
n:Raffalli;Christophe
org:LAMA (UMR 5127)
email;internet:Christophe.Raffalli@univ-savoie.fr
title;quoted-printable:Ma=C3=AEtre de conf=C3=A9rences
tel;work:+33 4 79 75 81 03
note;quoted-printable:Message sign=C3=A9 cryptographiquement avec pgp, la clef publique est sur=
	 subkeys.pgp.net
x-mozilla-html:TRUE
version:2.1
end:vcard


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

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

[skaller]

On Mon, 2007-10-29 at 10:34 +0100, Christophe Raffalli wrote:
> Or
> 
> let split l n =
>   let rec aux acc l n =
>      if n = 0 then List.rev acc, l
>      else match l with
>         [] -> List.rev acc, []
>      | hd::l -> aux (hd::acc) l (n-1)
>   in aux [] l n
> 
> This is tail recursive, it does not use magic nor  references
> and keed the original ordering of the list.

Yes, but it double handles the head needlessly. Ignoring
the interesting observation you make below, this would
be expected to transfer head memory twice into the cache,
when once would suffice.

> Finally, I did in the past some testing  comparing a tail-rec append or map
> using magic and the composition of rev and rev-append or rev-map ...
> There was no noticable difference, because the extra cost  of
> mutability (regarding the managment of the grey val list) compensate
> the extra call to reverse.

However, you raise here an important issue not covered well anywhere:
when you have a garbage collection, the effect of some operation
should include not just the local algorithmic considerations
but also the cost of the garbage collection.

In the equivalent Felix code, there is no issue with write
barriers because Felix collector doesn't use them, so mutations
don't incur any cost. OTOH allocations are expensive.

Now, back to collectors .. the append is a special.
The mutations in the append are not mutations, but deferred
initialisations, that is, the write operation is guaranteed
to be replacing a NULL pointer.

Overwriting of NULL pointers is already possible in functional
coding without it implying mutation.

So one might imagine a collector with a minor and major heap,
in which the major heap requires special handling for mutations.
However the rule for moving an object out of the minor heap
is that the object must be fully initialised. (all pointers
in the block are non-null). 

In that design (I have no idea if it is viable!) the performance
might be different for the 'append' and other mutations.

The bottom line is that a good point is made that the 
usual fine detail performance analysis doesn't apply to
a garbage collected language.. thanks for pointing this out!


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

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

[David Allsopp]

Christophe Raffalli wrote:
> let split l n =
>   let rec aux acc l n =
>      if n = 0 then List.rev acc, l
>      else match l with
>         [] -> List.rev acc, []
>      | hd::l -> aux (hd::acc) l (n-1)
>   in aux [] l n

I'd go one stage further and use Obj.magic to eliminate the List.rev calls
(cf. ExtList.List in ExtLib). I'm sensibly wary of using Obj.magic in
general but find it acceptable here because its use is hidden within the
function (you are constructing a new list anyway, you just use Obj.magic to
allow tail-consing instead) - and there is no risk of "entertaining" side
effects (cf. John's earlier email!). I've got tail-consing wrapped in a few
extra functions in List so that this would become:

let split l n =
  let acc = List.tlempty ()
  in
    let rec aux l n =
       if n = 0 then (List.tlresult acc, l)
       else match l with
              []    -> (List.tlresult acc, [])
            | hd::l -> List.tlcons hd acc; aux l (n-1)
    in
      aux l n


David


PS List.tlempty:        returns a new, empty tail-consing list
   List.tlcons x tlist: adds x to the end of the given tlist and returns
                        the same tlist pointer
   List.tlresult tlist: casts an 'a tlist to an 'a list - and marks the
                        tlist as "exported", preventing future tail-consing
                        (which would violate the semantics of O'Caml 'a
                        lists)

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

[Christophe Raffalli]

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

David Allsopp a écrit :
> Christophe Raffalli wrote:
>> let split l n =
>>   let rec aux acc l n =
>>      if n = 0 then List.rev acc, l
>>      else match l with
>>         [] -> List.rev acc, []
>>      | hd::l -> aux (hd::acc) l (n-1)
>>   in aux [] l n
> 
> let split l n =
>   let acc = List.tlempty ()
>   in
>     let rec aux l n =
>        if n = 0 then (List.tlresult acc, l)
>        else match l with
>               []    -> (List.tlresult acc, [])
>             | hd::l -> List.tlcons hd acc; aux l (n-1)
>     in
>       aux l n
> 
> 

My point in my second last post was that in practice, for OCaml, the
second code is not much faster than the first ...

All this forced me to redo the testing : the details are bellow, but
list_split with rev wins for small list, the dirty thing with set_field
wins for big lists and the transition is between length 10000 and 100000.
Overall the difference is small.

Remark: the result might differ a lot for map if the mapped function does allocate memory ...
then there should almost no difference ...

So I would advice not to use Obj.set_field in this case ...

(* module for lists that can be constructed by both end *)
module Tlist = struct
  type 'a tlist = 'a list * 'a list

  (* a fake value for the tail of a list *)
  let rec dummy_tlist = Obj.magic 0::dummy_tlist

  let empty = [], []

  let tailcons tl a =
    match tl with
      [], [] -> let tl = a :: dummy_tlist in (tl, tl)
    | (_::_ as s), (_::dl as e) when dl == dummy_tlist ->
	let e' = a::dummy_tlist in
	Obj.set_field (Obj.repr e) 1 (Obj.repr e');
	s, e'
    | _ -> raise (Invalid_argument "Tlist.tail_cons")

  let cons a tl =
    match tl with
      [], [] -> let tl = a :: dummy_tlist in (tl, tl)
    | (_::_ as s), (_::dl as e) when dl ==  dummy_tlist ->
	a::s, e
    | _ -> raise (Invalid_argument "Tlist.cons")

  (* this must be the final call to transform a 'a tlist into a list *)
  let append tl l =
    match tl with
      [], [] -> l
    | (_::_ as s), (_::dl as e) when dl == dummy_tlist ->
	Obj.set_field (Obj.repr e) 1 (Obj.repr l);
	s
    | _ -> raise (Invalid_argument "Tlist.append")
end

(* the two versions of split *)
let split_with_rev l n =
   let rec aux acc l n =
      if n = 0 then List.rev acc, l
      else match l with
         [] -> List.rev acc, []
      | hd::l -> aux (hd::acc) l (n-1)
   in aux [] l n

let split_with_tlist l n =
  let rec aux acc l n =
    if n = 0 then (Tlist.append acc [], l)
    else match l with
      [] -> Tlist.append acc [], []
    | hd::l -> aux (Tlist.tailcons acc hd) l (n-1)
  in
  aux Tlist.empty l n

(* code for testing *)
let rec build_list n =
  let rec aux acc n =
    if n = 0 then acc else aux (n::acc) (n-1)
  in
  aux [] n

let test_tlist n p =
  for i = 1 to n do
    ignore (split_with_tlist (build_list (2*p)) p)
  done

let test_rev n p =
  for i = 1 to n do
    ignore (split_with_rev (build_list (2*p)) p)
  done

let _ = test_tlist 10 1000000

(*
result:

  test_tlist 10000000 10 : 3.1s
  test_rev 10000000 10 : 2.6s

  test_tlist 100000 1000 : 8.8s
  test_rev 100000 1000 : 6.9s

  test_tlist 100 100000 : 5.9s
  test_rev 100 100000 : 7.4s

  test_tlist 10 1000000 : 6.2s
  test_rev 10 1000000 : 7.9s
*)

-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

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

[skaller]

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! :)


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

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

[Brian Hurt]

[-- 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 --]

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

[Jon Harrop]

On Monday 29 October 2007 23:33, 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.

I tend to write a combinator that nests an arbitrary number of function 
applications:

# let rec nest n f x =
    if n=0 then x else nest (n-1) f (f x);;
val nest : int -> ('a -> 'a) -> 'a -> 'a = <fun>

and then apply this to a function that moves head elements:

# let aux = function
    | front, h::back -> h::front, back
    | _ -> invalid_arg "aux";;
val aux : 'a list * 'a list -> 'a list * 'a list = <fun>

Then I write a "chop" function in terms of those two:

# let chop n list =
    nest n aux ([], list);;
val chop : int -> 'a list -> 'a list * 'a list = <fun>

For example, splitting after the fourth element:

# chop 4 [1;2;3;4;5;6;7;8;9];;
- : int list * int list = ([4; 3; 2; 1], [5; 6; 7; 8; 9])

Note that the front list is reversed.

PS: Ignore any responses that even mention Obj.
-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

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

[Robert Fischer]

[-- Attachment #1: Type: text/html, Size: 1591 bytes --]